1 习 题 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 2 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）1401231231234567333377 PPP （3）定义启发函数h为每一白色板左边的黑色板数的和。 显然，)()(nhnh，所以该算法具有可采纳性。 又，),()()(0)(jiijnncnhnhth，所以该启发函数h满足单调限制条件。 9、解： ((( ),( )),( ),(( ),( ))) ((S,( )),( ),(( ),( ))) ((A,( )),( ),(( ),( ))) ((A,S),( ),(( ),( ))) ((A,A),( ),(( ),( ))) ((A),( ),(( ),( ))) (S,( ),(( ),( ))) (A,( ),(( ),( ))) (A,S,(( ),( ))) (A,A,(( ),( ))) (A,(( ),( ))) 3 (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 有一个扩展出...
