2024年3月25日发(作者:邓含巧)
第五章 搜索策略 习题参考解答
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人安全过河的方案。(提示:应用状态空间表示和搜索方法时,可用
(N
m
,N
c
)来表示状态描述,其中N
m
和N
c
分别为传教士和野人的人数。初始状态为(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°,初始状态S
0
和目标状
态S
g
如图5.11所示,用宽度优先搜索法和深度优先搜索法求从S
0
到S
g
的路径。
图5.11 圆盘问题
5.10 用有界深度优先搜索方法求解图5.12所示八数码难题。初始状态为S
0
,目标状态
S
g
,要求寻找从初始状态到目标状态的路径。
2
8
1 6
3
7 5
4
S
0
1 2
3
8
4
7 6
5
S
g
图 5.12 八数码难题 图5.13 推销员旅行交通费用图
138
2024年3月25日发(作者:邓含巧)
第五章 搜索策略 习题参考解答
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人安全过河的方案。(提示:应用状态空间表示和搜索方法时,可用
(N
m
,N
c
)来表示状态描述,其中N
m
和N
c
分别为传教士和野人的人数。初始状态为(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°,初始状态S
0
和目标状
态S
g
如图5.11所示,用宽度优先搜索法和深度优先搜索法求从S
0
到S
g
的路径。
图5.11 圆盘问题
5.10 用有界深度优先搜索方法求解图5.12所示八数码难题。初始状态为S
0
,目标状态
S
g
,要求寻找从初始状态到目标状态的路径。
2
8
1 6
3
7 5
4
S
0
1 2
3
8
4
7 6
5
S
g
图 5.12 八数码难题 图5.13 推销员旅行交通费用图
138