人工智能原理 练习题-1
从习题中选择自己感兴趣的题目进行思考和解答，任何尝试都是有益的。必要时，仔细阅读教科书当中的某些章节。对于加星号的习题，应该编写程序来完成。
第1章 人工智能概述
1 用自己的语言定义：（a）智能，（b）人工智能，（c）智能体。
2 用你自己的话定义下列术语：智能体、智能体函数、智能体程序、理性、自主、反射型智能体、基于模型的智能体、基于目标的智能体、基于效用的智能体、学习智能体。
3 对于下列智能体，分别给出任务环境PEAS描述：
a. 机器人足球运动员； b. 因特网购书智能体； c. 自主的火星漫游者；
d. 数学家的定理证明助手。
4 检查AI的文献，去发现下列任务现在计算机是否能够解决：
a. 打正规的乒乓球比赛。 b. 在开罗市中心开车。
c. 在市场购买可用一周的杂货。 d. 在万维网上购买可用一周的杂货。 e. 参加正规的桥牌竞技比赛。 f. 发现并证明新的数学定理。 g. 写一则有内涵的有趣故事。
h. 在特定的法律领域提供令人满意的法律建议。 i. 从英语到西班牙语的口语实时翻译。 j. 完成复杂的外科手术。 对于现在不可实现的任务，试着找出困难所在，并预测如果可能的话它们什么时候能被克服。
5 Loebner奖每年颁发给最接近天通过某个版本图灵测试的程序。查找和汇报Loebner奖最近的得主。它使用了什么技术？它对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加仑、8加仑和3加仑，还有一个水龙头。可以把壶装满或者
倒空，从一个壶倒进另一个壶或者倒在地上。要求量出刚好1加仑水。
*3 传教士和野人问题通常描述如下：三个传教士和三个野人在河的一边，还有一条能载一个
人或者两个人的船。找到一个办法让所有的人都渡到河的另一岸，要求在任何地方野人数都不能多于传教士的人数（可以只有野人没有传教士）。这个问题在AI领域中很著名，因为它是第一篇从分析的观点探讨问题形式化的论文的主题（Amarel,1968） a. 精确地形式化该问题，只描述确保该问题有解所必需的特性。画出该问题的完全状态空间
图。
b. 用一个合适的搜索算法实现和最优地求解该问题。检查重复状态是个好主意吗？ c. 这个问题的状态空间如此简单，你认为为什么人们求解它却很困难？
*4 编写一个程序，当输入两个网页的URL（链接地址）后能找到从一个网页到另一个网页的链
接路径。什么样的搜索策略是适合的？双向搜索是好主意吗？能用搜索引擎实现一个前辈函数吗？
5 考虑一个状态空间，它的初始状态编号为1，状态n的后继函数返回两个状态，编号为2n和
2n+1。
a. 画出状态1到15的部分状态空间图。
b. 假设目标状态为11。列出用以下算法访问节点的顺序：广度优先搜索，深度限制为3的深度有限搜索，以及迭代深入搜索。
c. 双向搜索是否适合这个问题？如果合适的话，详细地描述它是怎样工作的。 d. 在双向搜索中每个方向上的分支因子是什么？
e. 对（c）的回答是否能提出问题的一种重新形式化，使你可以几乎不用搜索来求解从状态1到达目标状态的问题？
*6 实现两种八数码游戏的后继函数：一种通过复制和编辑八数码游戏的数据结构立刻生成它的
2
全部后继；另一种每次调用的时候通过直接修改父状态（需要的话可以撤消修改）生成一个新后继。写出使用这两种后继函数的迭代深入算法和深度优先算法并比较它们的性能。
7 证明用于GRAPH-SEARCH算法是，单步耗散为常数的代价一致搜索和广度优先搜索是最优
的。给出一个单步消耗为常数的状态空间，在其中使用迭代深入的GRAPH-SEARCH算法会找到非最优解。
8 描述一个状态空间，在其中迭代深入搜索比深度优先搜索的性能要差很多（例如，一个是O
（n2），另一个是O（n））。
*9 在下图中所示的平面上有两个点，之间有很多凸多边形障碍物，考虑寻找这两个点之间的最
短路很的问题。这是机器人在拥挤的环境中求解道路导航问题的一种理想化情况。 a. 假设状态状态空间由平面上所有的点（x,y）组成。共有多少个状态？共有多少条到达目标的路径？
b. 简要解释为什么在这个场景中从一个多边形的顶点到另一个顶点的最短距离必然由连接某些多边形的顶点的直线段组成。现在定义一个良好的状态空间。这个状态空间有多大？ 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*算法返回的不是最优解，如果它的启
发函数h(n)是可采纳的但不是一致的。
13 在第4.2.2节，我们定义了松弛的八数码游戏，其中如果B是空的，一个棋子可以直接从方
格A移到方格B。这个问题的精确解定义了Gaschnig启发式（Gaschnig，1979）。解释为什
3
哈工大人工智能原理习题homework-1
