A New Approach for Heterogeneous Hybridization of Constraint Satisfaction Search Algorithms.
Debasis Mitra, Hyoung-Rae Kim · The Florida AI Research Society · 2004
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.