实验6 A最佳优先搜索算法教程.doc

实验6 A*最佳优先搜索算法一 实验原理最佳优先的一个重要原理就是根据评价函数的计算结果总是选择代价最小的那条路径向下搜索。在搜索过程中通过不断地放弃代价较大的路径，从而最终找到代价最小的问题求解答案。二 实验目的掌握宽度搜索算法及A*最佳优先搜索算法。三 实验内容与结果运用所学知识，设计并编程实现对树的宽度搜索及A*最佳优先索算法。（见后面作业题目，将实验结果同时保存在电子版中）。四 实验总结61 广度（宽度）搜索上一章介绍了深度搜索，现在我们来介绍广度搜索。为了使你对这两种搜索方式有一个较深刻的了解，再次将它们做个比较。使用下面的树来说明这两种搜索方式。节点a是搜索的起点，而节点i是搜索的目标。先来看看深度搜索。深度搜索的搜索路径如下：a-ba-b-ea-ca-c-fa-c-ga-d-i最后找到了节点i。它先找出与a相连的某个节点b，发现b下面还有节点e，由于是深度搜索，所以它就会访问节点e，此时发现e下面没有其它的节点了，于是就返回到节点b，同样b下面也没有其它的节点，于是就返回到节点a，节点a还有子节点c，所以就开始访问节点c，如此下去，直到找到节点i。而广度（宽度）搜索的路径如下：a-ba-ca-da-b-ea-c-fa-c-ga-d-i这种搜索方式先考察a的所有子节点b、c和d，当它没有发现目标时就再考虑这些子节点的子节点，直到找到目标。这也是它取名为广度搜索的原因。宽（广）度搜索的Prolog程序与深度搜索一样简单：源程序备注说明：append/3谓词的作用是把两个表合成为一个表。上面的route/3使用广度搜索来找出答案。不难看出广度搜索与深度搜索的区别就是：广度搜索是递归在前，而深度搜索是递归在后。其实从逻辑上理解上面的route/3的编写方法是不难的，不过许多人都不会满足于这种逻辑上的理解，而希望能够了解程序的运行流程。首先，我们调用的目标与第二个route子句匹配，而此子句的头一个子目标就是它本身，所以又与route的第一个子句匹配。于是我们的程序就变成了如下的样子。route(Links,Current,Des):- route(,Current,Current), sub(Current,Des), append(PreLinks,Next,Links). 很清楚这段程序判断从Current到Des有没有直接的通路。当找不到时，它就回溯到route目标，这次它与第二条route子句匹配，而第二条子句又马上递归调用它本身，所以再次与第一条子句匹配。这是程序变成了如下的样子：route(Links,Current,Des):- route(,Current,Current), （1）sub(Current,Next), （2）append, （3）sub(Next,Des), append.前面的1、2、3个子句是把第一个route目标展开的结果。很容易看出来，此程序考虑了深度为2的节点。如果还没有发现目标，它又会递归调用来寻找深度为3的节点。每次展开后的程序大致如下：sub(Current,X1), sub(X1,X2),. sub(Xn-1,Xn), sub(Xn,Des). 于是此程序能够完成广度搜索。当然这种搜索的工作量是巨大的，并且程序的运行流程也很复杂，幸好这些工作都由Prolog完成了，我们所要做的就是使用这些搜索方法来解决一些实际的问题。测试用例及结果62 最佳优先搜索 最佳优先搜索可以看成是对宽度优先搜索的一种改进。与宽度优先一样，最佳优先也总是保留一组继续向下搜索的可选择路径。除此以外，最佳优先的一个重要原理就是根据评价函数的计算结果总是选择代价最小的那条路径向下搜索。在搜索过程中通过不断地放弃代价较大的路径，从而最终找到代价最小的问题求解答案。最佳优先搜索要求给出由一个状态前进到下一个状态所付出的代价。这在一般的问题求解中都是事先确定了的。例如，两个城市之间的距离就可以看成是求解此两个城市之间运输路线问题的代价。 最佳优先搜索的核心问题是如何构造估算路径成本的评价函数。这里，将介绍一种简单的评价函数构造方法。 假如n是由起点s到目标状态t的最佳路径上的某一个节点。用f(n)来表示对这条最佳路径的成本计算。f(n)定义为：f(n)=g(n)+h(n)其中g(n)为由起点s到n的各部代价之和，h(n)为由n到终点t的代价估算。在求解过程中当搜索到n时，g(n)是已知的它是由s到n的各步代价的总和。然而如何确定h(n),却不是件容易的事，因为由n到g是一个未知的世界。这里，无法给出一个通用的求解方法。它只能根据所求解问题的性质，或是人们所积累的经验来决定。因此，只能针对特定的问题加以解决。为了不影响进一步的讨论，不妨假设已知这个函数。 对宽度优先搜索进行如下的改进就成了最佳优先搜索。 全部的搜索过程由一组互相竞争的子过程构成，每一个子过程负责一种搜索选择，即负责搜索属于自身的那棵子树。而且这些子过程又由它自己的子过程构成，如此等等。在所有这些子过程中，只有到目前为止具有最低值的那个子过程是活动的。其他子过程则处于一种等待状态。当搜索过程沿着唯一活动的子过程继续时，就会增大活动子过程的值，从而可能使其他子过程成为到目前为止具有最低值的子过程。这使这个新的具有最低值的子过程成为活动的，于是搜索又由这一新的活动子过程向下继续进行。不妨对上述搜索过程作如下想象：一群互相竞争的搜索子过程按照他们的值由小到大排队。其中，位于队首的子过程由于具有最低的值而获得向下搜索的权利。这个活动的子过程实时地受到其他的竞争对手的威胁，在向下搜索的过程中除非搜索到了目标状态，否则它每前进一步都要报告它所获得的新的值。一旦这个新的值超过了它的下一个竞争对手，则他必须把向下搜索的权利让给这个竞争对手，而自己则根据新的值回到队列中恰当的位置上等待下一次机会。不难看出，竞争对手的f值是对活动的搜索子过程的一种限制，它时刻提醒活动过程在向下搜索时不得超过由竞争对手时确定的界限。 根据上面的叙述不难看出，深度搜索和广度搜索都是这种搜索方式的特例。对于深度搜索，深度越深优先权越大，而对于广度搜索，深度越深，优先权越小。 图1 A*算法流程图作业：1 请编写下面相应树的宽度搜索源程序，并给出至少两个测试用例及结果图