A dynamic constraint-directed ordered search algorithm for solving constraint satisfaction problems
Wesley W. Chu, Patrick H. Ngai · 1988
Many engineering problems such as Job Shop Scheduling can be categorized as constraint satisfaction problems. We propose the Dynamic Constraint-directed Ordered Search (DCOS) to solve such problems. DCOS repeatedly re-arranges the search order of the variables and eliminates its local inconsistencies by using a low order network consistency algorithm. As a result, it reduces the width of the search tree. The reduction of the width of the search tree causes the decrease in the number of backtrackings required to find the solution. We have applied DCOS to the Graph Coloring Problem and the Zebra Problem with a second order network consistency algorithm and obtained almost-backtrack-free searches for both cases.