-
人工智能原理
练习题
-1
从习题中选择自己感兴趣的题目进行思考和解答，
任何尝试都是有益的。
必要时，
仔细阅读教科
书当中的某些章节。对于加星
号的习题，应该编写程序来完成。
第
1
章
人工智能概述
1
用自己的语言定义：
（
a
）智能，
（
b
）人工智能，
（
c<
/p>
）智能体。
2
用你自己的话定义下列术语：智
能体、智能体函数、智能体程序、理性、自主、反射型智能
体、基于模型的智能体、基于
目标的智能体、基于效用的智能体、学习智能体。
3
对于下列智能体，分别给出任务
环境
PEAS
描述：
a.
机器人足球运动员；
b.
因特网购书智能体；
c.
自主的火星漫游者；
d.
数学家的定理证明助手。
4
检查
AI
的文献，去发现下列任务现在计算机是否能够解决：
a.
打正规的乒乓球比赛。
b.
在开罗市中心开车。
c.
在市场购买可用一周的杂货。
d.
在万维网上购买可用一周的杂货。
e.
参加正规的桥牌竞技比赛。
f.
发现并证明新的数学定理。
g.
写一则有内涵的有趣故事。
h.
在特定的法律领域提供令人满意的法律建议。
i.
从英语到西班牙语的口语实时翻译。
j.
完成复杂的外科手术。
对于现在不可
实现的任务，
试着找出困难所在，
并预测如果可能的话它们什么
时候能被克服。
5
Loebner
奖每年颁发给最接近
天通过某个版本图灵测试的程序。
查找和汇报
Loebner<
/p>
奖最近的
得主。它使用了什么技术？它对
AI
目前的发展水平有什么推动？
6
这道习题要探讨的是智能体函数与智能体程序的区别：
a.
是否有不止一个智能体程序可以实现给定的智能体函数？
请举例，或者说明为什么不可能。
b.
有没有无法用任何智能体程序实现的智能体函数。
c
．给定一个机器体系结构，能使每个智能体程序刚好实现一个智能体函数
吗？
d.
给定一个存储量为
n
比特的体系结构，可以有多少种可能的不同智能体程序？
7
有一
些类众所周知的难题对计算机而言是难以解决的困难，其它类问题是不能判定的。这是
否
意味着
AI
是不可能的？
1
8
内省
-----
汇报自己的内心想法
-----
是如何不精确的？我会搞错
我怎么想的吗？请讨论。
第
2
章
搜索技术
1
解释为什么问题的形式化必须在目标的形式化之后。
2
有限的状态空间总是导致有限的
搜索树吗？是树结构的有限空间呢？你能更精确地说出什么
类型的状态空间总是导致有限
的搜索树吗？（改编自
Bender
，
1996
）
2
给出下列问题的初始状态、
目标测试、
后继函数和耗散函数。
选择精确
得足以实现的形式化。
a.
只用四种颜色对平面地图染色
，要求每两个相邻的地区不能染成相同的颜色。
b.
一
间屋子里有一只
3
英尺的猴子，屋子的房顶上挂着一串香蕉，离
地面
8
英尺
.
屋子里有
两个可叠放起来、可移动、可攀登的
3
英尺高的箱子。猴子很想得到香蕉。
c.
有一个程序，当送入一个特定文件的输入记录时会输出“不合法的输入记录”
。已知每个
记录的处理独立于其它记录。要求找出哪个记录不合法。
d.
有三个水壶，容量分别为
12<
/p>
加仑、
8
加仑和
3
加仑，还有一个水龙头。可以把壶装满或者
倒空，从一个壶倒
进另一个壶或者倒在地上。要求量出刚好
1
加仑水。
*3
传教士和野人
问题通常描述如下：
三个传教士和三
个野人在河的一边，
还有一条能载一个
人或者两个人的船。
找到一个办法让所有的人都渡到河的另一岸，
要求在任何地方野人数
都
不能多于传教士的人数
（可以只有野人没有传教士）
。
这个问题在
AI
领域
中很著名，
因为它
是第一篇从分析的观点探讨问题形式化的论文
的主题（
Amarel,1968
）
a
.
精确地形式化该问题，只描述确保该问题有解所必需的特性。画出该问题的完全状态空间
图。
b
.
用一个合适的搜索算法实现和最
优地求解该问题。检查重复状态是个好主意吗？
c
.
这个问题的状态空间如此简单，
你认为为什么人们求解它却很困难？
*4
编写一个程序，当输入两个网页的
URL
（链接地址）后能找到从一个网页到另一个网页的链
接
路径。什么样的搜索策略是适合的？双向搜索是好主意吗？能用搜索引擎实现一个前辈
函
数吗？
5
考虑一个状态空间，它的初始状态编号为
1
，状态
n
的后继函数返回两个状态，编号为
2n
和
2n+1
。
a.
画出状态
1
到
15
的部分状态空间图。
b.
假设目标状态为
11
。
列出用以下算法访问节点的顺序：
广度优先搜索
，
深度限制为
3
的深
< br>度有限搜索，以及迭代深入搜索。
c.
双向搜索是否适合这个问题？如果合适的话，详细地描述它是怎样工作的。
d.
在双向搜索中每个方向上的分支因子是什么？
e.
对（
c
）的回答是否能提出问题的一种重新形式化，使你可以几乎不用搜索来求解从状态
1
到达目标状态的问题？
*6
实现两种八数码游戏的后继函数：一种通过复制和编辑八
数码游戏的数据结构立刻生成它的
2
全部后继；
另一种每次调用的时候通过直接修改父状态
（需要
的话可以撤消修改）
生成一个
新后继。写出使用这两种后继函数
的迭代深入算法和深度优先算法并比较它们的性能。
7
证明用于
GRAPH-SEARC
H
算法是，单步耗散为常数的代价一致搜索和广度优先搜索是最优
的。给出一个单步消耗为常数的状态空间，在其中使用迭代深入的
GRAPH-
SEARCH
算法
会找到非最优解。
8
描述一个状态空间，在其中迭代
深入搜索比深度优先搜索的性能要差很多（例如，一个是
O
（<
/p>
n
2
）
，另一个
是
O
（
n
）<
/p>
）
。
*9
在下图中所示的平面上有两个点
，之间有很多凸多边形障碍物，考虑寻找这两个点之间的最
短路很的问题。这是机器人在
拥挤的环境中求解道路导航问题的一种理想化情况。
a
.
假设状态状态空间由平面上所有
的点（
x,y
）组成。共有多少个状态？共有多少条到达目
标的路径？
b
.
简要解释为什么在这个场景中从一个多边形的顶点到另一个顶点的最短距离必然由连接<
/p>
某些多边形的顶点的直线段组成。
现在定义一个良好的状态空间。
这个状态空间有多大？
c
.
定义必要的函数来实现这个搜索
问题，包括把一个顶点作为输入的后继函数，它返回从
该顶点出发能够通过直线段到达的
顶点集合。
（不要忘记该顶点所在的多边形的相邻顶
点。
）用直线段的长度作为启发函数。
d
.
应用本章中的一种或多种搜索算
法来求解这个领或内的一定范围的问题，并评价它们的
性能。
G
S
10
跟
踪
A*
搜索算法用直线距离启发式求解从
Lugoj
到
Bucharest
问
题的过程。按顺序列出算法
扩展的节点和每个节点的
f
，
g
，
h
值。
11
启发式路径算法
是一个最佳优先搜索，它的目标函数是
f(n) = (2 - w) g(n) + w h(n)
。算法中
w
取什么值能保证算法是最优的？当
w =
0
时，这个算法是什么搜索？
w =
1
呢？
w =
2
呢？
12
设计一个状态空间，在其中用
GRAPH-SEARCH
的
A*
算法返回的不是最优解，如果它的启<
/p>
发函数
h(n)
是可采纳的但不是一致的
。
13
在第
4.2.2
节，我们定义了松弛的八数码游戏，其中如果<
/p>
B
是空的，一个棋子可以直接从方
格
A
移到方格
B
。这
个问题的精确解定义了
Gaschnig
启发式（
Gaschnig
，
1979
）
。解释为什
3
么
Gaschnig
启发式至少和
h
1
（不在位棋子数）
一样精确，
并说明它比
h
1
和
h
2
（曼哈顿距离）
更精确的情况。你能给出一个有效计算
Gaschnig
启发式的方法吗？
14
根据下面的特殊情况给出算法的名称：
a. k = 1
的局部剪枝搜索。
b. k =
∞的局部剪枝搜索。
c.
所有时刻
T =
0
的模拟退火搜索。
d.
种群大小为
N =
1
的遗传算法。
15
有些情况下一个问题找不到好的评价函数，但是有一个好
的比较方法：即只是指出一个节点
是否优于另一个节点而不需要指出它们实际的评价数值
。
证明这对于最佳优先搜索就已经足
够了。
A*
算法是否类似？
16
假设一个智能体在一个教科书中图
4.18
所示的
3
╳
3
大小的迷宫里（如下图）
。智能体知道它
的起始位置是（
1
，
1<
/p>
）
，目标位置是（
3
，
3
）
，四种行动
Up
（上）
，
Down
（下）
，
Left
（
左）
，
Right
（右）通常可以发挥
效果，除非遇到有墙阻碍。智能体不知道迷宫内部的墙在哪些地
方。
在任何给定的状态，
智能体知道合法行动集合；
它也知道一
个状态是已经访问过的状态
还是新状态。
3
G
2
1
S
1
2
3
图<
/p>
4.18
一个简单的迷宫问题。智能体从状态
< br>S
出发到达状态
G
，但是智能体
对环境一无所知
a.
解释这个联机
搜索问题如何可以视为在信念状态空间中的脱机搜索问题，初始的信念状
态包括所有可能
的环境布局。初始信念状态有多大？信念状态空间有多大？
b.
在初始状态可能有多少个不同的感知信息？
c.
描述这个问题的偶发性计划的头几个分支。完整的计划（
大约）有多大？
注意这个偶发性计划是符合给定描述的每个可
能环境的解决方案。
因此，
即使在未知环境
4
下搜索和行动的交叉也不是严格必需的了。
*17
在本题中，我们将在机器人
导航问题中考察爬山法，以第
9
题中图示（教科书图
3.22
）的环
境为例。
a.
用爬山法算法重复习题
9
。
智能体会卡在局部最小值上吗？可能遇到被凸障碍物卡住的情
况吗？
b.
构造一个非凸多边形的环境，智能体在其中会被卡住。
c.
修改爬山法算法，在决定下一步的时候不用深度为
1
的搜索，而用深度为
k
的搜索。它
将找到最好的
k
步路径
并且沿着该路径走一步，然后重复这个过程。
d.
有没有某个
k
使得新的算法保证能避免局部极小
值？
e.
解释
LRT
A*
是怎样使新的算法能够在这种情况下避免局部极小值的。
18
用你自己的话定义约束满足问
题、约束、回溯搜索、弧相容、后向跳转和最小冲突。
19
图
5.1
（澳大利亚地图）所示的地图染色问题一共有多少个解？
20
解释为什么在
CSP
搜索中，一个好的启发式选择变量的时候应该选择约束最多的变量，而选
择
值得时候应该选择造成约束最少的。
21
对以下两个问题给出精确的约束满足问题的形式化：
a.
直线地面规划：在一个大的矩形里找到不重叠放置许多小的矩形的方法。
b.
授课日程安排：给定了固定数量的教授和教室，一个可提
供课程的清单，以及可能安排课
程的时间段清单。每个教授有他（或她）能教的课程列表
。
22
分别用回溯算法、前向检验算法、
MRV
和最少约束值启发式算
法手工求解下图（图
5.2
）中
的密码
算术问题。
T W O
+ T W
O
F O U
R
F
T
U
W
R
O
X
3
X
2
X
1
(a)
(b)
图
5.2
（
a
）一个密
码算术游戏。每个字母表示一个不同的数字：目标是找到能使加法式子成立的代替字母的数
字，附加约束是前面的数字不能是
0
。（
b
）密码算术游戏的约束超图，表示了
Alldiff
约束和每列相加的约束。每
个约束在图中用方块表示，连接到它所约
束的变量
5