您的当前位置是：第三章 确定性推理>>学习内容>>知识点一

2．算法说明

①上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索策略的主要区别在于对OPEN表中节点的排列顺序不同。例如，宽度优先搜索把先生成的子节点排在后面，而深度优先搜索则把后生成的子节点排在前面。

②对节点n扩展后，生成并记入M的子节点有以下三种情况：

ⅰ 该子节点来从未被任何节点生成过，由n第一次生成；

ⅱ 该子节点原来被其他节点生成过，但还没有被扩展，这一次又被n再次生成；

ⅲ 该子节点原来被其他节点生成过，并且已经被扩展过，这一次又被n再次生成。

上三种情况是对一般图搜索算法而言。对于状态空间是树状结构不会出现后两种情况，这是因为每个节点经扩展后生成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。

在第⑦步针对M中子节点的不同情况进行处理时，如果发生当第ⅱ种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点？

一般是由起始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。起始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。

如果发生第ⅲ种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也是由起始节点到该节点的路径上的代价。

③在搜索图中，除起始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。

图搜索过程的第⑧步对OPEN表上的节点进行排序，以便能够从中选出一个“最好”的节点作为第④步扩展用。这种排序可以是任意的即盲目的（属于盲目搜索），也可以用以后要讨论的各种启发思想或其它准则为依据（属于启发式搜索）。

④在搜索过程的第⑤步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第⑦步所形成的指向父节点的指针来确定。

⑤如果搜索过程终止在第③步，即没有达到目标，且Open表中已无可供扩展的节点，则失败结束。

1  2