Some Heuristic Analysis of Local Search Algorithms for SAT Problems
- 605 Downloads
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.
Unable to display preview. Download preview PDF.
- [Betal03]Barthel, W., Hartmann, A., Weigt, M.: Solving satisfiability by fluctuations: The dynamics of stochastic local search algorithms. Physical Review E 67(066104) (2003)Google Scholar
- [SAT00]Special Issue “SAT-2000”. J. of Automated Reasoning 24(1-2) (2000)Google Scholar
- [SM03]Semerjian, G., Monasson, R.: Relaxation and metastability in a local search procedure for the random satisfiability problem. Physical Review E 67(066103) (2003)Google Scholar
- [Wat05]Watanabe, O.: Pseudo expectation: A tool for analyzing local search algorithms, Progress of Theoret. Physics Supplement 157, 338–344 (2005) (A detail version is available: Research Report C-198, Dept. of Mathematical and Comput. Sci., Tokyo Inst. of Tech.)Google Scholar