Имам проблем, който е продължение на проблема с 2-SAT. В стандартния проблем 2-SAT можем да намерим всяко от заданията на истината, което зависи от подреждането на избраните от нас върхове. Искам да проверя дали съществува едно и само едно присвояване на истината (т.е. само една комбинация), за което изразът е удовлетворим. Броят на литералите може да бъде 100 000. Един от начините е да намерите всички възможни присвоявания на истината, след което да ги сравните, ако са различни. Но проблемът е, че за всяко сравнение ще трябва да сравня 100 000 стойности (без литерали). Има ли някакъв ефикасен начин?
2-Проблем с удовлетворимостта-Дали съществува уникално присвояване на истината или не
Отговори (1)
Feder (1994) описва алгоритъм за ефективно изброяване на всички решения на даден екземпляр с 2-задоволимост. В статията има и цитати за алгоритми за отчитане на броя на присвояванията, но трябва само да опитате да посочите две присвоявания, което може да е по-ефективно.
person
Martin Hock
schedule
03.11.2009
Благодаря ти много. Можете ли да ми предоставите линка за статията в pdf?
- person avd; 03.11.2009
Ето един за един от листовете за броене. cse.psu.edu/~kasivisw/2sat.pdf Уебсайтът на Томас Федер не съдържа връзка към документа от 1994 г.
- person Martin Hock; 03.11.2009
Само коментар: документът, до който ви изпратих, е за алгоритъм за експоненциално време. Тогава предполагам, че искате да използвате алгоритъма на Федер, който изглежда е полиномиално време. Можете да го закупите тук за $34 или можете да намерите копие на Algorithmica в местната научна библиотека. springerlink.com/content/j582276p06276l12
- person Martin Hock; 03.11.2009
Благодаря ви много за вашата помощ.
- person avd; 03.11.2009
