| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Система нелинейных булевых уравнений с заданным ко |
| Автор: dengalf 8.9.2009, 03:20 |
| Необходимо сгенерировать случайную систему нелинейных булевых уравнений от n переменных (n>50), которая имела бы единственное или некоторое фиксированное количество (2, 3,..., m) известных решений. Хотя бы в общих чертах опишите, как это можно сделать. Перебор исключаем |
| Автор: nworm 8.9.2009, 13:36 |
| Очень просто. пишем x1x2=0 x2x3=1 x3x4=0 ... и т.д. единственное решение x1=0 x2=1 x3=1 x4=0 ... |
| Автор: dengalf 9.9.2009, 08:42 |
| Во-первых, как таком подходе создать систему, имеющую, например 2 решения. Во-вторых, решение задано изначально, например, не 0110, а 1111. В-третьих, системы, получаемые таким образом будут довольно однообразны, а необходимы как можно более случайные. То есть, к примеру на одно решение 10101010 в одном случае нужно 2 конъюнкции в первом уравнении, а в другом 100. С этим, понятное дело, можно будет бороться в процессе реализации, но все-таки... Есть идея изначально представлять систему в виде векторов 10011010 10110010 10100110 а затем как-то хитро переводить ее в другую форму Только дальше идеи как-то не двигается :( |
| Автор: nworm 9.9.2009, 11:34 |
| можно в форме ДНФ искать, тогда будет любое нужное число решений. |
| Автор: nworm 9.9.2009, 19:24 |
| Дело в том, что я всей задачи не знаю. Тут могут быть разные условия. Например, может быть так, вполне допускается решать одно уравнение или несколько. Тогда можно это одно или несколько уравнений сгенерировать так случайно как надо. Решить. Посчитать количество решений. А остальные уравнения подогнать, используя какую-нибудь простую схему. Или может быть эвристический поиск подойдёт. Одно сгенерировали, решили, посчитали количество решений, дальше строим следующее уравнение. Дальше решаем уже систему. Если решений стало меньше чем нужно, второе уравнение убираем. И так пока не будет ровно столько сколько нужно решений. Ещё вариант построить какую-то линейную систему с одним решением и начать её усложнять, внося нелинейность. Тут задача не поставлена до конца. Какие-то идеи я бросил, а так может быть и совсем подругому. |
| Автор: dengalf 12.9.2009, 09:35 |
| Я пытался построить в форме ДНФ примерно так: строим вектор со значениям x и f вначале одинаково по натуральному порядку(чтобы гарантированно получить разные значения функций, хотя натуральный порядок не принципиален): x1x2x3|f1 f2 f3 0 0 0 |0 0 0 | 0 0 1 |0 0 1 | 0 1 0 |0 1 0 | ... |... | 1 1 1 |1 1 1 | Затем случайно перемешиваем значения функций и выбираем "понравившееся решение" x1x2x3|f1 f2 f3 0 0 0 |0 0 1 | 0 0 1 |0 1 1 | 0 1 0 |0 0 0 | ... |... | 1 1 1 |1 0 1 | Заменяем еще несколько (сколько надо) значений функций на набор из нашего решения x1x2x3|f1 f2 f3 0 0 0 |0 0 1 | 0 0 1 |0 1 1 | 0 1 0 |0 0 0 | ... |... | 1 1 1 |0 1 1 | Строим ДНФ и как-нибудь малость минимизируем. Получаем примерно так: x1-x3 v x2x3 v -x1x2-x3=0 x1x2 v x1-x3 v x2-x3=1 -x1x3 v x2-x3=1 Только вышло довольно громоздко: время на генерацию зашкаливает, а генерация вектора с наборами x при n>24 вышибает программу... Можно ли как-то оптимизировать такой подход |
| Автор: nworm 12.9.2009, 15:12 |
| Да прям случайно выбираем решение. Например, выбралось 1010 и 0110. И пишем ответ: x1-x2x3-x4 v -x1x2x3-x4=1. Дальше можно заполнить систему мусором. Например, так, x1x2x3x4 = 0 x1-x2x3-x4 + x1x2x3x4= 1 -x1x2x3-x4 + 1 = 0 Ну и продолжать по каким-то алгоритмам до того пока не набирётся требуемое колличество конъюнкций. |
| Автор: dengalf 12.9.2009, 15:48 |
| Не факт, что если не придумать какой-то хитрый алгоритм отслеживания верных решений, что какое-то из них не просочиться. Забить мусором тоже не так-то просто - в конечном итоге получиться закономерность как у Вас - повторение определенных наборов (и последнее уравнение не верно на наборе 1, если, это конечно не случайность). Я сейчас использую довольно простую схему - создаю левую часть системы, вгоняю нужный набор, получаю правую часть и почти гарантированное получаю более одного решения. |
| Автор: nworm 12.9.2009, 16:38 |
| Да я там ошибся. Надо аккуратнее. x1x2x3x4 = 0 (x1-x2x3-x4 v -x1x2x3-x4) + x1x2x3x4= 1 (x1-x2x3-x4 v -x1x2x3(1-x4)) + 1 = 0 Вы просили оптимизировать. Схема с забиванием мусором не простая, зато очень быстрая. Используя всякие разные тождества можно получить сколь угодно длинные формулы. |
| Автор: dengalf 16.9.2009, 12:44 |
| "Небольшая" поправочка - вместо операции дизъюнкции в уравнениях берется сложение mod 2. Т.е. не х1х2 v x2x3, а х1х2 + x2x3. Итого используются только операции &, - и + |
| Автор: nworm 16.9.2009, 14:01 |
| для замусоривания это хорошо. будет не х1х2 v x2x3, а значительно длиннее х1х2 + x2x3 + (х1х2 & x2x3) поскольку x v y = x + y + xy но может у Вас там какая-то минимизация нужна (хотя и не полна, иначе бы Вы просто случайные решения выписывали.) а так да, задача не поставлена пока, нет математической постановки задачи. |
| Автор: dengalf 16.9.2009, 16:24 |
| Задача вкратце вот в чем - был написан алгоритм (генетический), который позволяет находить решения СНБУ. Алгоритм был опробован на различных системах и при определенных структурах решения и вида левой части системы позволяет находить ответ за полиномиальное время для систем до 60 переменных(дальше пока не вижу смысла двигаться, пока не решу проблему генератора). Но при определенных исходных алгоритм "встает"(например, не нравится ему почему-то решения, имеющие закономерности в последовательностях 0 и 1). Вот и хотелось бы создать генератор, позволяющий составлять системы 1 с определенным видом и количеством решений. 2 с определенным, так скажем, "состоянием линеаризации" уравнений 3 наличие минимальных функций в качестве уравнений и я думаю со временем еще чего-нибудь и уже затем производить оптимизацию, изучение, оценки и тп. Глобально задача стоит в экспериментальном рассмотрении свойств пространства, на котором ведется поиск решения, но это уже далеко "потом". В общем-то время терпит, никуда не тороплюсь, поэтому пока интересен пункт 1. Добавлено @ 16:25 Не от руки же их вбивать |
| Автор: nworm 18.9.2009, 00:44 |
| если генерирование - вспомогательная задача и есть проблема именно с конкретными решениями, то можно так как я предложил генерить, придумать несколько тождеств и случайно их выбирать для замусоривания хотя может кто-то что-нибудь поинтереснее предложит... |
| Автор: maxim1000 15.12.2009, 09:30 |
| Модератор: вопрос про решение системы выделен сюда: http://forum.vingrad.ru/forum/topic-283920.html |