实验6 a最佳优先搜索算法教程

《实验6 a最佳优先搜索算法教程》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验6A*最佳优先搜索算法一．实验原理最佳优先的一个重要原理就是根据评价函数的计算结果总是选择代价最小的那条路径向下搜索。在搜索过程中通过不断地放弃代价较大的路径，从而最终找到代价最小的问题求解答案。二．实验目的掌握宽度搜索算法及A*最佳优先搜索算法。三．实验内容与结果运用所学知识，设计并编程实现对树的宽度搜索及A*最佳优先索算法。（见后面作业题目，将实验结果同时保存在电子版中）。四．实验总结116．1广度（宽度）搜索上一章介绍了深度搜索，现在我们来介绍广度搜索。为了使你对这两种搜索方式有一个较深刻的了解，再次将它们做个比较。使用下面的树来说明这两种搜索方式。节点a是搜索的起点，而节点

2、i是搜索的目标。先来看看深度搜索。深度搜索的搜索路径如下：a-ba-b-ea-ca-c-fa-c-ga-d-i11最后找到了节点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，当它没有发现目标时就再考虑这些子节点的子节点，直到找到目标。这也是它取

3、名为广度搜索的原因。11宽（广）度搜索的Prolog程序与深度搜索一样简单：11源程序备注说明：append/3谓词的作用是把两个表合成为一个表。上面的route/3使用广度搜索来找出答案。不难看出广度搜索与深度搜索的区别就是：广度搜索是递归在前，而深度搜索是递归在后。其实从逻辑上理解上面的route/3的编写方法是不难的，不过许多人都不会满足于这种逻辑上的理解，而希望能够了解程序的运行流程。首先，我们调用的目标与第二个route子句匹配，而此子句的头一个子目标就是它本身，所以又与route的第一个子句匹配。于是我们的程序就变成了如下的样子。route(Links,Current,De

4、s):-route([],Current,Current),sub(Current,Des),append(PreLinks,[Next],Links).很清楚这段程序判断从Current到Des有没有直接的通路。当找不到时，它就回溯到route目标，这次它与第二条route子句匹配，而第二条子句又马上递归调用它本身，所以再次与第一条子句匹配。这是程序变成了如下的样子：route(Links,Current,Des):-11route([],Current,Current),（1）sub(Current,Next),（2）append,（3）sub(Next,Des),append.前

5、面的1、2、3个子句是把第一个route目标展开的结果。很容易看出来，此程序考虑了深度为2的节点。如果还没有发现目标，它又会递归调用来寻找深度为3的节点。每次展开后的程序大致如下：sub(Current,X1),sub(X1,X2),...sub(Xn-1,Xn),sub(Xn,Des).于是此程序能够完成广度搜索。当然这种搜索的工作量是巨大的，并且程序的运行流程也很复杂，幸好这些工作都由Prolog完成了，我们所要做的就是使用这些搜索方法来解决一些实际的问题。测试用例及结果116．2最佳优先搜索最佳优先搜索可以看成是对宽度优先搜索的一种改进。与宽度优先一样，最佳优先也总是保留一组继续

6、向下搜索的可选择路径。除此以外，最佳优先的一个重要原理就是根据评价函数的计算结果总是选择代价最小的那条路径向下搜索。在搜索过程中通过不断地放弃代价较大的路径，从而最终找到代价最小的问题求解答案。最佳优先搜索要求给出由一个状态前进到下一个状态所付出的代价。这在一般的问题求解中都是事先确定了的。例如，两个城市之间的距离就可以看成是求解此两个城市之间运输路线问题的代价。最佳优先搜索的核心问题是如何构造估算路径成本的评价函数。这里，将介绍一种简单的评价函数构造方法。假如n是由起点s到目标状态t的最佳路径上的某一个节点。用f(n)来表示对这条最佳路径的成本计算。f(n)定义为：f(n)=g(n)

7、+h(n)11其中g(n)为由起点s到n的各部代价之和，h(n)为由n到终点t的代价估算。在求解过程中当搜索到n时，g(n)是已知的——它是由s到n的各步代价的总和。然而如何确定h(n),却不是件容易的事，因为由n到g是一个未知的世界。这里，无法给出一个通用的求解方法。它只能根据所求解问题的性质，或是人们所积累的经验来决定。因此，只能针对特定的问题加以解决。为了不影响进一步的讨论，不妨假设已知这个函数。对宽度优先搜索进行如下的改进就成了最佳优先