《答深度优先搜索算法的特点是》由会员分享，可在线阅读，更多相关《答深度优先搜索算法的特点是（8页珍藏版）》请在金锄头文库上搜索。
1、习题31、答：深度优先搜索算法的特点是 一般不能保证找到最优解； 当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制; 方法与冋题无关，具有通用性； 属于图搜索方法。宽度优先搜索算法的特点是 当问题有解时，一定能找到解； 当问题为单位耗散值，并且问题有解时，一定能找到最优解； 效率低； 方法与问题无关，具有通用性； 属于图搜索方法。2、答：在决定生成子状态的最优次序时，应该采用深度进行衡量，使深度大的 结点优先扩展。3、答：(1)深度优先(2) 深度优先(3) 宽度优先(4) 宽度优先(5) 宽度优先4、答：如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那 么给以后放皇
2、后留下的余地就大，找到解的可能性也大；反之留下的余地就 小,找到解的可能性也小。并不是任何启发函数对搜索都是有用的。6讨论一个启发函数h在搜索期间可以得到改善的几种方法。7、答：最短路径为ACEBDA，其耗散值为15。8、解：(1) (S，O, So, G)S： 3个黑色板和3个白色板在7个空格中的任何一种布局都是一个 状态。O:一块板移入相邻的空格； 一块板相隔1块其他的板跳入空格； 一块板相隔2块其他的板跳入空格。So：WWWBBBWWWBBBWWWBBBWW WBBB7一P77龙6龙5疋4疋3工2 X1(2) 3140P3 -P33X2X1X3X2X1(3) 定义启发函数h为每一白色板左
3、边的黑色板数的和。显然，h(n) _ h ( n)，所以该算法具有可采纳性。又，h(nj) -h(ni“c(ni，nj)，所以该启发函数h满足单调限制条件h(t)=O9、解:(),(),( ),(),(1:)(S,(+),( ),(),(1)(A,(+),( ),(),()(A,SV),(),(),()(A,A)，()，()，()(A),(),(1),()(S,(T)，(1),()(A,(),),()(A,S,(),()(A,A.(),()(A,(),()(A,(S,()J(A,(A,()(A,(A,S)J(A,(A,A)(A,(A)J(A,S)J(A,A)(A)JS10、选择一个你熟悉的领域，设计一个状态搜索系统。11、解：从结点n到目的结点集合N的解图G递归定义为 如果n是N的一个元素，则G由单个结点组成； 如果n有一个扩展出结点n 1,n2,nk的K-连接符，使得从每一个 ni(i=1,2,k)到N有一解图，则G由结点n、K-连接符和n,nk中的每 个结点到N的解图所组成； 否则，n到N不存在解图。如果n=s，贝吐匕解图即为所求解问题的解图。AO*算法由两个过程组成 图生成过程，即扩展结点； 计算耗散值的过程。#1 1_ 2510、#12、解:(8)(8)(9)(9)#(9)(10)(10)#
