Задача нахождения минимального покрытия Опции

[Scorp_Freeman]

У меня вот такая проблема(
Я минимизирую булевую функцию методом Квайна-мак-Класки который условно можно поделить да две подзадачи - склеивание наборов до получения пустого и нахождение миним. покрытия.

Так вот первую часть я выполнил, а во второй не могу найти метод, который можно было бы это сделать((. Полный перебор не подходит...

К примеру после решения первой части задачи выходит вот такая таблица покрытий:

__________________________________________

______0110____0010____0101____0001____1000____1101

01х1____________________1_________________________

х101____________________1_______________________1_

011х____1_________________________________________

хх10_____1______1_________________________________


Я хотел попробовать методом Петрика.... но кажется он не так прост для программирования его( может есть какие то попроще, кто знает? ))

Сообщение отредактировано: Scorp_Freeman - 17.01.2008 14:58

[Michael_Rybak]

насколько я помню наш курс дискретки, лучшее, что придумали - как раз известные теоретические алгоритмы. но это так, отдаленно помню.

хочешь - опиши, в чем суть, может подскажу, как безболезненно закодить.

[Гость]

Суть такова:

В результате выполнения первой подзадачки у меня на выходе получается табличка которую я представил раньше (я ее пока представляю как двумерный вектор, матрицу).

Строки этой матрицы - это все наборы на которых минимизируемая функция принимает значение равное 1
(для моего примера, 0110, 0010, 0101, 0001, 1000, 1101 ), а строки - "маски", в которых кроме символов "0" и "1" встречаются "х" (любое из "0"/ "1")

Так к примеру маска "01х0" покрывает следующие наборы: 0110 и 0100. И т.д.

Цель: Найти минимальное покрытие, т.е. множество масок покрывающих все наборы на которых функция принимает значение 1.

Лучше всего было бы это разобрать метод Петрика так как он дает точный результат по сравнению, для примера, с методом минимальной строки/столбца. Но вот как его реализовать, и как представить эту таблицу покрытий пока загадка)