Backtracking deterministic annealing for constraint satisfaction problems
Heiko Wersing · 1999
We present a new deterministic annealing ap-proach to the solution of quadratic constraint satisfaction problems with complex interlock-ing constraints, such as exemplified in poly-omino tiling puzzles. We first analyze the dy-namical properties of the solution strategies im-plemented by deterministic annealing (DA) in the analog neural representation of Potts-Mean-Field (PMF) and penalty-function-based com-petitive layer model (CLM) neural networks, revealing a similar mechanism. The key idea of our extension of these plain DA approaches is motivated by classical backtracking algo-rithms. We show that their ability for iterative local pruning of the search space can be im-plemented within the framework of DA by in-troducing local temperature parameters which are “reheated ” when locally unresolved con-flicts occur. To achieve the pruning of the search space, reheating is accompanied by a modifi-cation of the constraint-implementing weight matrix to reduce the chance of reentering the same local configuration. The weight changes provide a learning mechanism that facilitates the generation of a solution for subsequent runs. We demonstrate the benefits of the result-ing “backtracking deterministic annealing ” al-gorithm (BDA) by applying it to a pentomino tiling problem. We show that the method re-liably finds perfect solutions to the task, while the plain DA approach for both PMF and CLM is unable to solve the task in a comparable or even considerably larger number of iterations. 1