zhuye

图搜索策略

图搜索策略把搜索过程中所有应用过的操作及其生成的状态描述用搜索图的形式记录下来。整个问题求解空间可以用初始状态和操作集合所决定的隐含图表示。因此，搜索过程就相当于在隐含图中寻找一条路径，这条路径从初始状态出发，到目标状态结束。下面先介绍图的基本概念，再介绍图搜索算法。

1、基本概念----图的说明

2、图搜索过程

过程GRAPHSEarcH是一个一般的图搜索算法，足以包括各种类型的图搜索策略。G是过程生成的搜索图，它是在第1步初始化，在第6步逐步生成的。OPEN表用来存储待扩展的节点，每次循环从OPEN表中取出一个结点加以扩展，并把新生成的结点加入OPEN表。第8步OPEN表的排序是决定搜索效率的关键，不同的排序方法对应着不同类型的图搜索算法。cLOSED表用来存贮已扩展的结点，它的用途是检查新生成的结点是否已被扩展过。第7步为每个新生成的结点设置一个指向其父结点的指针。由于每个结点只有—个指针，因此通过对指针树跟踪，可以决定从初始结点到任—结点的—条路径。根据所有结点的指针，可以生成一棵搜索树T。
这个程序给出了一条从初始状态到目标状态的路径，一个搜索图G和一个搜索树T。由于不同的结点可以扩展出相同的结点，因此G是图而不是树。但是，每个结点只有一个指向父绪点的指针，因此指针所决定的T是树。另外，由于第7步要根据路径的耗散值确定结点的指针，因此，G与T另外的一个区别是，搜索图G给出了从初始结点到任一结点所有可能的路径，而搜索树T给出了从初始结点到任一结点耗散值最小的路径。

另外，根据从初始结点到目标结点的路径的要求，搜索方式又可分为

任一路径的搜索最佳路径的搜索

请点击超链看详细介绍