实验5树的深度搜索

1、实验5树的深度搜索一实验原理1、定义在此搜索中，首先扩展最新产生的（即最深的）节点。深度相等的节点可以任 意排列。这种盲目（无信息）搜索叫做深度优先搜索（depth-first search）。2、特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始 节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替 代的路径。3、深度界限为了避免考虑太长的路径（防止搜索过程沿着无益的路径扩展下去），往往给 出一个节点扩展的最大深度橐深度界限。任何节点如果达到了深度界限，那么都 将把它们作为没有后继节点处理。二实验目的掌握有关树的深度优先搜索和图的搜索算法三实验内容与结果

2、 四实验心得5.1树的深度搜索深度搜索在人工智能领域，经常使用到搜索技术。常见的搜索方式有深度优先搜索与宽度 优先搜索两种。问题：树的搜索树在计算机科学领域是一种数据结构的概念。例如下图就表示一棵树：树中的字母表示树的节点，节点a叫做树的根，节点b、c、d叫做节点a的子节 点。b、c、d又分别有它们的子节点。树的搜索的意思就是要找到一条连接两个 节点的路径，例如连接节点a与g的路径是a-c-g。上面的例子是显而易见的，不过要想让计算机也能够找到这条路径，就必须编程 解决。下面介绍它的Prolog程序的编法。树的表达 首先我们需要把上面的树翻译为Prolog的语言，这不难办到，只要使用事实就可以

3、轻易地搞定：FILE18.PRO15:1InsertIndentsub(a,b). sub(a,c). sub (a, d). sub (b, e). sub(c,f). sub (c, g). sub(d,i). sub (d,h).上面的每一条事实对应树中的一条树枝。树的搜索先给出搜索程序：(事实框中输入)route(X,X,).route(X,Y,L):-sub (X, Z) , 4首先找到工的一个子节点码route (Z,Y,L1),板在寻找从Z到目的节点Y的路由L1,L = Z| L1.专最终的路由表为Z加上L1.树的深度搜索完整源程序:测试用例及结果(目标框中输入): route(

4、a,f,L).L = c,f;1 Solution route(a,h,L)L= d,h1 Solution我们可以看出，上面的route/3是使用递归的方法书写的。前两个参数为要 考虑的节点，第三个参数储存找出来的路由表。route的第一个子句为边界条件； 第二个子句递归调用route/3本身。在这个程序中，当找到X的一个子节点后，系统就开始寻找这个子节点的子 节点，一直到找到目标，搜索就成功地结束，而如果某个节点没有子节点，就会 引起回溯，去寻找它的父节点的另一个子节点。这种搜索方式就叫做深度优先搜 索。由于Prolog内建的自动回溯功能，使得我们可以非常容易地实现深度搜索。 所以在一般情

5、况下，通常使用深度搜索，而只在特殊的情况下才使用宽度搜索。5.2图的搜索-树的搜索拓展有向图如果在前面的事实中增加一条sub(d,g)，那么g既是d的子节点，又是c 得子节点。我们把这样的树叫做有向图。有向图的搜索与树的搜索过程是相同的。图的搜索图是最复杂的数据结构了。在图中不分什么父节点与子节点，每个节点都与 一定数量的其它节点相连，一条连接叫做一条路经。每条路径都有不同的权值， 从某个节点到另外的节点所走过的路径就叫做这两个节点之间的通路。图的搜索 的目的就是要找出这些通路，有时还需要所有的权值加起来最小(后面实验将会 涉及)。图的最典型的例子就是地理上的地图了，每个城市相当于一个节点，城

6、 市之间的道路就是路径了。搜索工作就是一个旅游向导，它能够帮助你决定到达 另外一个城市所需的路径。图的搜索和树的搜索是类似的，不过由于图中存在着环路，所以如果不加以 控制，而直接使用前面的程序就会导致永远不会结束。（此处及以下的解决搜索 主要是针对无向图解决环路的办法也很简单：使用一个列表储存已经考虑过的节点，如果正在 考虑的节点已经在此列表中就表明没有必要再搜索此节点了。卜面是完整的Prolog程序。上图为源程序及程序注解说明。源程序备注说明：谓词c/2定义了图的信息，你也可以自己根据事实给出的信息在纸上画画此有向 图。findroad/4findroad/4为寻找路由的谓词，它的调用方式为

7、findroad(a,e,X)。findroad(X,X,L,L).第一个子句定义了边界条件，它用来把第三个参数传给第四个参数，第 三个参数为临时的路由表，第四个参数为最终的路由表。findroad(X,Y,L,L1)：- % L 为储存的路由表。connect(X,Z),not(member(Z,L),% X所连接的节点Z不在已经储存的路由表中。findroad(Z,Y,Z|L,L1).第二个子句先找出与X相连的节点Z，然后判断Z是否在临时的路由表 中，如果不在，就把Z加入到临时路由表中，并且寻找从Z到Y的路由。下面是运行结果：findroad(a,e,L),write(L),nl,fail

8、e,be,f,b e,b,ce,b,a,ce,f,b,a,ce,b,d,a,ce,f,b,d,a,ce,b,a,de,f,b,a,de,b,c,a,de,f,b,c,a,de,b,de,f,b,dNo solutionsfindroad(a,f, 口，L),write(L),nl,failf,e,bf,bf,e,b,cf,b,cf,e,b,a,cf,b,a,cf,e,b,d,a,cf,b,d,a,cf,e,b,a,df,b,a,df,e,b,c,a,df,b,c,a,df,e,b,df,b,dNo solutions 对于结果正确与否，同学们可以通过参照下图自己来验证。这里有两点需要说明:第一，我们找出来的路由表是倒过来的，不过这并不影响结果；第二，这个程序找出了所有的通路，但是并不能判断哪条通路是最短通路，另 外我们还没有加入路径的权值。作业要求：实验结果均要求保存在