A Hybrid Search Algorithm for Solving Constraint Satisfaction Problems

Authors: Abdel-Reza Hatamlou, Mohammad Reza Meybodi

Abstract:

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.

Keywords: Constraint Satisfaction Problem, Hybrid SearchAlgorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1056264

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.