Experiments with the Graph Traverser program

Abstract

An automatic method is described for the solution of a certain family of problems. To belong to this family a problem must be expressible in the language of graph theory as that of finding a path between two specified nodes of a specified graph. The method depends upon the evaluation of intermediate states of the problem according to the extent to which they have features in common with the goal state. We define evaluation functions each of which assigns to any state of the problem a value which is in some way related to its 'distance' from the goal state. Equivalently we assign to nodes of the corresponding graph values which are related to the distance over the graph from the goal node. Distance is reckoned as the smallest number of arcs needed to connect two nodes. An Algol program, the Graph Traverser, has been written to operate in this context. It is designed in a completely general way, and has two 'empty' procedures one of which must be written to specify the structure of the graph, that is the constraints of the problem, and the other to define an evaluation function. Results obtained by supplying the program with definitions of various sliding block puzzles and also a simple problem of algebraic manipulation are reported for a range of evaluation functions.