Ваша проблема нуждается в небольшом уточнении - кажется, вам дано семейство подмножеств $$ S_1, \ ldots, S_n $$ множества A, такое, что объединение подмножеств равно A, и вы хотите минимальное количество подмножеств, объединение которых по-прежнему равно A.
Основной подход является ветвлением и связан с некоторыми эвристиками. Например, если конкретный элемент A находится только в одном подмножестве $$ S_i $$, то вы должны выбрать $$ S_i $$. Точно так же, если $$ S_k $$ является подмножеством $$ S_j $$, то нет причин рассматривать $$ S_k $$; если элемент $$ a_i $$ находится в каждом подмножестве, в котором находится $$ a_j $$, то вы можете не задумываться над $$ a_i $$.
Для ветвления и связывания вам нужна хорошая ограничивающая эвристика. Нижние границы могут быть получены из независимых множеств (если есть k элементов $$ i_1, \ ldots, i_L $$ в A, таких что каждый, если $$ i_p $$ содержится в $$ A_p $$ и $$ i_q $$ содержится в $$ A_q $$ тогда $$ A_p $$ и $$ A_q $$ не пересекаются). Лучшие нижние границы получаются из релаксации LP, описанной выше.
Система минимизации логики Espresso от Berkeley имеет очень качественный комплект покрывающего двигателя.