WalkSAT - WalkSAT - Wikipedia
v počítačová věda, GSAT a WalkSAT jsou místní vyhledávání algoritmy vyřešit Booleovské problémy se uspokojivostí.
Oba algoritmy fungují vzorce v Logická logika které jsou v nebo byly převedeny na konjunktivní normální forma. Začínají přiřazením náhodné hodnoty každé proměnné ve vzorci. Pokud zadání splňuje všechny doložky, algoritmus se ukončí a vrátí přiřazení. Jinak se proměnná převrátí a výše se potom opakuje, dokud nejsou splněny všechny klauzule. WalkSAT a GSAT se liší metodami používanými k výběru proměnné, které se mají převrátit.
GSAT provede změnu, která minimalizuje počet neuspokojených klauzulí v novém přiřazení, nebo s určitou pravděpodobností náhodně vybere proměnnou.
WalkSAT nejprve vybere klauzuli, která není uspokojena aktuálním přiřazením, a poté v této klauzuli převrátí proměnnou. Klauzule je vybrána náhodně mezi neuspokojenými klauzulemi. Proměnná je vybrána, což povede k tomu, že nejméně dříve splněných klauzulí bude neuspokojeno, s určitou pravděpodobností náhodného výběru jedné z proměnných. Při náhodném výběru je WalkSAT zaručena alespoň šance jedné z počtu proměnných v klauzuli opravy aktuálně nesprávného přiřazení. Při výběru hádané proměnné, která má být optimální, musí WalkSAT provést méně výpočtů než GSAT, protože zvažuje méně možností.
Algoritmus se může restartovat s novým náhodným přiřazením, pokud nebylo příliš dlouho nalezeno žádné řešení, jako způsob, jak se dostat z místní minima počtu neuspokojených klauzulí.
Existuje mnoho verzí GSAT a WalkSAT. WalkSAT se osvědčil jako obzvláště užitečný při řešení problémů s uspokojivostí způsobených převodem z automatické plánování problémy. Přístup k plánování, který převádí problémy plánování na booleovské problémy s uspokojivostí, se nazývá satplan.
MaxWalkSAT je varianta WalkSAT určená k řešení vážený problém uspokojivosti, ve kterém je každá klauze spojena s váhou, a cílem je najít přiřazení - takové, které může nebo nemusí splňovat celý vzorec -, které maximalizuje celkovou váhu klauzulí splněných tímto přiřazením.
Reference
- Henry Kautz a B. Selman (1996). Posunutí obálky: plánování, výroková logika a stochastické hledání. v Sborník z třinácté národní konference o umělé inteligenci (AAAI'96), strany 1194–1201.
- Papadimitriou, Christos H. (1991), „O výběru uspokojivého zadání pravdy“, Sborník z 32. ročníku sympozia o základech informatiky, str. 163–169, doi:10.1109 / SFCS.1991.185365, ISBN 978-0-8186-2445-2.
- Schöning, U. (1999), „Pravděpodobnostní algoritmus pro k-SAT a problémy s uspokojením omezení ", Sborník ze 40. ročníku sympozia o základech informatiky, str. 410–414, CiteSeerX 10.1.1.132.6306, doi:10.1109 / SFFCS.1999.814612, ISBN 978-0-7695-0409-4.
- B. Selman a Henry Kautz (1993). Rozšíření GSAT nezávislé na doméně: Řešení velkých problémů se strukturovanou uspokojivostí. v Sborník ze třinácté mezinárodní společné konference o umělé inteligenci (IJCAI'93), strany 290–295.
- Bart Selman, Henry Kautz, a Bram Cohen. „Místní strategie vyhledávání pro testování uspokojivosti.“ Konečná verze se objeví v Cliques, Coloring a Satisfiability: Second DIMACS Implementation Challenge, 11. – 13. Října 1993. David S. Johnson a Michael A. Trick, eds. Řada DIMACS v diskrétní matematice a teoretické informatice, sv. 26, AMS, 1996.
- B. Selman, H. Levesque a D. Mitchell (1992). Nová metoda řešení problémů s tvrdou uspokojivostí. v Sborník příspěvků z desáté národní konference o umělé inteligenci (AAAI'92), strany 440–446.