1.何谓图搜索
    图搜索策略可看作一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的数据库。求得把一个数据库变换为另一数据库的规则序列问题就等价于求得图中的一条路径问题。

2.图搜索算法中的几个重要名词术语
    (1) OPEN表与CLOSE表
    (2) 搜索图与搜索树

3.图搜索(GRAPHSEARCH)的一般过程
    (1) 建立一个只含有起始节点S的搜索图G,把S放到一个叫做OPEN的未扩展节点表中。
    (2) 建立一个叫做CLOSED的已扩展节点表,其初始为空表。
    (3) LOOP:若OPEN表是空表,则失败退出。
    (4) 选择OPEN表上的第一个节点,把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。
    (5) 若n为一目标节点,则有解并成功退出,此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。
    (6) 扩展节点n,同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。
    (7) 对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员,确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员,确定是否需要更改图G中通向它的每个后裔节点的指针方向。 自动控制网www.eadianqi.com版权所有
    (8) 按某一任意方式或按某个探试值,重排OPEN表。
    (9) GO LOOP。

自动控制网www.eadianqi.com版权所有

4.图搜索方法分析
    图搜索过程的第8步对OPEN表上的节点进行排序,以便能够从中选出一个“最好”的节点作为第4步扩展用。这种排序可以是任意的(盲目搜索),也可以启发思想或其它准则为依据(启发式搜索)。搜索过程在找到目标节点时成功结束,这时,通过第7步设置的指针从目标节点向S回溯。当图中不再有未被扩展的非端节点时,搜索过程就以失败告终,在此情况下,问题无解。