《答深度优先搜索算法的特点是》由会员分享,可在线阅读,更多相关《答深度优先搜索算法的特点是(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)#