A New Approach for Heterogeneous Hybridization ofConstraint Satisfaction Search Algorithms

May 2004

Proceedings of the Seventeenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2004)

Volume

Proceedings of the Seventeenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2004)

All Papers

In the recent years, CSP’s have come to be seen as the core problem in many applications. We propose here a hybrid algorithm (MC-FC) that combines two different search methods, where a problem is solved partially with a random answer using Min-conflict algorithm (MC) and then the partial solution guides the systematic search algorithm (Forward-checking, FC) to solve the remainder of the problem. The specific problems used for this study are primarily the graph coloring problems with various degree of connectivity. The time complexity of the MC-FC is much better than the pure MC and FC under many circumstances. Furthermore, its time-complexity is more predictable over multiple experiments compared to that of the pure MC or FC, and the former algorithm uses less storage than the pure algorithms. We attempt to motivate our heterogeneous hybridization technique with some preliminary experiments and simple manual calculations.