2024年5月11日发(作者：电脑怎么重装系统win10专业版)
习 题 3
1、答：深度优先搜索算法的特点是
①一般不能保证找到最优解；
②当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制；
③方法与问题无关，具有通用性；
④属于图搜索方法。
宽度优先搜索算法的特点是
①当问题有解时，一定能找到解；
②当问题为单位耗散值，并且问题有解时，一定能找到最优解；
③效率低；
④方法与问题无关，具有通用性；
⑤属于图搜索方法。
2、答：在决定生成子状态的最优次序时，应该采用深度进行衡量，使深度大的
结点优先扩展。
3、答：（1）深度优先
（2）深度优先
（3）宽度优先
（4）宽度优先
（5）宽度优先
4、答：如果把一个皇后放在棋盘的某个位置后，它所影响的棋盘位置数少，那
么给以后放皇后留下的余地就大，找到解的可能性也大；反之留下的余地就
小，找到解的可能性也小。
并不是任何启发函数对搜索都是有用的。
6、讨论一个启发函数h在搜索期间可以得到改善的几种方法。
7、答：最短路径为ACEBDA， 其耗散值为15。
8、解：（1）（S，O，S
0
，G）
S：3个黑色板和3个白色板在7个空格中的任何一种布局都是一个
状态。
O：① 一块板移入相邻的空格；
② 一块板相隔1块其他的板跳入空格；
③ 一块板相隔2块其他的板跳入空格。
S
0
：
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
1
W W W B B B
W W W B B B
W W W B B B
W W W B B B
P
7
7
7654321
（2）
33
140
321321
P
3
P
3
（3）定义启发函数h为每一白色板左边的黑色板数的和。
显然，
h(n)h
(n)
，所以该算法具有可采纳性。
h(n
j
)h(n
i
)c(n
i
,n
j
)
又，
，所以该启发函数h满足单调限制条件。
h(t)0
9、解：
((( ),( )),( ),(( ),( )))
((S,( )),( ),(( ),( )))
((A,( )),( ),(( ),( )))
((A,S),( ),(( ),( )))
((A,A),( ),(( ),( )))
((A),( ),(( ),( )))
(S,( ),(( ),( )))
(A,( ),(( ),( )))
(A,S,(( ),( )))
(A,A,(( ),( )))
(A,(( ),( )))
2
发布者：admin，转转请注明出处：http://www.yc00.com/xitong/1715384269a2609933.html
评论列表（0条）