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

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

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

__________________________________________

______0110____0010____0101____0001____1000____1101

01х1____________________1_________________________

х101____________________1_______________________1_

011х____1_________________________________________

хх10_____1______1_________________________________


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

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

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

Суть такова:

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

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

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

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

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

Это я гость)) забыл про авторизацию))))

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

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

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

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

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

Нет, не подойдет)) Я для примера показал наборі из 3ех разрядов, у меня макс. кол-во разрядов - 32



Там выполняются упрощения по формулам, например, (A + B)*(A+C) = A+AC+BA+CA и т.д. Вот именно это меня и смущает( Ведь этих множеств(А, В...) не постоянноеколичество...

Ну и что, что не постоянное? Заводишь массив заведомо больший, и хранишь количество символов в отдельной переменной + сами символы в этом массиве.

можно попробовать... идея появилась,правда придется повозиться )))

Повозиться тут определенно придется. Особенно на паскале.

А чего особенно на паскале? Хотя я все равно буду делать на Си++, но Паскаль я лучше знаю)))), но выбора у меня уже нету....)

Так на с++ векторами гораздо удобнее! Вектор - это массив, у которого можно менять длину. Погугли std::vector example.

Сделай класс маски с нужными тебе операторами/методами, и заводи вектор масок. Загляденье будет.

Говоришь векторы)) Посмотрим с чем их едят Спасибо! Пойду кодить тогда))

А еще тогда вопрос не по теме) При закрытии приложения векторы сами очищаются или надо самому их очистить? Как я понимаю это типа динамические в паскале?

Типа динамических в паскале, но на порядок удобнее. Очищаются сами. Всю работу с памятью делают сами. Ты только размер указываешь, добавляешь/удаляешь элементы и т.п. Для тебя это получается просто переменная, которая умеет делать []