《人工智能导论》习题及解答 第4章 搜索技术与问题求解

4.1试用状态空间表示猴子摘香蕉问题和野人与传教士问题。解：一、猴子摘香蕉问题（1）状态定义采用四元组S=(x,y,z,w)描述系统状态，各元素含义与取值如下：x：猴子的水平位置，取值为房间内离散区域（如A、B、C等）；y：箱子的水平位置，取值与猴子位置一致；z：猴子的所处状态，z=0表示猴子在地面，z=1表示猴子站在箱子上；w：香蕉获取状态，w=0表示香蕉未被摘取，w=1表示香蕉被摘取。（2）初始状态和目标状态设香蕉位于水平位置C，箱子初始位于水平位置B，猴子初始位于水平位置A，则初始状态为S0​=(A,B,0,0)；目标状态为猴子站在箱子上且在香蕉的位置拿到香蕉，即Sg​=(C,C,1,1)。（3）操作算子定义4种满足前置条件的操作，执行后改变状态参数，具体如下：Move(u,v)：猴子从位置u移动到位置v，前置条件：z=0，执行后x=v；Carry(u,v)：猴子从位置u搬箱子到位置v，前置条件：x=y=u、z=0，执行后x=v、y=v；Climb：猴子站到箱子上，前置条件：x=y、z=0，执行后z=1；Grab：猴子摘取香蕉，前置条件：x=y=C、z=1、w=0，执行后w=1。二、野人与传教士问题（1）状态定义采用三元组S=(m,c,b)描述河左岸的状态（右岸状态可由总数推导），各元素含义与取值如下：m：左岸传教士数量，m∈{0,1,2,3}；c：左岸野人数目，c∈{0,1,2,3}；b：船的位置，b=1表示船在左岸，b=0表示船在右岸。状态约束：任何时刻，两岸及船上的野人数目不得超过传教士数目（传教士数量为0时除外），即左岸需满足m=0或m≥c，右岸需满足3−m=0或3−m≥3−c，不满足约束的为无效状态。（2）初始状态与目标状态所有传教士、野人和船均在左岸，初始状态为S0​=(3,3,1)；所有传教士、野人和船均在右岸，目标状态为Sg​=(0,0,0)。（3）操作算子操作以(nm​,nc​)表示每次船上的传教士和野人数目，船的摆渡方向分左岸→右岸（b=1→0）和右岸→左岸（b=0→1），需满足船的最大载客量为2，且操作后状态符合约束。核心有效操作包括：(1,0)、(0,1)、(1,1)、(0,2)、(2,0)，执行操作后对应岸的m、c和船位b同步更新。4.2有一个农夫带着一匹狼、一只羊和一筐白菜过河，假设农夫每次渡河时只能带其中一个，当无农夫在场时，狼会吃掉羊，羊会吃掉白菜，请为该问题设计状态空间，并画出状态空间图。解：一、状态空间设计（1）状态定义采用四元组S=(f,w,s,c)描述河左岸的状态，右岸状态由总数推导，各元素取值为0或具体含义如下：f=1表示农夫在左岸，f=0表示农夫在右岸；w=1表示狼在左岸，w=0表示狼在右岸；s=1表示羊在左岸，s=0表示羊在右岸；c=1表示白菜在左岸，c=0表示白菜在右岸。状态约束：农夫不在某岸时，该岸不能同时存在狼和羊，也不能同时存在羊和白菜，即无效状态为(0,1,1,*)、(0,*,1,1)。（2）初始状态与目标状态 所有对象均在左岸，初始状态为S0​=(1,1,1,1)；所有对象均在右岸，目标状态为Sg​=(0,0,0,0)。（3）操作算子操作记为F(X)，其中X为农夫携带的物品（X=∅表示不带物品），需满足：农夫与船位置一致，每次仅能带一个物品且操作后状态为有效状态。有效操作共4种：F(∅)（农夫单独过河）、F(W)（带狼过河）、F(S)（带羊过河）、F(C)（带白菜过河）。二、问题求解的状态空间图4.3设有三枚硬币，其初始状态为“反正反”，每次必须且只能翻转一个硬币，试用状态空间图搜索达到“正正正”或“反反反”目标状态的最佳方案。解：该问题的状态定义如下：采用三元组(a,b,c)表示，a,b,c分别对应三枚硬币的状态，取值为1表示正面，取值为0表示反面。初始状态：反正反，记为(0,1,0)；目标状态：正正正，记为(1,1,1)或反反反，记为(0,0,0)。三个钱币正反组合可能出现的状态有8种组合，该问题的状态集合为：Q0=(0,0,0),Q1=(0,0,1),Q2=(0,1,0),Q3=(0,1,1),Q4=(1,0,0),Q5=(1,0,1),Q6=(1,1,0),Q7=(1,1,1)操作算子有三种：翻转a，翻转b，翻转c；该问题的状态空间搜索图可表示为：最佳方案可为：（0,1,0）翻转a得到（1,1,0），翻转b得到（1,0,0），再翻转a得到（0,0,0）。4.4什么是搜索？盲目搜索和启发式搜索的根本区别是什么？答：在人工智能领域，搜索是指从问题的初始状态出发，在问题的状态空间中，通过不断应用预设的操作算子（规则），遍历并探索状态节点，寻找一条从初始状态到目标状态的有效路径的过程。盲目搜索和启发式搜索是两类基础的搜索策略，根本区别在于是否利用与问题领域相关的启发信息引导搜索过程，具体特征与差异如下：盲目搜索：搜索过程中仅根据操作算子的规则遍历状态空间，不利用任何与问题目标相关的启发信息，对所有待探索节点一视同仁，属于无方向的穷举式搜索。算法逻辑简单，搜索效率低，易出现组合爆炸问题，仅适用于状态空间规模较小的简单问题。主要有宽度优先搜索、深度优先搜索、等代价搜索等。启发式搜索：搜索过程中引入与问题领域相关的启发信息，通过设计专门的估价函数对每个节点的“优劣”进行量化评估，优先探索估价更优、更接近目标状态的节点，减少无效的状态遍历。主要有A算法、A*算法、有序搜索等。4.5什么是估价函数？什么是启发式函数？试分析启发式函数的强弱对搜索效率的影响。答：估价函数是启发式搜索中用于量化评估节点优劣的核心函数，记为f(n)，其核心作用是估计从问题的初始状态出发，经过当前节点n到达目标状态的最小代价，为搜索方向的选择提供量化依据。经典估价函数的通用形式为：f(n)=g(n)+h(n)g(n)：从初始节点到当前节点n的实际代价（已走路径的真实代价，如移动步数、路径长度等）；h(n)：从当前节点n到目标节点的估计代价，由启发式函数定义，是估价函数中体现启发信息的核心部分，也叫启发式函数。启发式函数h(n)的强弱体现在与节点n到目标节点实际代价之间的差距。h(n)的取值越接近实际代价，启发式函数越强，则对搜索过程的引导作用越显著，搜索效率就越高，在满足可采纳性条件的前提下，能在保证最优解的同时，大幅缩短搜索时间。反之，h(n)的取值与实际代价偏离越大，那么启发式函数就越弱，搜索过程中会遍历大量无关节点，搜索效率降低，接近盲目搜索。123847654.6有图4-25所示的八数码问题，试按宽度优先搜索和深度优先搜索方法，画出状态空间搜索树。28316475图4-25八数码问题解：深度优先搜索：宽度优先搜索（略）4.7有图4-25所示的八数码问题，应用启发式A*算法，设计估价函数，画出搜索图，并给出搜索过程中OPEN表和CLOSE表的变化过程，试给出最优解。解：定义估价函数：f(n)=d(n)+w(n)d(n):节点n的深度，对g(n)的度量;w(n):与目标棋局相比,错位的棋子数目，对启发式函数h*(n)的度量。步骤OPEN表CLOSED表父节点是否为目标节点1s{}否2B,A,CssB,A,C否3D,E,F,A,Cs,BBD,E,F否4E,F,A,C,G,Hs,B,DDG,H否5I,F,A,C,G,H,Js,B,D,EEI,J否6K,F,A,C,G,H,Js,B,D,E,IIK否7L,F,A,C,G,H,J,Ms,B,D,E,I,KKL,M否8F,A,C,G,H,J,Ms,B,D,E,I,K,L是最佳走步序列：4.8假设有五个城市，城市之间距离如下表4-2所示。要求从A城出发，经过其他各城市一次且仅一次，最后回到A城，请找出一条距离最短的线路。表4-3五个城市间的距离ABCDEA010152014B10081215C15801012D20121008E14151280解：下图给出了问题的部分搜索分支，供参考：最优路径1：A→B→C→D→E→A（总代价50）最优路径2：A→E→D→C→B→A（总代价50）4.9极大极小搜索与剪枝搜索本质区别是什么？哪种搜索更有优势？为什么？答：二者的核心本质区别在于是否对博弈树的无效分支进行提前剪枝操作：（1）极大极小搜索是无剪枝的全节点遍历算法，需要计算博弈树中所有节点的倒推值，才能得到MAX方的最优策略，搜索过程中无任何分支省略；（2）α-β剪枝搜索是带剪枝的极大极小搜索，保留了极大极小搜索“自底向上计算倒推值、MAX取大、MIN取小”的核心逻辑，增加了α/β值动态更新和无效分支剪枝机制，无需遍历所有节点。α-β剪枝搜索相比极大极小搜索具有显著的优势，且未牺牲解的最优性，其原因在于：首先，α-β剪枝提升了搜索效率，通过剪去无效分支，无需计算博弈树中大量无关节点的倒推值，大幅减少了节点计算量和搜索时间；在博弈树规模较大时，效率提升尤为明显。其次，搜索深度显著增加。在相同的计算资源下，极大极小搜索因遍历所有节点，搜索深度受限；而α-β剪枝因减少了计算量，可探索博弈树的更深层次，