人工智能原理练习题-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是不可能的？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 实现两种八数码游戏的后继函数：一种通过复制和编辑八数码游戏的数据结构立刻生成它的全部后继；另一种每次调用的时候通过直接修改父状态（需要的话可以撤消修改）生成一个新后继。

写出使用这两种后继函数的迭代深入算法和深度优先算法并比较它们的性能。

7 证明用于GRAPH-SEARCH 算法是，单步耗散为常数的代价一致搜索和广度优先搜索是最优的。

给出一个单步消耗为常数的状态空间，在其中使用迭代深入的GRAPH-SEARCH 算法会找到非最优解。

8 描述一个状态空间，在其中迭代深入搜索比深度优先搜索的性能要差很多（例如，一个是O（n 2），另一个是O （n ））。

*9 在下图中所示的平面上有两个点，之间有很多凸多边形障碍物，考虑寻找这两个点之间的最短路很的问题。

这是机器人在拥挤的环境中求解道路导航问题的一种理想化情况。

a . 假设状态状态空间由平面上所有的点（x,y ）组成。

共有多少个状态？共有多少条到达目标的路径？b . 简要解释为什么在这个场景中从一个多边形的顶点到另一个顶点的最短距离必然由连接某些多边形的顶点的直线段组成。

现在定义一个良好的状态空间。

这个状态空间有多大？c . 定义必要的函数来实现这个搜索问题，包括把一个顶点作为输入的后继函数，它返回从该顶点出发能够通过直线段到达的顶点集合。

（不要忘记该顶点所在的多边形的相邻顶点。

）用直线段的长度作为启发函数。

d . 应用本章中的一种或多种搜索算法来求解这个领或内的一定范围的问题，并评价它们的性能。

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）。

解释为什G么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），目标位置是（3，3），四种行动Up （上），Down （下），Left （左），Right （右）通常可以发挥效果，除非遇到有墙阻碍。

智能体不知道迷宫内部的墙在哪些地方。

在任何给定的状态，智能体知道合法行动集合；它也知道一个状态是已经访问过的状态还是新状态。

321321SG图4.18 一个简单的迷宫问题。

智能体从状态S 出发到达状态G ，但是智能体对环境一无所知a. 解释这个联机搜索问题如何可以视为在信念状态空间中的脱机搜索问题，初始的信念状态包括所有可能的环境布局。

初始信念状态有多大？信念状态空间有多大？b. 在初始状态可能有多少个不同的感知信息？c. 描述这个问题的偶发性计划的头几个分支。

完整的计划（大约）有多大？注意这个偶发性计划是符合给定描述的每个可能环境的解决方案。

因此，即使在未知环境下搜索和行动的交叉也不是严格必需的了。

*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 OF O U R(a)(b)图5.2 （a）一个密码算术游戏。

每个字母表示一个不同的数字：目标是找到能使加法式子成立的代替字母的数字，附加约束是前面的数字不能是0。

（b）密码算术游戏的约束超图，表示了Alldiff约束和每列相加的约束。

每个约束在图中用方块表示，连接到它所约束的变量23 考虑下述的逻辑问题：有5所不同颜色的房子，住着5个来自不同国家的人，每个人都喜欢一种不同牌子的香烟、不同牌子的饮料和不同的宠物。

给定下列已知条件，请回答问题“斑马住在哪儿？以及哪所房子里的人喜欢喝水？”：英国人住在红色的房子里。

西班牙人养的是狗。

挪威人住在最左边的第一所房子里。

住在黄色房子里的人喜欢抽Kools牌香烟。