例子演示
设一个搜索过程已经生成了—个搜索图G如图2．9(a)所示。图中用箭头表示指针，用空心圆圈表示在OPEN表中的结点，用实心圆圈表示在cLOSED表中的结点。为简单起见，我们设每段弧的耗散值为1，则可以计算出从初始结点到每个结点的路径的耗散值，用括号中的数字标于该结点的旁边。现在我们扩展结点1，设它只有一个后继结点，即结点2。由于结点2已被扩展过，因此该结点已在cLOSED表中，在算法的第7步中，结点2满足第2和第3个条件。对于第2条，我们应当决定是否改变结点2的指针。由于根据原来的路径(经由结点3)计算出的耗散值为4，而新路径(经由结点1)的耗散值仅为2，因此采用新路径，把结点2的指针改为指向结点1，如图2．9(b)所示。对于第7步的第3条，由于结点2已在cLOSED表中，它还有2个后继结点，即结点4和结点5，应当决定它的后继结点是否应改变指针。由于从初始结点s到结点4已有两条路径，一条经由结点3，一条经由结点6。结点4原来的指针指向结点6，耗散值为4。现在从初始结点s到结点4又增加了一条经过结点1的路径，其耗散值为3，故应将结点4的指针改变为指向结点2。这个例子说明了过程的第7步对指针进行调整的理由。