Czy ktoś mógłby wskazać jedną lub więcej stron internetowych, z których można pobrać działającą implementację solvera #SAT? Interesują mnie osoby zwracające dokładną liczbę rozwiązań, a nie przybliżenie.
Czy ktoś mógłby wskazać jedną lub więcej stron internetowych, z których można pobrać działającą implementację solvera #SAT? Interesują mnie osoby zwracające dokładną liczbę rozwiązań, a nie przybliżenie.
Odpowiedzi:
Możesz to zrobić za pomocą SAT4J , po prostu iterując wszystkie modele: http://www.sat4j.org/howto.php#models . Wyobrażam sobie, że większość solverów SAT ma tę zdolność.
Możesz także wypróbować solver #SAT „sharpSAT” ( strona internetowa , github ) do zliczania liczby spełniających wymagania formuł CNF.
Jedną z opcji jest użycie biblioteki BDD, takiej jak JavaBDD . Wszystkie takie biblioteki mają albo funkcję, która szybko liczy rozwiązania, albo przynajmniej ułatwiają napisanie takiej funkcji. Wadą jest jednak to, że konstruowanie BDD będzie w wielu przypadkach powolne i może wymagać dużej ilości pamięci.
Temat pokrewny: Najlepszy SAT Solver .
Najlepsze, co znalazłem, to „kompilator c2d”. http://reasoning.cs.ucla.edu/c2d/
Używa d-DNNF i potrzebujesz opcji -count .
MBound Solver podany tutaj http://www.cs.cornell.edu/~sabhar/ może dawać liczby modeli z gwarancjami probabilistycznymi. Jest to znacznie szybsze niż wyliczenie wszystkich rozwiązań.
Napisałem mały model / główny wylicznik implikujący . Można to już wykorzystać do zliczania modeli z wyliczeniem modelu, ale nie jest to zbyt praktyczne. Jeśli ktoś jest zainteresowany, mogę go rozszerzyć, aby liczył modele z najlepszych implantów.
Witryna BeyondNP zawiera dobry spis istniejących narzędzi do rozwiązywania #SAT (i innych powiązanych trudnych problemów dotyczących formuł CNF). Możesz także znaleźć listę narzędzi do przybliżonego zliczania modeli i kompilacji wiedzy (zadanie przekształcenia CNF w miejmy nadzieję zwięzłą strukturę danych, która często obsługuje zliczanie wielomianowe modelu czasowego).
Możesz także znaleźć listę narzędzi do wstępnego przetwarzania formuł CNF, które mogą być przydatne do poprawy wydajności liczników modeli i różnych testów porównawczych .
Oto jeden o nazwie tensorCSP i oparty na narzędziu o nazwie sieci tensor. Wyjaśniono to w tym artykule .
Glukoza to bardzo wydajny solver SAT opracowany na uniwersytecie w Bordeaux.