答深度优先搜索算法的特点是VIP专享VIP免费

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 有一个扩展出...