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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:51136", author = "Abdel-Reza Hatamlou and Mohammad Reza Meybodi", title = "A Hybrid Search Algorithm for Solving Constraint Satisfaction Problems", 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.", volume = "1", number = "10", pages = "2985-3", }