Всем привет!

Подкинули мне тут задачку, да вот не знаю, как решить.
Есть матрица 4х4 заполненная 0 и 1. Надо выделить в ней прямоугольники, состоящие из 1, причем:
0. Помимо всего прочего соседними считаются первая и последняя строки и первый и последний столбей (короче, карта Карно)
1. Площадь прямоугольников должна равняться степени 2 (вариант когда есть 16 единиц исключен)
2. Каждая единица может покрываться несколько раз
3. Прямоугольник, покрывающий данную 1, должен быть наибольшего размераь (естественно не должно быть найдено 2 и более

абсолютно одинаковых прямоугольника). Но есть исключение: когда рядом с 1, которая может быть объединена в большой

прямоугольник, есть сосед, который может быть объединен только с ней.

Пример:

   ~y ~y  y  y
 x  1  1  0  1  u
 x  1  1  0  1 ~u
~x  1  0  1  1 ~u
~x  1  1  0  0  u
   ~z  z  z ~z

Выделяем:

1000   1100   1100   1001   0000
1000   1100   0000   1001   0000
1000   0000   0000   0000   0011
1000   0000   1100   0000   0000

Итого: f = (~y /\ ~z) \/ (x /\ ~y) \/ (~y /\ u) \/ (x /\ ~z) \/ (~x /\ y /\ ~u)

Вот такая вот задача. Кстати ее совершенно не обязательно решать самым оптимальным методом. Пока я вижу только одно решение:

в лоб — т.е. перебрать все прямоугольники, благо их немного.

Заранее спасибо.

Здравствуйте, Reunion, Вы писали:

R>

R>   ~y ~y  y  y
R> x  1  1  0  1  u
R> x  1  1  0  1 ~u
R>~x  1  0  1  1 ~u
R>~x  1  1  0  0  u
R>   ~z  z  z ~z
R>

В этой карте — очевидно, лучше строить не ДНФ, а КНФ: (~x|y|u)^(x|y|z)^(~x|~y|z|~u)

К>В этой карте — очевидно, лучше строить не ДНФ, а КНФ: (~x|y|u)^(x|y|z)^(~x|~y|z|~u)

Пардон, забыл проинвертировать : (x|~y|~u)^(~x|~y|~z)^(x|y|~z|u)

> Подкинули мне тут задачку, да вот не знаю, как решить.
>
Когда-то ооочень давно с товарищем писали прогу минимизации булевых функций (как детерминированных, так и нет), причём писали это дело ещё на VisualBasic'е (как вспомню аж в дрожь бросает)!!!
Если интересно, то саму прогу можешь здесь глянуть, а если хочешь на наши исходники взглянуть, то могу тебе их кинуть!!!

P. S. Для меньшего гемороя с выводом минимизированной функции в виде текста я не стал сильно париться и сделал весь вывод в Unicod'е с использованием Arial Unicode MS (идёт вместе с офисом)!!!

Здравствуйте, Кодт, Вы писали:

К>>В этой карте — очевидно, лучше строить не ДНФ, а КНФ: (~x|y|u)^(x|y|z)^(~x|~y|z|~u)

К>Пардон, забыл проинвертировать : (x|~y|~u)^(~x|~y|~z)^(x|y|~z|u)

Когда мне давали задание, сказали, что ДНФ. Но мне вот сейчас кажется, что это не совсем хорошо. Короче, спасибо, буду делать как надо. Кстати, я правильно понимаю, что ДНФ — когда количество 1 >= количества 0? А КНФ, соответственно, наоборот...

Здравствуйте, Stanky, Вы писали:

>> Подкинули мне тут задачку, да вот не знаю, как решить.
>>
S>Когда-то ооочень давно с товарищем писали прогу минимизации булевых функций (как детерминированных, так и нет), причём писали это дело ещё на VisualBasic'е (как вспомню аж в дрожь бросает)!!!
S>Если интересно, то саму прогу можешь здесь глянуть, а если хочешь на наши исходники взглянуть, то могу тебе их кинуть!!!

Хочу: .

S>P. S. Для меньшего гемороя с выводом минимизированной функции в виде текста я не стал сильно париться и сделал весь вывод в Unicod'е с использованием Arial Unicode MS (идёт вместе с офисом)!!!
Странно, у меня отображаются только иксы и квадратики...

Здравствуйте, Reunion, Вы писали:

R>Когда мне давали задание, сказали, что ДНФ. Но мне вот сейчас кажется, что это не совсем хорошо. Короче, спасибо, буду делать как надо. Кстати, я правильно понимаю, что ДНФ — когда количество 1 >= количества 0? А КНФ, соответственно, наоборот...

Скорее, наоборот. Но я бы вот так обобщать не стал...

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, Reunion, Вы писали:

R>>Когда мне давали задание, сказали, что ДНФ. Но мне вот сейчас кажется, что это не совсем хорошо. Короче, спасибо, буду делать как надо. Кстати, я правильно понимаю, что ДНФ — когда количество 1 >= количества 0? А КНФ, соответственно, наоборот...

К>Скорее, наоборот.

Ну да, я тоже забыл синвертировать...

К>Но я бы вот так обобщать не стал...

Приведи пример, посмотрим, подумаем... Я все равно еще исходник не получил, а перебором пока делать лень — времени еще много остается

> Странно, у меня отображаются только иксы и квадратики...
>
У тебя Arial Unicode MS не установлен!!!

Здравствуйте, Stanky, Вы писали:

>> Странно, у меня отображаются только иксы и квадратики...
>>
S>У тебя Arial Unicode MS не установлен!!!

А офис стоит!!! Ладно, это не важно.

> А офис стоит!!! Ладно, это не важно.
>
Чтоб этот шрифт поставился нужно при установке "Общие средства Office->Многоязыковая поддержка->Выбрать все пункты"!!!

Здравствуйте, Reunion, Вы писали:

К>>Но я бы вот так обобщать не стал...

R>Приведи пример, посмотрим, подумаем... Я все равно еще исходник не получил, а перебором пока делать лень — времени еще много остается

       x
    +++ ---
  - 1 1 0 0 +
y - 1 1 0 0 - t
  + 1 1 0 0 -
  + 1 1 1 0 +
    - +++ -
       z

DNF = (x) | (y&z&t)
CNF = (x|z) & (x|y) & (x|t)

Пример того, как количество единиц/нулей не согласовано с размером форм.

Здравствуйте, Кодт, Вы писали:

К>>>Но я бы вот так обобщать не стал...

R>>Приведи пример, посмотрим, подумаем... Я все равно еще исходник не получил, а перебором пока делать лень — времени еще много остается

К>

К>       x
К>    +++ ---
К>  - 1 1 0 0 +
К>y - 1 1 0 0 - t
К>  + 1 1 0 0 -
К>  + 1 1 1 0 +
К>    - +++ -
К>       z

К>DNF = (x) | (y&z&t)
К>CNF = (x|z) & (x|y) & (x|t)
К>

К>Пример того, как количество единиц/нулей не согласовано с размером форм.

К моему великому щастью я узнал, что мне нужна именно минимальная ДНФ Ее я уже почти получил — осталось выкинуть лишние слагаемые, которые возникают при определенном раскладе. Хотя, просто так, ради интереса можно посидеть дальше, что-то мне эта задача (полной минимизации) понравилась

Здравствуйте, Stanky, Вы писали:

>> А офис стоит!!! Ладно, это не важно.
>>
S>Чтоб этот шрифт поставился нужно при установке "Общие средства Office->Многоязыковая поддержка->Выбрать все пункты"!!!

Спаси,о за исходник — он меня на умные идеи навел...

> К моему великому щастью я узнал, что мне нужна именно минимальная ДНФ
> Ее я уже почти получил — осталось выкинуть лишние слагаемые,
> которые возникают при определенном раскладе. Хотя, просто так, ради
> интереса можно посидеть дальше, что-то мне эта задача (полной
> минимизации) понравилась
>
Я сейчас уже конечно не очень хорошо эту тему помню, но для машинной минимизации есть метод Квайна-Максласски (вроде так) и вроде ещё какой-то!!! Так же есть ещё поиск тупиковых форм — всё это мы использовали в своей проге, так что советую найти описание сего детища!!!

Здравствуйте, Stanky, Вы писали:

>> К моему великому щастью я узнал, что мне нужна именно минимальная ДНФ
>> Ее я уже почти получил — осталось выкинуть лишние слагаемые,
>> которые возникают при определенном раскладе. Хотя, просто так, ради
>> интереса можно посидеть дальше, что-то мне эта задача (полной
>> минимизации) понравилась
>>
S>Я сейчас уже конечно не очень хорошо эту тему помню, но для машинной минимизации есть метод Квайна-Максласски (вроде так) и вроде ещё какой-то!!! Так же есть ещё поиск тупиковых форм — всё это мы использовали в своей проге, так что советую найти описание сего детища!!!

Да, есть... Есть еще метод импликантных таблиц и алгоритм Петрика, а еще метод максимальных граней единичного n-мерного куба (где n — число переменных функции)...

Но ура, я полностью сделал задачу через карту Карно (как и просили) — так что еще раз всем спасибо!

Здравствуйте, Stanky, Вы писали:

>> К моему великому щастью я узнал, что мне нужна именно минимальная ДНФ
>> Ее я уже почти получил — осталось выкинуть лишние слагаемые,
>> которые возникают при определенном раскладе. Хотя, просто так, ради
>> интереса можно посидеть дальше, что-то мне эта задача (полной
>> минимизации) понравилась
>>
S>Я сейчас уже конечно не очень хорошо эту тему помню, но для машинной минимизации есть метод Квайна-Максласски (вроде так) и вроде ещё какой-то!!! Так же есть ещё поиск тупиковых форм — всё это мы использовали в своей проге, так что советую найти описание сего детища!!!

Есть еще Алгоритм Рота...По сути полностью формализованный алгоритм Квайна.

Здравствуйте, Reunion, Вы писали:


R>Но ура, я полностью сделал задачу через карту Карно (как и просили) — так что еще раз всем спасибо!

И каков же вариант решения? Перебор?

Здравствуйте, Dr.Gigabit, Вы писали:

DG>Здравствуйте, Reunion, Вы писали:


R>>Но ура, я полностью сделал задачу через карту Карно (как и просили) — так что еще раз всем спасибо!

DG>И каков же вариант решения? Перебор?

Сначала находим все подходящие прямоугольники для каждой ячейки. Затем сортируем их по убыванию размера. А потом выкидываем ненужные. Алгоритм не самый быстрый, но: во-первых на мой взгляд это не тот случай, когда надо оптимизировать (карта Карно обычно небольшая, в моем случае — вообще 4х4, да и на более больших работает в момент), а во-вторых это просто реализовать. Получается 100% результат для минимальной ДНФ. В принципе, я думаю, можно найти еще минимальную RYA и определить, что лучше. Вот такой вот алгоритм.

> Сначала находим все подходящие прямоугольники для каждой ячейки. Затем
> сортируем их по убыванию размера. А потом выкидываем ненужные. Алгоритм
> не самый быстрый, но: во-первых на мой взгляд это не тот случай, когда
> надо оптимизировать (карта Карно обычно небольшая, в моем случае -
> вообще 4х4, да и на более больших работает в момент), а во-вторых это
> просто реализовать. Получается 100% результат для минимальной ДНФ. В
> принципе, я думаю, можно найти еще минимальную RYA и определить, что
> лучше. Вот такой вот алгоритм.
>
А недетерминированные функции учитываешь?