Задача нахождения минимального покрытия |
Задача нахождения минимального покрытия |
Scorp_Freeman |
17.01.2008 10:54
Сообщение
#1
|
Пионер Группа: Пользователи Сообщений: 68 Пол: Мужской Реальное имя: Сергей Репутация: 0 |
У меня вот такая проблема(
Я минимизирую булевую функцию методом Квайна-мак-Класки который условно можно поделить да две подзадачи - склеивание наборов до получения пустого и нахождение миним. покрытия. Так вот первую часть я выполнил, а во второй не могу найти метод, который можно было бы это сделать((. Полный перебор не подходит... К примеру после решения первой части задачи выходит вот такая таблица покрытий: __________________________________________ ______0110____0010____0101____0001____1000____1101 01х1____________________1_________________________ х101____________________1_______________________1_ 011х____1_________________________________________ хх10_____1______1_________________________________ Я хотел попробовать методом Петрика.... но кажется он не так прост для программирования его( может есть какие то попроще, кто знает? )) Сообщение отредактировано: Scorp_Freeman - 17.01.2008 10:58 |
Michael_Rybak |
17.01.2008 12:09
Сообщение
#2
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
насколько я помню наш курс дискретки, лучшее, что придумали - как раз известные теоретические алгоритмы. но это так, отдаленно помню.
хочешь - опиши, в чем суть, может подскажу, как безболезненно закодить. |
Гость |
17.01.2008 18:44
Сообщение
#3
|
Гость |
Суть такова:
В результате выполнения первой подзадачки у меня на выходе получается табличка которую я представил раньше (я ее пока представляю как двумерный вектор, матрицу). Строки этой матрицы - это все наборы на которых минимизируемая функция принимает значение равное 1 (для моего примера, 0110, 0010, 0101, 0001, 1000, 1101 ), а строки - "маски", в которых кроме символов "0" и "1" встречаются "х" (любое из "0"/ "1") Так к примеру маска "01х0" покрывает следующие наборы: 0110 и 0100. И т.д. Цель: Найти минимальное покрытие, т.е. множество масок покрывающих все наборы на которых функция принимает значение 1. Лучше всего было бы это разобрать метод Петрика так как он дает точный результат по сравнению, для примера, с методом минимальной строки/столбца. Но вот как его реализовать, и как представить эту таблицу покрытий пока загадка) |
Scorp_Freeman |
17.01.2008 18:47
Сообщение
#4
|
Пионер Группа: Пользователи Сообщений: 68 Пол: Мужской Реальное имя: Сергей Репутация: 0 |
Это я гость)) забыл про авторизацию))))
|
Michael_Rybak |
18.01.2008 3:34
Сообщение
#5
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
А тебе точно не подойдет полный перебор? Для функций четырех переменный его хватит с головой, и писать гораздо меньше.
Почитал про метод Петрика. Дебри, конечно, но ничего смертельного; просто берешь, и так и делаешь, как сказано В чем проблема с представлением таблицы покрытий? Просто булевский двумерный массив (true - если покрывает, false - если нет). А маски представляй, для удобства, в системе счисления с основанием 4: 0 это 0, 1 это 1, 2 это "х", а 3 не используется. Можно было бы в троичной, но с основанием 4 удобнее работать - можно с помощью сдвигов легко манипулировать разрядами. Или представляй парой чисел - первое с единицами вместо "х", а второе - с единицами вместо "х" и нулями вместо не "х". Например, маску "01х1" представляй парой (0111, 0010). Первое число в паре задает точные биты, а второе говорит, где у нас иксы. Вообще, можно и обойтись без этой матрицы, и просто на ходу для каждой пары (маска, набор) вычислять, покрывает ли маска этот набор. |
Scorp_Freeman |
18.01.2008 15:14
Сообщение
#6
|
Пионер Группа: Пользователи Сообщений: 68 Пол: Мужской Реальное имя: Сергей Репутация: 0 |
А тебе точно не подойдет полный перебор? Для функций четырех переменный его хватит с головой, и писать гораздо меньше. Нет, не подойдет)) Я для примера показал наборі из 3ех разрядов, у меня макс. кол-во разрядов - 32 Цитата Почитал про метод Петрика. Дебри, конечно, но ничего смертельного; просто берешь, и так и делаешь, как сказано Там выполняются упрощения по формулам, например, (A + B)*(A+C) = A+AC+BA+CA и т.д. Вот именно это меня и смущает( Ведь этих множеств(А, В...) не постоянноеколичество... |
Michael_Rybak |
18.01.2008 15:16
Сообщение
#7
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Ну и что, что не постоянное? Заводишь массив заведомо больший, и хранишь количество символов в отдельной переменной + сами символы в этом массиве.
|
Scorp_Freeman |
18.01.2008 15:24
Сообщение
#8
|
Пионер Группа: Пользователи Сообщений: 68 Пол: Мужской Реальное имя: Сергей Репутация: 0 |
можно попробовать... идея появилась,правда придется повозиться )))
|
Michael_Rybak |
18.01.2008 15:26
Сообщение
#9
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Повозиться тут определенно придется. Особенно на паскале.
|
Scorp_Freeman |
18.01.2008 15:28
Сообщение
#10
|
Пионер Группа: Пользователи Сообщений: 68 Пол: Мужской Реальное имя: Сергей Репутация: 0 |
А чего особенно на паскале? Хотя я все равно буду делать на Си++, но Паскаль я лучше знаю)))), но выбора у меня уже нету....)
|
Michael_Rybak |
18.01.2008 15:37
Сообщение
#11
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Так на с++ векторами гораздо удобнее! Вектор - это массив, у которого можно менять длину. Погугли std::vector example.
Сделай класс маски с нужными тебе операторами/методами, и заводи вектор масок. Загляденье будет. |
Scorp_Freeman |
18.01.2008 15:43
Сообщение
#12
|
Пионер Группа: Пользователи Сообщений: 68 Пол: Мужской Реальное имя: Сергей Репутация: 0 |
Говоришь векторы)) Посмотрим с чем их едят Спасибо! Пойду кодить тогда))
А еще тогда вопрос не по теме) При закрытии приложения векторы сами очищаются или надо самому их очистить? Как я понимаю это типа динамические в паскале? |
Michael_Rybak |
18.01.2008 15:54
Сообщение
#13
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Типа динамических в паскале, но на порядок удобнее. Очищаются сами. Всю работу с памятью делают сами. Ты только размер указываешь, добавляешь/удаляешь элементы и т.п. Для тебя это получается просто переменная, которая умеет делать []
|
Текстовая версия | 19.04.2024 5:57 |