Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Алгоритмы _ Задача нахождения минимального покрытия

Автор: Scorp_Freeman 17.01.2008 14:54

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

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

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

__________________________________________

______0110____0010____0101____0001____1000____1101

01х1____________________1_________________________

х101____________________1_______________________1_

011х____1_________________________________________

хх10_____1______1_________________________________


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

Автор: Michael_Rybak 17.01.2008 16:09

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

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

Автор: Гость 17.01.2008 22:44

Суть такова:

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

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

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

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

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

Автор: Scorp_Freeman 17.01.2008 22:47

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

Автор: Michael_Rybak 18.01.2008 7:34

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

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

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

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

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

Автор: Scorp_Freeman 18.01.2008 19:14

Цитата(Michael_Rybak @ 18.01.2008 4:34) *

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


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

Цитата

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


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

Автор: Michael_Rybak 18.01.2008 19:16

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

Автор: Scorp_Freeman 18.01.2008 19:24

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

Автор: Michael_Rybak 18.01.2008 19:26

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

Автор: Scorp_Freeman 18.01.2008 19:28

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

Автор: Michael_Rybak 18.01.2008 19:37

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

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

Автор: Scorp_Freeman 18.01.2008 19:43

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

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

Автор: Michael_Rybak 18.01.2008 19:54

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