Experimental study of hybrid-type distributed maximal constraint satisfaction algorithm
Masato Noto, Masahito Kurihara · 2006
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. KEY WORDS distributed constraint satisfaction problem, hybrid algo-rithm, synchronous branch and bound, iterative distributed breakout, graph-coloring problem 1