A Prolog Technique of Implementing Search of A/O Graphs with Constraints

Abstract

Our research has been motivated by the task of forming a solution subgraph which satisifies 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.