Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Алгоритмы > Решение системы булевых уравнений

Автор: Zhenia87 15.12.2009, 00:55

а у меня вот другая проблема, мне нужен сам алгоритм для решения системы булевых уравнений. В интернете искал , но пока ничего не нашел. Думаю, что можно метод Гауса переделать для решения таких уравнений.

Автор: dengalf 15.12.2009, 07:22

Гаусс не пойдет:
Во-первых в силу особенностей булевых функций - шанс потерять решение гораздо выше чем на действительных числах, поэтому придется проверять половину всех решений(просто занулять ведь нельзя, а у нас всего 2 цифры а не 10), что фактически эквивалентно полному перебору
Во-вторых, возможно на небольших системах он и сработает, а вот при решении систем с количеством переменных >90 надолго заглохнет, проще перебор.
Если есть желание поразвлечься - попробуйте эволюционные исчисления(ГА, муравьи, если станет интересно - пишите, я сам этим плотно занимаюсь,поделимся результатами), либо поищите специфические алгоритмы(#метод линеаризующего множества, посмотрите жадные алгоритмы, хотя они, помнится, не очень хорошо здесь работают, уверен - что-нибудь еще есть)
При количестве переменных <50 - полный перебор(если эффективно реализовать и распараллелить можно и за сотню убежать, а может и больше)
Если надо - могу более конкретную задачку на эту тему подбросить smile

Автор: maxdiver 16.12.2009, 02:04

Если система линейная (а видимо такая и есть), то конечно Гаусса.

Работает он за O(n^3), а для булевых систем его можно реализовать с помощью битовых операций за порядка n^3 / 32 операций.

dengalf Что вы такое говорите, никакой потери точности не будет: если Гаусс применяем для решения булевых систем, то никакого типа данных, кроме булева (false/true) не потребуется, никакой потери точности. Во-вторых, асимптотика его n^3, и даже при простой реализации будет за секунду запросто решать системы с несколькими сотнями переменных. При хорошей реализации - с битовыми операциями, про что я упоминал, - будет вообще систему с 1000 переменными успевать за секунду решать.

Zhenia87 Могу помочь с реализацией на C++, на нём алгоритм даже за n^3 / 32 очень короткий и простой.

Автор: cardinal 16.12.2009, 02:09

Цитата(Zhenia87 @ 14.12.2009, 22:55

)

а у меня вот другая проблема, мне нужен сам алгоритм для решения системы булевых уравнений

А зачем интересно? smile

Автор: dengalf 16.12.2009, 04:50

Цитата

Если система линейная (а видимо такая и есть), то конечно Гаусса.

Если линейная - то действительно Гаусс, но в изначальной теме(откуда этот вопрос перенесли) речь шла именно о нелинейной

Цитата

Работает он за O(n^3)

Опять же для нелинейных оценка - экспонента. Есть конечно алгоритмы, которые подводят к полиномиальной(да и то, думаю с некоторыми ограничениями на условия), но это, как правило, за счет параллельной обработки. Или я не прав? Задача - NP-полная...

Цитата

Что вы такое говорите, никакой потери точности не будет

Речь не о потере точности(какую такую точность тут в принципе можно потерять?), а о эффективности алгоритма: на каждом шаге Гаусса придется проверять не равно ли x[i] нулю, а это как раз половина полного перебора.
Повторюсь, я имел ввиду именно нелинейные системы, как и было сформулировано изначально

Автор: Zhenia87 16.12.2009, 16:23

Цитата

А зачем интересно?

в дипломной работе при исправлении ошибок стирания в циклических кодах реализованных с помощью ЛПМ.

Цитата

Zhenia87 Могу помочь с реализацией на C++, на нём алгоритм даже за n^3 / 32 очень короткий и простой.

я буду реализовывать на С#, но думаю твой алгоритм на С++ очень поможет.
У меня нужно будет решать системы такого вида, причем сложе́ние по модулю 2 :
х1+х2+nx3=0
x3+nx1+x4=0
x2+x3=0

Автор: cardinal 16.12.2009, 20:45

Цитата(Zhenia87 @ 16.12.2009, 14:23

)

в дипломной работе при исправлении ошибок стирания в циклических кодах реализованных с помощью ЛПМ.

Ничего не понял. Ты должен научиться объяснять то, чем ты занимаешься людям, которые не в теме - иначе никто и не оценит...

Автор: Zhenia87 16.12.2009, 21:49

Цитата(cardinal @ 16.12.2009, 20:45)

Цитата(Zhenia87 @ 16.12.2009, 14:23

)

в дипломной работе при исправлении ошибок стирания в циклических кодах реализованных с помощью ЛПМ.

зачем людям знать все подробности моей дипломной работы, мне нужно только узнать какие есть алгоритмы решения систем булевых уравнений

Автор: cardinal 16.12.2009, 22:03

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

Автор: Zhenia87 16.12.2009, 22:16

Цитата(cardinal @ 16.12.2009, 22:03)

да я и не боюсь smile

просто долго объяснять всю суть. В моей дипломной работе я декодирую циклические коды, при этом могут возникнуть некоторые типы ошибок(пакеты ошибок, стирания, независимые инвертированные). Для декодирования я использую теорию логических последовательстных машин (ЛПМ). Так вот, при ошибках стирания на одном из этапов мне нужно решать системы булевых уравнений(вид которых я описал выше). Вот в чем моя проблема.

Автор: cardinal 16.12.2009, 23:07

что-то странное вообщем smile

Автор: maxdiver 19.12.2009, 14:33

Вот решение линейных систем за N^2 / 32:

Код


const int N = 100;

int n;
cin >> n;
vector < bitset<N> > a (n);
for (int i=0; i<n; ++i)
    for (int j=0; j<=n; ++j) {
        int cur;
        cin >> cur;
        if (cur)
            a[i].set (j);
    }

for (int i=0; i<n; ++i) {
    for (int j=i; j<n; ++j)
        if (a[j].test(i)) {
            swap (a[i], a[j]);
            break;
        }
    if (!a[i].test(i)) {
        cout << "Degenerated system!";
        return 0;
    }
    for (int j=0; j<n; ++j)
        if (j!=i && a[j].test(i))
            a[j] ^= a[i];
}

for (int i=0; i<n; ++i)
    cout << a[i].test(n) << endl;

Для плохо знающих C++: трюк в том, что булевый массив bitset<макс.размер> умеет ксориться с другим таким же за (макс.размер / число_бит_в_int) операций, т.е. обычно за N/32 операций. А это место и было самым узким в алгоритме.