人工智能B卷参考答案及评分标准

第页20-20学年第二学期试卷参考答案及评分标准课程名称：《人工智能》B卷考核方式：考试考核形式：闭卷使用对象：一、单项选择题（共10小题，每题2分，共计20分）1、C2、B3、C4、B5、C6、D7、A8、D9、C10、A二、判断题（共10小题，每题2分，共计20分，对的打“√”，错的打“×”）11√12×13√14×15×16√17×18×19×20×三、应用题(共1小题，共计15分）21.参考答案：第一步，定义问题的描述形式。（5分）用四元组S=（f，w，s，v）表示问题状态，其中，f，w，s和v分别表示农夫，狼，羊和青菜是否在左岸，它们都可以取1或0，取1表示在左岸，取0表示在右岸。第二步，用所定义的问题状态表示方式，把所有可能的问题状态表示出来，包括问题的初始状态和目标状态。（5分）由于状态变量有4个，每个状态变量都有2种取值，因此有以下16种可能的状态：S0=(1,1,1,1)，S1=(1,1,1,0)，S2=(1,1,0,1)，S3=(1,1,0,0)S4=(1,0,1,1)，S5=(1,0,1,0)，S6=(1,0,0,1)，S7=(1,0,0,0)S8=(0,1,1,1)，S9=(0,1,1,0)，S10=(0,1,0,1)，S11=(0,1,0,0)S12=(0,0,1,1)，S13=(0,0,1,0)，S14=(0,0,0,1)，S15=(0,0,0,0)其中，状态S3，S6，S7，S8，S9，S12是不合法状态，S0和S15分别是初始状态和目标状态。第三步，定义操作，即用于状态变换的算符组F。（5分）由于每次过河船上都必须有农夫，且除农夫外船上只能载狼，羊和菜中的一种，故算符定义如下：L(i)表示农夫从左岸将第i样东西送到右岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。由于农夫必须在船上，故对农夫的表示省略。R(i)表示农夫从右岸将第i样东西带到左岸（i=1表示狼，i=2表示羊，i=3表示菜，i=0表示船上除农夫外不载任何东西）。同样，对农夫的表示省略。这样，所定义的算符组F可以有以下8种算符：L(0)，L(1)，L(2)，L(3)R(0)，R(1)，R(2)，R(3)第四步，根据上述定义的状态和操作进行求解。该问题求解过程的状态空间图如下图所示。四、回答题（共4小题，每题5分，共计20分）22．[参考答案]搜索求解问题的基本步骤是：（1）根据问题，定义出相应的状态空间，确定出状态的一般表示，它含有相关对象各种可能的排列。其中包括：问题的初始状态、目标状态，并能够给出所有其他状态的一般表示。(2)规定一组操作(算子)，能够作用于一个状态后过渡到另一个状态。(3)决定一种搜索策略，使得能够从初始状态出发，沿某个路径达到目标状态。23．[参考答案]若P∈G，说明经过P已经有一条路径，要选择一条好的路径（搜索成本较低的路径），因此要确定是否更改Tree中P到n的指针，或保留原来的指针。24．参考答案如下：它表示在搜索过程中既要充分利用已有的知识，给胜率高的节点更多的机会，又要考虑探索那些暂时胜率不高的兄弟节点。是一种对“利用”（Exploitation）和“探索”（Exploration）关系进行权衡的体现。25.[参考答案]MinMax搜索算法将生成后继与评价棋局两个过程分开考虑，即首先生成全部搜索树，然后再进行底层端节点静态评价和倒推值计算。这个过程效率会很低。五、算法理解题：（共2小题，第26题15分，第27题10分，共计25分）26.解：（每标出一个1分，最后的箭头5分）27.解：（每个剪枝4分，箭头2分） 首先，从根节点开始，向下生成出到达指定节点深度的节点(1)，由(1)的值为1，可得(2)>=1,继续扩展生成节点(3)，由于(3)的值8大于(2)的值1，所以确定(4)的值为8。由(4)的值可以确定(5)<=8。继续生成节点(6)、(7)，由(6)的节点为-4，得(7)>=-4，继续生成(8)，由(8)的值为-2，得到(9)=-2，进而得到(10)<=-2。继续生成节点(11)、(12)，由(11)=10，得到(12)>=10，(12)是极大值节点，其值大于其先辈节点(10)，满足β剪枝条件，因此(12)的其他节点被剪掉不再生成。得到(13)=-2，进而得到(14)>=-2。 同理生成(15)-