Вопросы реализации в проблеме 2-удовлетворенности
Я хочу реализовать задачу 2-SAT для 100000 литералов. Таким образом, было бы 200000 вершин. Так что я застрял на наличие массива всех достижимых вершин из каждой вершины, сложность пространства O(200000^2) что невозможно, поэтому, пожалуйста, предложите решение для этого. И, пожалуйста, пролите немного света на эффективную реализацию проблемы 2-SAT.
2 ответа
Из википедии:
... 2-выполнимость может быть решена за полиномиальное время. Как заметил Aspvall, Plass & Tarjan (1979), экземпляр 2-выполнимости разрешим в том и только в том случае, если каждая переменная экземпляра принадлежит другому сильно связному компоненту графа импликации, чем отрицание той же переменной. Поскольку сильно связанные компоненты могут быть найдены в линейное время с помощью алгоритма, основанного на глубинном поиске, такая же линейная временная граница применима также к 2-выполнимости.
Я не буду притворяться, что понимаю большую часть этого абзаца, но может показаться, что существует алгоритм, который можно использовать для решения проблемы 2-SAT, и он описан в этом ссылочном документе ( Алгоритм линейного времени для тестирования истинность некоторых количественных логических формул). По-видимому, его можно купить онлайн примерно за 20 долларов США. Я не уверен, полезно это или нет, но это так!
обновление: бесплатный PDF того же документа можно найти здесь. Кредит идет к liori за находку.
Вся эта тема немного запуталась. Да, можно решить 2-сел за линейное время, но нет - вы не можете решить это для такого количества переменных. Время для решения 2-sat является линейным по отношению к числу значений, которое для 200 000 переменных может достигать (200000*199999)/2, и, более того, если вы используете это решение, вам потребуется примерно такой же объем памяти, Есть другое решение (не использовать сильно подключенные компоненты, которые работают медленнее, но не требуют много памяти).