第五章 搜索策略 习题参考解答
5.1 练习题
5.1 什么是搜索？有哪两大类不同的搜索方法？两者的区别是什么？
5.2 用状态空间法表示问题时，什么是问题的解？求解过程的本质是什么？什么是最优解？最优解唯一吗？
5.3 请写出状态空间图的一般搜索过程。在搜索过程中OPEN表和CLOSE表的作用分别是什么？有何区别？
5.4 什么是盲目搜索？主要有几种盲目搜索策略？
5.5 宽度优先搜索与深度优先搜索有何不同？在何种情况下，宽度优先搜索优于深度优先搜索？在何种情况下，深度优先搜索优于宽度优先搜索？
5.6 用深度优先搜索和宽度优先搜索分别求图5.10所示的迷宫出路。
图5.10 习题5.6的图
5.7 修道士和野人问题。设有3个修道士和3个野人来到河边，打算用一条船从河的左岸渡到河的右岸去。但该船每次只能装载两个人，在任何岸边野人的数目都不得超过修道士的人数，否则修道士就会被野人吃掉。假设野人服从任何一种过河安排，请使用状态空间搜索法，规划一使全部6人安全过河的方案。（提示：应用状态空间表示和搜索方法时，可用(Nm,Nc)来表示状态描述，其中Nm和Nc分别为传教士和野人的人数。初始状态为(3,3)，而
137
可能的中间状态为(0,1),(0,2),(0,3), (1,1),(2,1),(2,2),(3,0),(3,1),(3,2)等。）
5.8 用状态空间搜索法求解农夫、狐狸、鸡、小米问题。农夫、狐狸、鸡、小米都在一条河的左岸，现在要把它们全部送到右岸去。农夫有一条船，过河时，除农夫外，船上至多能载狐狸、鸡和小米中的一样。狐狸要吃鸡，鸡要吃小米，除非农夫在那里。试规划出一个确保全部安全的过河计划。（提示：a.用四元组(农夫，狐狸，鸡，米)表示状态，其中每个元素都可为0或1，0表示在左岸，1表示在右岸；b.把每次过河的一种安排作为一个算符，每次过河都必须有农夫，因为只有他可以划船。）
5.9 设有三个大小不等的圆盘A、B、C套在一根轴上，每个圆盘上都标有数字1、2、3、4，并且每个圆盘都可以独立地绕轴做逆时针转动，每次转动90°，初始状态S0和目标状态Sg如图5.11所示，用宽度优先搜索法和深度优先搜索法求从S0到Sg的路径。
图5.11 圆盘问题
5.10 用有界深度优先搜索方法求解图5.12所示八数码难题。初始状态为S0，目标状态Sg，要求寻找从初始状态到目标状态的路径。
2 8 1 6 3 7 5 4 S0
1 2 3 8 4 7 6 5 Sg
图 5.12 八数码难题 图5.13 推销员旅行交通费用图
138
5.11 推销员旅行问题。设有五个相互可直达的城市A、B、C、D、E，如图5.13所示，各城市间的交通费用已在图中标出。推销员从城市A出发，去每个城市各旅行一次，最后到达城市E，请找出一条费用最省的旅行路线。
5.12 什么是启发式搜索？什么是启发信息？
5.13 什么是估价函数？在估价函数中，g(x)和h(x)各起什么作用？
5.14 什么是最佳优先搜索？局部最佳优先搜索与全局最佳优先搜索有何异同？ 5.15 用全局最佳优先搜索方法求解八数码难题。如果八数码难题的初始状态图及目标状态图如图5.14所示，请利用全局最佳优先搜索算法求取由S0转换为Sg的路径，并画出它的全局最佳优先搜索树。
s0 2 8 3 1 4 7 6 5
sg 1 2 3 8 4 7 6 5 图5.14 八数码难题
5.16 什么是A*算法？它的估价函数是如何确定的？A*算法与A算法的区别是什么？ 5.17 A*算法有哪些性质？它们的意义如何？ 5.18 证明单调性启发策略是可采纳的。
5.19 如图5.37是一棵“与/或”树，请分别用“与/或”树的广度优先搜索及深度优先搜索求出其解树。
AA5CDt562C1BB7D22t1t2t3t43t2t3t4
t1
图5.37 习题5.19的与或树 图5.38 习题5.20的与或树
5.20 设有“与/或”树如图5.38所示，请分别按和代价法以及最大代价法求出解树的代价。 5.21 设有如图5.39所示的博弈树，其中个叶子节点下的数值为假设的估值，请对该博弈树做如下工
139
作：
（1）计算各节点的倒推值；
（2）利用α-β剪枝技术剪去不必要的分枝。
5.2 习题参考解答
5.1 答：（略） 5.2 答：
用状态空间法表示问题时，问题的解就是有向图中从某一节点（初始状态节点）到另一节点（目标状态节点）的路径。求解过程的本质就是对状态空间图的搜索，即在状态空间图上寻找一条从初始状态到目标状态的路径。
在不考虑搜索的代价时，即假设状态空间图中各节点之间的有向边的代价相同时，最优解就是解路径中长度最短的那条路径，在考虑搜索代价时，最优解则是解路径中代价最小的那条路径。因为在状态空间图中，可能存在几条长度或代价相等的最短解路径，所以，最优解可能会不唯一。
5.3 答：（略） 5.4 答：
盲目搜索又称无信息搜索，即在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。主要的盲目搜索策略有：宽度优先搜索、深度优先搜索、有界深度优先搜索、代价数的宽度优先搜索和代价树的深度优先搜索。
5.5 答：
深度优先搜索与宽度优先搜索的区别就在于：在对节点n进行扩展时，其后继结点在OPEN表中的存放位置。宽度优先搜索是将后继节点放入OPEN表的末端，而深度优先搜索则是将后继节点放入OPEN表的前端。即宽度优先搜索按照“先扩展出的节点先被考察”的原则进行搜索，而深度优先搜索则按照“后扩展出的节点先被考察”的原则进行搜索。宽度优先搜索是一种完备搜索，即只要问题有解就一定能够求出，而深度优先搜索是不完备搜索。
在不要求求解速度且目标节点的层次较深的情况下，宽度优先搜索优于深度优先搜索，因为宽度优先搜索效率低，但却一定能够求得问题的解；在要求求解速度且目标节点的层次较浅的情况下，深度优先搜索优于宽度优先搜索。因为当搜索算法在一个扩展的很深但又没
140
有解的分支上，进行搜索是一种无效搜索，降低了求解的效率，有时甚至不一定能求得问题的解。
5.6 解：
在这个迷宫中，S是源节点，F是目标节点，A，B，C，D，E是五个具有二叉分枝的节点，在每个节点处，都可能会出现两种路线，要么向左拐要么向右拐，我们在每个二叉节点处设立两个虚节点，以表示到该节点后的走向，向右拐为第一个虚节点，用下标1表示，向左拐为第二个虚节点，用下标2表示。例如，A节点处向右拐的虚节点用A1表示，向左拐的虚节点用A2表示。可以将该迷宫转换成一个有向图如图5.15所示。
图5.15 走迷宫的有向图
图中，除F节点是目标节点外，其余没有后继节点的虚节点都说明走入了死胡同。
利用深度优先搜索，其搜索树如图5.16所示，图中节点旁所标数字为节点扩展次序。所得到的解路径为：
S→A→A1→B→B1→C→C1→F
也就是说，从S出发，在A节点处不能左拐，而是直行，到B节点处右拐，到C节点也右拐，即可到达出口F。
利用宽度优先搜索，其搜索树如图5.17所示，图中节点旁所标数字为节点扩展次序。所得到的解路径也为：
S→A→A1→B→B1→C→C1→F
由搜索过程可以看出，宽度优先搜索的效率低于深度优先搜索。
141
相关推荐：
loading