最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

人工智能教程习题及答案第5章习题参考解答

IT圈 admin 42浏览 0评论

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

发布评论

评论列表 (0)

  1. 暂无评论