IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> Задача нахождения минимального покрытия
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Сергей

Репутация: -  0  +


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

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

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

__________________________________________

______0110____0010____0101____0001____1000____1101

01х1____________________1_________________________

х101____________________1_______________________1_

011х____1_________________________________________

хх10_____1______1_________________________________


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

Сообщение отредактировано: Scorp_Freeman -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

хочешь - опиши, в чем суть, может подскажу, как безболезненно закодить.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Гость






Суть такова:

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

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

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

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

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


Пионер
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Сергей

Репутация: -  0  +


Это я гость)) забыл про авторизацию))))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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

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

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

Вообще, можно и обойтись без этой матрицы, и просто на ходу для каждой пары (маска, набор) вычислять, покрывает ли маска этот набор.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Сергей

Репутация: -  0  +


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

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


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

Цитата

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


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


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Ну и что, что не постоянное? Заводишь массив заведомо больший, и хранишь количество символов в отдельной переменной + сами символы в этом массиве.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Сергей

Репутация: -  0  +


smile.gif можно попробовать... идея появилась,правда придется повозиться )))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Повозиться тут определенно придется. Особенно на паскале.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Пионер
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Сергей

Репутация: -  0  +


А чего особенно на паскале? Хотя я все равно буду делать на Си++, но Паскаль я лучше знаю)))), но выбора у меня уже нету....)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

Сделай класс маски с нужными тебе операторами/методами, и заводи вектор масок. Загляденье будет.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Пионер
**

Группа: Пользователи
Сообщений: 68
Пол: Мужской
Реальное имя: Сергей

Репутация: -  0  +


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

А еще тогда вопрос не по теме) При закрытии приложения векторы сами очищаются или надо самому их очистить? Как я понимаю это типа динамические в паскале?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 12:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name