A Prolog Technique of Implementing Search of A/O Graphs with Constraints.
Mária Bieliková, Pavol Návrat · 1997
. Our research has been motivated by the task of forming a solution subgraph which satisfies given constraints. The problem is represented by an A=O graph. Our approach is to apply a suitably modified technique of dependency-directed backtracking. We present our formulation of the standard chronological backtracking algorithm in Prolog. Based on it, we have developed an enhanced algorithm which makes use of special heuristic knowledge. It involves also the technique of node marking. We have gathered experience with the prototype Prolog implementation of the algorithm in applying it to (one step of) the problem of building a software configuration. Our experience shows that Prolog programming techniques offer a considerable flexibility in implementing the above outlined tasks. Keywords. A=O-graph, non-chronological backtrack, Prolog 1 PROBLEM AREA AND GOAL Many problems to which artificial intelligence techniques are often applied can be described as constraint satisfaction problems. We...