资源描述：
《《人工智能导论教学课件》人工智能》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、K用回溯策略求解如下所示二阶梵塔问题，画出搜索过程的状态变化示意图。对每个状态规定的操作顺序为：先搬1柱的盘，放的顺序是先2柱后3柱；再搬2柱的盘，放的顺序是先3柱后1柱；最后搬3柱的盘，放的顺序是先1柱后2柱。答：为了方便起见，我们用((AB)()O)这样的表表示一个状态。这样得到搜索图如下:：3)00)(B))(AB))0)0)2.滑动积木块游戏的棋盘结构及某一种将牌的初始排列结构如下:IbIbIbIwIwIwIeI其中B表示黑色将牌，、V表示白色将牌，E表示空格。游戏的规定走法是：(1)任意一个将牌可以移入相邻的空格，规定其耗散值为
2、1;(2)任意一个将牌可相隔1个或2个其他的将牌跳入空格，规定其耗散值等于跳过将牌的数目；游戏要达到的目标是使所有白将牌都处在黑将牌的左边(左边有无空格均可)。对这个问题，定义一个启发函数h(n),并给出利用这个启发函数用算法A求解时所产生的搜索树。你能否辨别这个h(n)是否满足下界范围？在你的搜索树中，对所有的节点满足不满足单调限制？提示：叫定义h为：h=B右边的W的数H设j节点是i节点的子节点，则根据走法不同，h(i)-h(j)的值和C(i,j)分为如下几种情况：(1)B或W走到了相邻的一个空格位置,此时：h(i)-h(j)=O,C(
3、ij)=l；(2)W跳过了1或2个W,此时h(i)-h(j)=O,C(iJ)=l或2；(3)W向右跳过了一个B(可能同时包含一个W),此时:h(i)-h(j)=-l,C(i,j)=l或2；(4)W向右跳过了两个B,此时:h(i)-h(j)=-2,C(i,j)=2；(5)W向左跳过了一个B(可能同时包含一个W),此时：h(i)-hd)=l,C(i,j)=l或2；(6)W向左跳过了两个B,此时：h(i)-h(j)=2,C(ij)=2：(7)B跳过了1或2个B,此时h(i)-h(j)=O,C(i,j)=l或2；(8)B向右跳过了一个W(可能同时
4、包含一个B),此时：h(i)-h(j)=l,C(i,j)=l或2；(9)B向右跳过了两个W,此时:h(i)-h(j)=2,C(i,j)=2；(10)B向左跳过了一个W(可能同时包含一个B),此时：h(i)-h(j)=-l;C(ij)=l或2；(11)B向左跳过了两个W,此时:h(i)-h(j)=-2,C(i,j)=2：纵上所述，无论是哪一种情况，具有：h(i)-hO),即满足A*条件。3对1.4节中的旅行商问题，定义两个h函数(非零
5、)，并给出利用这两个启发函数用算法A求解1・4节中的五城市问题。讨论这两个函数是否都在h*的下界范围及求解结果。定义hl=n*k,共中n是还未走过的城市数，k是还未龙过的城市间距离的最小值。h2=Zl，其中n是还未走过的城市数，k是还未走过的城市间距离小n个最小的距离。显然这两个h函数均满足A*条件。5、对N=5,k勺的M-C问题，定义两个h函数(非零)，并给出用这两个启发函数的A算法搜索图。讨论用这两个启发函数求解该问题吋是否得到最佳解。答：定义hl=M+C-2B,其中M,C分别是在河的左岸的传教上人数和野人人数。B=1表示船在左岸，B
6、=0表示船在右岸。也可以定义h2=M+Cohl是满足A*条件的，而h2不满足。要说明h(n)=M+C不满足A*条件是很容易的，只需要给出一个反例就可以了。比如状态(1,1,1)，h(n)=M+C=l+l=2,而实际上只要一次摆渡就可以达到目标状态，其最优路径的耗散值为lo所以不满足A*的条件。下面我们來证明h(n)=M+C-2B是满足A*条件的。我们分两种情况考虑。先考虑船在左岸的情况。如果不考虑限制条件，也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回來。这样，船一个來回可以运过河2人，而船仍然在左岸。而最后剩下的三个人
7、，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需耍x2+1摆渡次。其中分子上的”一3“表示剩下三个留待最后一次运过去。除以“2”是因为一M+C-3个來回可以运过去2人，需要2个來回，而"來回”数不能是小数，需要向上取整，这个用符号」】表示。而乘以“2“是因为一个來回相当丁•两次摆渡，所以耍乘以2。而最后的”+1“，则表示将剩下的3个运过去，需要一次摆渡。化简有：M+C—3c«xM+C-3小■a,勺a.z-x2+1>x2+1-M+C-3+1-M+C-222再考虑船在右岸的情况。同样不考虑限制条件。船在右岸，需要
8、一个人将船运到左岸。因此对于状态(M,C,0)来说,其所需要的最少摆渡数,相当于船在左岸时状态(M+l,C,1)或(M,C+l,1)所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡
