答深度优先搜索算法的特点是
习 题 3
1、答:深度优先搜索算法的特点是
①一般不能保证找到最优解;
②当深度限制不合理时,可能找不到解,可以将算法改为可变深度限制; ③方法与问题无关,具有通用性;
④属于图搜索方法。
宽度优先搜索算法的特点是
①当问题有解时,一定能找到解;
②当问题为单位耗散值,并且问题有解时,一定能找到最优解;
③效率低;
④方法与问题无关,具有通用性;
⑤属于图搜索方法。
2、答:在决定生成子状态的最优次序时,应该采用深度进行衡量,使深度大的结点优先扩展。
3、答:(1)深度优先
(2)深度优先
(3)宽度优先
(4)宽度优先
(5)宽度优先
4、答:如果把一个皇后放在棋盘的某个位置后,它所影响的棋盘位置数少,那么给以后放皇后留下的余地就大,找到解的可能性也大;反之留下的余地就小,找到解的可能性也小。
并不是任何启发函数对搜索都是有用的。
6、讨论一个启发函数h在搜索期间可以得到改善的几种方法。
7、答:最短路径为ACEBDA, 其耗散值为15。
8、解:(1)(S,O,S0,G)
S:3个黑色板和3个白色板在7个空格中的任何一种布局都是一个
状态。
O:① 一块板移入相邻的空格;
② 一块板相隔1块其他的板跳入空格;
③ 一块板相隔2块其他的板跳入空格。
S0:
B B B W W W
G:
W W W B B B
W W W B B B
W W W B B B
W W W B B B
W W W B B B
W W W B B B
W W W B B B
(2)P7
373P3P37654321321321140
(3)定义启发函数h为每一白色板左边的黑色板数的和。 显然,h(n)h(n),所以该算法具有可采纳性。 又,
9、解:
((( ),( )),( ),(( ),( )))
((S,( )),( ),(( ),( )))
((A,( )),( ),(( ),( )))
((A,S),( ),(( ),( )))
((A,A),( ),(( ),( )))
((A),( ),(( ),( )))
(S,( ),(( ),( )))
(A,( ),(( ),( )))
(A,S,(( ),( )))
(A,A,(( ),( )))
(A,(( ),( )))
h(nj)h(ni)c(ni,nj)h(t)0,所以该启发函数h满足单调限制条件。
(A,(S,( ))) (A,(A,( )))
(A,(A,S))
(A,(A,A))
(A,(A))
(A,S)
(A,A)
(A)
S
10、选择一个你熟悉的领域,设计一个状态搜索系统。
11、解:从结点n到目的结点集合N的解图G′递归定义为
① 如果n是N的一个元素,则G′由单个结点组成; ② 如果n有一个扩展出结点{n1,n2,…,nk}的K-连接符,使得从每一个ni(i=1,2,…,k)到N有一解图,则G′由结点n、K-连接符和{n1,n2,…,nk}中的每个结点到N的解图所组成;
③ 否则,n 到N不存在解图。
如果n=s,则此解图即为所求解问题的解图。
AO*算法由两个过程组成
① 图生成过程,即扩展结点;
② 计算耗散值的过程。
2 3
(1)
3
(2)
2
(3)
2
(4)
2
2
12、解:
(1)
(2)
(3)
(4)
(5)
(6)
(7)