人工智能教程习题及答案第5章习题参考解答文档格式.docx
《人工智能教程习题及答案第5章习题参考解答文档格式.docx》由会员分享，可在线阅读，更多相关《人工智能教程习题及答案第5章习题参考解答文档格式.docx（15页珍藏版）》请在冰点文库上搜索。
但该船每次只能装载两个人，在任何岸边野人的数目都不得超过修道士的人数，否则修道士就会被野人吃掉。
假设野人服从任何一种过河安排，请使用状态空间搜索法，规划一使全部6人安全过河的方案。
（提示：
应用状态空间表示和搜索方法时，可用（Nm,Nc）来表示状态描述，其中Nm和Nc分别为传教士和野人的人数。
初始状态为（3,3），而可能的中间状态为（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°
，初始状态S0和目标状态Sg如图5.11所示，用宽度优先搜索法和深度优先搜索法求从S0到Sg的路径。
图5.11圆盘问题
5.10用有界深度优先搜索方法求解图5.12所示八数码难题。
初始状态为S0，目标状态Sg，要求寻找从初始状态到目标状态的路径。
28
123
163
84
754
765
S0
Sg
图5.12八数码难题图5.13推销员旅行交通费用图
5.11推销员旅行问题。
设有五个相互可直达的城市A、B、C、D、E，如图5.13所示，各城市间的交通费用已在图中标出。
推销员从城市A出发，去每个城市各旅行一次，最后到达城市E，请找出一条费用最省的旅行路线。
5.12什么是启发式搜索？
什么是启发信息？
5.13什么是估价函数？
在估价函数中，g（x）和h（x）各起什么作用？
5.14什么是最佳优先搜索？
局部最佳优先搜索与全局最佳优先搜索有何异同？
5.15用全局最佳优先搜索方法求解八数码难题。
如果八数码难题的初始状态图及目标状态图如图5.14所示，请利用全局最佳优先搜索算法求取由S0转换为Sg的路径，并画出它的全局最佳优先搜索树。
s0
sg
283
123
14
765
图5.14八数码难题
5.16什么是A*算法？
它的估价函数是如何确定的？
A*算法与A算法的区别是什么？
5.17A*算法有哪些性质？
它们的意义如何？
5.18证明单调性启发策略是可采纳的。
5.19如图5.37是一棵“与/或”树，请分别用“与/或”树的广度优先搜索及深度优先搜索求出其解树。
图5.37习题5.19的与或树图5.38习题5.20的与或树
5.20设有“与/或”树如图5.38所示，请分别按和代价法以及最大代价法求出解树的代价。
5.21设有如图5.39所示的博弈树，其中个叶子节点下的数值为假设的估值，请对该博弈树做如下工作：
（1）计算各节点的倒推值；
（2）利用α-β剪枝技术剪去不必要的分枝。
5.2习题参考解答
5.1答：
（略）
5.2答：
用状态空间法表示问题时，问题的解就是有向图中从某一节点（初始状态节点）到另一节点（目标状态节点）的路径。
求解过程的本质就是对状态空间图的搜索，即在状态空间图上寻找一条从初始状态到目标状态的路径。
在不考虑搜索的代价时，即假设状态空间图中各节点之间的有向边的代价相同时，最优解就是解路径中长度最短的那条路径，在考虑搜索代价时，最优解则是解路径中代价最小的那条路径。
因为在状态空间图中，可能存在几条长度或代价相等的最短解路径，所以，最优解可能会不唯一。
5.3答：
5.4答：
盲目搜索又称无信息搜索，即在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。
主要的盲目搜索策略有：
宽度优先搜索、深度优先搜索、有界深度优先搜索、代价数的宽度优先搜索和代价树的深度优先搜索。
5.5答：
深度优先搜索与宽度优先搜索的区别就在于：
在对节点n进行扩展时，其后继结点在OPEN表中的存放位置。
宽度优先搜索是将后继节点放入OPEN表的末端，而深度优先搜索则是将后继节点放入OPEN表的前端。
即宽度优先搜索按照“先扩展出的节点先被考察”的原则进行搜索，而深度优先搜索则按照“后扩展出的节点先被考察”的原则进行搜索。
宽度优先搜索是一种完备搜索，即只要问题有解就一定能够求出，而深度优先搜索是不完备搜索。
在不要求求解速度且目标节点的层次较深的情况下，宽度优先搜索优于深度优先搜索，因为宽度优先搜索效率低，但却一定能够求得问题的解；
在要求求解速度且目标节点的层次较浅的情况下，深度优先搜索优于宽度优先搜索。
因为当搜索算法在一个扩展的很深但又没有解的分支上，进行搜索是一种无效搜索，降低了求解的效率，有时甚至不一定能求得问题的解。
5.6解：
在这个迷宫中，S是源节点，F是目标节点，A，B，C，D，E是五个具有二叉分枝的节点，在每个节点处，都可能会出现两种路线，要么向左拐要么向右拐，我们在每个二叉节点处设立两个虚节点，以表示到该节点后的走向，向右拐为第一个虚节点，用下标1表示，向左拐为第二个虚节点，用下标2表示。
例如，A节点处向右拐的虚节点用A1表示，向左拐的虚节点用A2表示。
可以将该迷宫转换成一个有向图如图5.15所示。
图5.15走迷宫的有向图
图中，除F节点是目标节点外，其余没有后继节点的虚节点都说明走入了死胡同。
利用深度优先搜索，其搜索树如图5.16所示，图中节点旁所标数字为节点扩展次序。
所得到的解路径为：
S→A→A1→B→B1→C→C1→F
也就是说，从S出发，在A节点处不能左拐，而是直行，到B节点处右拐，到C节点也右拐，即可到达出口F。
利用宽度优先搜索，其搜索树如图5.17所示，图中节点旁所标数字为节点扩展次序。
所得到的解路径也为：
由搜索过程可以看出，宽度优先搜索的效率低于深度优先搜索。
图5.16深度优先搜索树图5.17宽度优先搜索树
5.7解：
5.8解：
5.9解:
设rA，rB，rC分别为将盘子A，B，C逆时针旋转90º
的操作，在运用这些操作符时的顺序为rA，rB，rC。
应用宽度优先搜索的搜索树如图5.18所示。
从图中可以看出，从初始状态S0到目标状态Sg的路径是：
S0→2→5→11→22（Sg）
应用深度优先搜索的搜索树如图5.19所示。
这里要指出的是，我们在应用深度优先搜索算法时，稍微作了一些改进，即不是只对当前节点判断其是否为目标节点，而是对当前节点的扩展节点进行判断，如果扩展节点中含有目标节点，则搜索停止，求解成功。
这有利于提高求解效率。
S0→2→3→4→Sg
图5.18圆盘问题的宽度优先搜索
图5.19圆盘问题的深度优先搜索
5.10解：
用有界深度优先搜索策略求解问题的搜索树如图5.20所示。
这里设深度界限dm=5，在这种情况下，该问题无解。
由此可以看出，在有界深度优先搜索算法中，深度界限的选择很重要。
选择过大，可能会影响搜索的效率；
选择的过小，有可能求不到解。
所以，有界深度优先搜索策略是不完备的。
图5.20有界深度优先搜索
5.11解：
由于涉及旅行费用，所以利用代价树宽度优先搜索方法求解。
为此，首先将旅行交通图转换为代价树如图5.21所示。
转换的方法如下：
从初始节点A开始，把与它直接相邻的节点作为它的后继节点，对其他节点也作同样的扩展，但若一个节点已作为某节点的前驱节点的话，则它就不能再作为该节点的后继节点。
由于要求从A出发后，到每个城市各旅行一次，因此，每条到达E的路径上都包含了所有的节点，不包含所有节点而到达节点E路径无效。
另外，图中的节点除了初始节点A外，其他的节点都有可能在代价树中多次出现，为了区分它的多次出现，分别用下标标出，以区别它们在不同分支及不同层次的出现，但它们却代表着旅行图中的同一个节点，例如，C12和C21分别表示代价数中第一分枝第二层和第二分支第一层的C节点，是旅行图中的同一节点C。
由于要求每个城市各旅行一次，因此，本题的代价树搜索算法如图5.22所示
搜索过程中，以简化的CLOSED表和OPEN表简单表示如下：
CLOSED表
OPEN表
NUL
A
B11（80）,C21（90）,E41（100）,D31（170）
A,B11
C21（90）,E12（145）,E41（160）,D31（170）,D12（180）,C12（190）
A,B11,C21
E12（145）,E41（160）,D31（170）,D22（175）,D12（180）,C12（190）,B22（200）,E22（230）
A,B11,C21,E12,E41,D31
D22（175）,D12（180）,C12（190）,B22（200）,E22（230）,E32（250）,C32（255）,B32（270）
A,B11,C21,E12,E41,D31,D22
D12（180）,C12（190）,B22（200）,E22（230）,E32（250）,C32（255）,E232（255）,B32（270）,B23（275）
A,B11,C21,E12,E41,D31,D22,D12
C12（190）,B22（200）,E22（230）,E32（250）,C32（255）,E232（255）,E132（260）,C13（265）,B32（270）,B23（275）
A,B11,C21,E12,E41,D31,D22,D12,C12
B22（200）,E22（230）,E32（250）,C32（255）,E232（255）,E132（260）,C13（265）,B32（270）,B23（275）,D13（275）,E131（330）
A,B11,C21,E12,E41,D31,D22,D12,C12,B22
E22（230）,E32（250）,C32（255）,E232（255）,E132（260）,C13（265）,B32（270）,B23（275）,D13（275）,E231（280）,D23（300）,E131（330）
A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32
E232（255）,E132（260）,C13（265）,B32（270）,B23（275）,D13（275）,E231（280）,D23（300）,E131（330）,B33（365）,E332（395）
A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,E232,E132,C13
B32（270）,B23（275）,D13（275）,E231（280）,D23（300）,E131（330）,B33（365）,E332（395）,E142（405）
A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,E232,E132,C13,B32
B23（275）,D13（275）,E231（280）,D23（300）,E131（330）,E331（335）,B33（365）,C33（380）,E332（395）,E142（405）
A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,E232,E132,C13,B32,B23
D13（275）,E231（280）,D23（300）,E131（330）,E331（335）,E242（340）,B33（365）,C33（380）,E332（395）,E142（405）
A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,E232,E132,C13,B32,B23,D13
E231（280）,D23（300）,E131（330）,E331（335）,E242（340）,E141（355）,B33（365）,C33（380）,E332（395）,E142（405）
A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,E232,E132,C13,B32,B23,D13,E231,D23
E131（330）,E331（335）,E242（340）,E141（355）,B33（365）,C33（380）,E241（380）,E332（395）,E142（405）
A,B11,C21,E12,E41,D31,D22,D12,C12,B22,E22,E32,C32,E232,E132,C13,B32,B23,D13,E231,D23,E131,E331,E242
E141（355）,B33（365）,C33（380）,E241（380）,E332（395）,E142（405）
OPEN表中节点右边括号中的数字为该节点代价。
当E242节点移入CLOSED表之后，因为它就是目标节点，且回溯路径中含有所有城市节点，因而成功退出。
所求得的最小代价路径为A→C21→D22→B23→E242，其代价是340。
因而，从城市A出发，经过各城市一次随后到大城市E的费用最省路线为：
A→C→D→B→E。
图5.21推销员旅行问题代价树
图5.22推销员旅行问题代价树宽度优先搜索算法框图
5.12答：
5.13答：
估价函数是一种用来表示和度量搜索树中节点的“希望”程度的一种的函数，其任务是估计待搜索节点的重要程度，为它们排定次序。
在估价函数中，g（x）为初始节点So到节点x已实际付出的代价。
h（x）是从节点x到目标节点Sg的最优路径的估计代价，搜索的启发信息主要由h（x）来体现，所以h（x）称作启发函数。
g（x）项体现了搜索的宽度优先趋势，这有利于搜索算法的完备性，但影响算法的搜索效率。
h（x）项体现了搜索的深度优先趋势，这会有利于搜索效率的提高，但影响搜索算法的完备性。
5.14答：
最佳优先搜索总是选择最有希望的节点作为下一个要扩展的节点，而这种最有希望的节点是按估价函数f（x）的值来挑选的，一般估价函数的值越小，它的希望程度越大。
局部最佳优先搜索是一种类似于深度优先搜索的启发式搜索方法，在对某一个节点扩展之后，只在后继节点的范围内选择下一个要考察的节点，范围比较小，所以称为局部最佳优先搜索。
全局最佳优先搜索是一种类似于宽度优先搜索的启发式搜索方法，在确定下一个扩展节点时，选择的范围是OPEN表中的全部节点，所以称为全局最佳优先搜索。
5.15解：
首先定义一个估价函数：
f（x）=d（x）+h（x）
其中，d（x）表示节点x在搜索树中的深度；
h（x）表示与节点x对应的棋盘中，与目标节点所对应的棋盘中棋子位置不同的个数。
例如，对于节点S0，其在搜索树中位于0层，所以d（x）=0，而它中的与Sg中棋子位置不同的个数是3，即h（x）=3，所以节点S0的估价函数值f（S0）=0+3=3，再如节点S1其估价函数f（S1）=d（S1）+h（S1）=1+3=4。
搜索树如图5.23所示。
图中，节点旁边圆圈内的数字表示该节点的f（x）值，Si表示节点扩展的顺序。
所以问题的解路径是S0→S1→S2→S3→Sg。
图5.23八数码难题的全局择优搜索树
5.16答：
A*算法是一种启发式搜索方法，利用这种算法进行搜索时，对扩展节点的选择方法做了一些限制，依据估价函数f（x）=g（x）+h（x）对OPEN表中的节点进行排序，并且要求启发函数h（x）是h*（x）的一个下界，即h（x）≤h*（x）。
h*（x）则是从x节点到目标节点的最小代价路径上的代价。
A*算法与A算法的区别就是A算法不要求启发函数h（x）是h*（x）的一个下界，即不限制条件h（x）≤h*（x）。
5.17答：
A*算法具有下列一些性质：
可采纳性、单调性、信息性。
A*算法具有可采纳性，是指对一个可求解的状态空间图，即从状态空间图的初始节点到目标节点存在路径，则该算法一定能在有限步内找到一条最佳路径，即最优解，并在此路径上结束。
A*算法的单调性是指对其估价函数中的h（x）部分即启发性函数，加了适当的单调性限制条件，使它对所扩展的一系列节点的估价函数值单调递增（或非递减），从而减少对OPEN表或CLOSED表的检查和调整，提高搜索效率。
A*算法的信息性是指其估价函数中的启发函数h（x），在满足h（x）≤h*（x）的前提下，h（x）的值越大越好。
h（x）的值越大，表明它携带的与求解问题相关的启发信息越多，搜索过程就会在启发信息指导下朝着目标节点前进，所走的弯路越少，搜索效率就会提高。
5.18证明：
将状态空间中的任意一条路径看作是由一系列状态S1,S2,S3,…,Sg组成，其中S1是起始状态，Sg是目标状态。
如果将Si+1看作是Si的子节点，则由搜索策略单调性可知，对启发函数h（x）有如下的限制：
（1）S1toS2：
h（S1）－h（S2）≤cost（S1,S2）
S2toS3：
h（S2）－h（S3）≤cost（S2,S3）
……
Sg-1toSg：
h（Sg-1）－h（Sg）≤cost（Sg-1,Sg）
（2）对目标节点Sg，有h（Sg）＝0
将
（1）中所有竖式相加，并根据
（2）中的h（Sg）＝0，得到：
PathS1toSg：
h（S1）≤cost（S1,Sg）
这就说明，单调性启发搜索策略中的启发函数h（x）满足A＊算法的要求，因而它是可采纳的。
证毕
5.19答：
5.20答：
5.21答：
升级会员 