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

[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]

А тебе точно не подойдет полный перебор? Для функций четырех переменный его хватит с головой, и писать гораздо меньше.

Почитал про метод Петрика. Дебри, конечно, но ничего смертельного; просто берешь, и так и делаешь, как сказано

В чем проблема с представлением таблицы покрытий? Просто булевский двумерный массив (true - если покрывает, false - если нет). А маски представляй, для удобства, в системе счисления с основанием 4: 0 это 0, 1 это 1, 2 это "х", а 3 не используется. Можно было бы в троичной, но с основанием 4 удобнее работать - можно с помощью сдвигов легко манипулировать разрядами.

Или представляй парой чисел - первое с единицами вместо "х", а второе - с единицами вместо "х" и нулями вместо не "х". Например, маску "01х1" представляй парой (0111, 0010). Первое число в паре задает точные биты, а второе говорит, где у нас иксы.

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