人工智能教程习题及答案第5章习题参考解答
137
第五章
搜索策略
习题参考解答
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)