Experimental Study of Hybrid-Type Distributed Maximal Constraint Satisfaction Algorithm

M. Noto and M. Kurihara (Japan)


distributed constraint satisfaction problem, hybrid algo rithm, synchronous branch and bound, iterative distributed breakout, graph-coloring problem


A constraint satisfaction problem (CSP) is a general frame work that can formalize various application problems in artificial intelligence. However, practical real-world prob lems tend to be over-constrained, and the descriptive power of the CSP is not always sufficient in formulating the prob lems because of various constraints involved. In this pa per, we will focus on an important subclass of distributed partial CSPs called the distributed maximal CSPs that can be applied to more practical kinds of problems. Specifi cally, we propose a hybrid-type algorithm of solving dis tributed maximal CSPs using a combination of approxi mate and exact algorithms that yields faster optimum so lutions than conventional methods. Experimental results are presented that demonstrate the effectiveness of the pro posed approach.

Important Links:

Go Back