资源描述：
《第3章 基本的问题求解方法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、习题31、答：深度优先搜索算法的特点是①一般不能保证找到最优解；②当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制；③方法与问题无关，具有通用性；④属于图搜索方法。宽度优先搜索算法的特点是①当问题有解时，一定能找到解；②当问题为单位耗散值，并且问题有解时，一定能找到最优解；③效率低；④方法与问题无关，具有通用性；⑤属于图搜索方法。2、答：在决定生成子状态的最优次序时，应该采用深度进行衡量，使深度大的结点优先扩展。3、答：（1）深度优先（2）深度优先（3）宽度优先（4）宽度优先（5）宽度优先4、答：如果把一个皇后放
2、在棋盘的某个位置后，它所影响的棋盘位置数少，那么给以后放皇后留下的余地就大，找到解的可能性也大；反之留下的余地就小，找到解的可能性也小。并不是任何启发函数对搜索都是有用的。5、解：首先用状态空间表达法表示该问题。（S，O，S0，G）S：（ML，CL，BL），其中0≤ML，CL≤5，BL∈{0，1}。（0，0，1）达不到（0，0，0）（0，1，1）（0，1，0）（0，2，1）（0，2，0）（0，3，1）（0，3，0）（0，4，1）（0，4，0）（0，5，1）（0，5，0）达不到（1，0，1）不合法（1，0，0）不合法（1，1，
3、1）（1，1，0）（1，2，1）不合法（1，2，0）不合法（1，3，1）不合法（1，3，0）不合法（1，4，1）不合法（1，4，0）不合法（1，5，1）不合法（1，5，0）不合法（2，0，1）不合法（2，0，0）不合法（2，1，1）不合法（2，1，0）不合法（2，2，1）（2，2，0）（2，3，1）不合法（2，3，0）不合法（2，4，1）不合法（2，4，0）不合法11（2，5，1）不合法（2，5，0）不合法（3，0，1）不合法（3，0，0）不合法（3，1，1）不合法（3，1，0）不合法（3，2，1）不合法（3，2，0）不合法
4、（3，3，1）（3，3，0）（3，4，1）不合法（3，4，0）不合法（3，5，1）不合法（3，5，0）不合法（4，0，1）不合法（4，0，0）不合法（4，1，1）不合法（4，1，0）不合法（4，2，1）不合法（4，2，0）不合法（4，3，1）不合法（4，3，0）不合法（4，4，1）（4，4，0）（4，5，1）不合法（4，5，0）不合法（5，0，1）达不到（5，0，0）（5，1，1）（5，1，0）（5，2，1）（5，2，0）（5，3，1）（5，3，0）（5，4，1）（5，4，0）（5，5，1）（5，5，0）达不到O：该问题有两
5、种操作，即从左岸划向右岸的Pmc操作和从右岸划向左岸的qmc操作。if(ML,CL,BL=1)then(ML-1,CL,BL-1)；(p10操作)if(ML,CL,BL=1)then(ML,CL-1,BL-1)；(p01操作)if(ML,CL,BL=1)then(ML-2,CL,BL-1)；(p20操作)if(ML,CL,BL=1)then(ML,CL-2,BL-1)；(p02操作)if(ML,CL,BL=1)then(ML-3,CL,BL-1)；(p30操作)if(ML,CL,BL=1)then(ML,CL-3,BL-1)
6、；(p03操作)if(ML,CL,BL=1)then(ML-1,CL-1,BL-1)；(p11操作)if(ML,CL,BL=1)then(ML-2,CL-1,BL-1)；(p21操作)if(ML,CL,BL=0)then(ML+1,CL,BL+1)；(q10操作)if(ML,CL,BL=0)then(ML,CL+1,BL+1)；(q01操作)if(ML,CL,BL=0)then(ML+2,CL,BL+1)；(q20操作)if(ML,CL,BL=0)then(ML,CL+2,BL+1)；(q02操作)if(ML,CL,BL=0
7、)then(ML+3,CL,BL+1)；(q30操作)if(ML,CL,BL=0)then(ML,CL+3,BL+1)；(q03操作)if(ML,CL,BL=0)then(ML+1,CL+1,BL+1)；(q11操作)if(ML,CL,BL=0)then(ML+2,CL+1,BL+1)；(q21操作)S0：（5，5，1）G：（0，0，0）①h(n)＝M＋C不满足A*算法的条件。例如状态（1，1，1），h(n)=M+C=1+1=2，这时只要一次摆渡就可以达到目标状态，最优路径的耗散值为1，所以不满足A*算法的条件。111(5,
8、5,1)h=10,f=105(5,4,0)h=9,f=103(5,3,0)h=8,f=92(5,2,0)h=7,f=84(4,4,0)h=8,f=913(5,4,1)h=9,f=116(5,3,1)h=8,f=108(3,3,0)h=6,f=99(5,1,0)h=6,f=97(5,0,0)
