A Hybrid Search Algorithm for Solving Constraint Satisfaction Problems

In this paper we present a hybrid search algorithm for solving constraint satisfaction and optimization problems. This algorithm combines ideas of two basic approaches: complete and incomplete algorithms which also known as systematic search and local search algorithms. Different characteristics of systematic search and local search methods are complementary. Therefore we have tried to get the advantages of both approaches in the presented algorithm. The major advantage of presented algorithm is finding partial sound solution for complicated problems which their complete solution could not be found in a reasonable time. This algorithm results are compared with other algorithms using the well known n-queens problem.

Authors:

• Abdel-Reza Hatamlou
• Mohammad Reza Meybodi

Keywords:

• Constraint Satisfaction Problem
• Hybrid SearchAlgorithm.

References:

[1] Narendra Jussien and Olivier Lhomme. Local search with constraint
propagation and conflict-based heuristics. Artificial Intelligence,
139(1):21-45, 2002.
[2] Vipin Kumar. Algorithms for constraint satisfaction problems: A survey.
AI Magazine, 13(1):32-44, 1992.
[3] K. Marriot, P. J. Stuckey. Programming with Constraints: An
Introduction. The MIT Press, 1998.
[4] Z. Michalewicz and D. B. Fogel. How to Solve It: Modern Heuristics.
Springer-Verlag, 2000.
[5] W. Ruml. Incomplete tree search using adaptive probing. In Proceedings
of the 17th International Joint Conference on Artificial
Intelligence (IJCAI-01), 2001.
[6] Andrea Schaerf. Combining local search and look-ahead for scheduling
and constraint satisfaction problems. In Proceedings of 15th
International Joint Conference on Artificial Intelligence (IJCAI-97),
pages 1254-1259, Nagoya, Japan, 1997.
[7] E. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.
[8] Stefan Voß. Meta-heuristics: State of the art. In Alexander Nareyek,
editor, Lcal search for planning and scheduling: revisited papers, pages
1-23. Springer-Verlag LNCS 2148, 2001.