Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Some Heuristic Analysis of Local Search Algorithms for SAT Problems
verfasst von : Osamu Watanabe
Erschienen in: Stochastic Algorithms: Foundations and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
By using heuristic analysis proposed in [WSA03], we investigate the dynamical behavior of greedy local search algorithms for satisfiability (SAT) problems. We observe that the difference between hard and easy instances is relatively small while there are enough places to be improved locally, and that the difference becomes crucial when all such places are processed. We also show that a tabu search type restriction could be useful for improving the efficiency of greedy local search algorithms.