EXPERIMENTS WITH GRAPH TRAVERSER PROGRAM
EXPERIMENTS WITH GRAPH TRAVERSER PROGRAM
复制标题
DOI：
10.1098/rspa.1966.0205
复制
发表时间：
1966-01-01
影响因子：
--
通讯作者：
MICHIE, D
中科院分区：
文献类型：
--
作者：
DORAN, JE;MICHIE, D
描述了一类问题的自动求解方法。要属于这一类，一个问题必须用图论的语言表示为寻找指定图的两个指定节点之间的路径的问题。该方法依赖于根据问题的中间状态与目标状态的共同特征的程度来评估问题的中间状态。我们定义了评估函数，每个评估函数都为问题的任何状态分配一个值，该值在某种程度上与它与目标状态的“距离”有关。等价地，我们将与图上到目标节点的距离相关的值分配给相应图的节点。距离被认为是连接两个节点所需的最小弧数。已编写了ALGOL程序Graph Traverser以在此上下文中运行。它是以一种完全通用的方式设计的，并且有两个空的过程，其中一个必须编写以指定图的结构，即问题的约束，另一个用于定义评估函数。给程序提供了各种滑块谜题的定义，以及一个简单的代数处理问题，对于一系列的评估函数，所获得的结果是。
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.