第三章问题求解方法习题解答.doc

第三章 问题求解方法3.1答：深度优先搜索与广度优先搜索的区别在于：在对节点n进行扩展时，其后继节点在OPEN表中的存放位置不同。广度优先搜索是将后继节点放入OPEN表的末端，而深度优先搜索则是将后继节点放入OPEN表的前端。广度优先搜索是一种完备搜索，即只要问题有解就一定能够求出，而深度优先搜索是不完备搜索。在不要求求解速度且目标节点的层次较深的情况下，广度优先搜索优于深度优先搜索；在要求求解速度且目标节点的层次较浅的情况下，深度优先搜索优于广度优先搜索。广度优先的正例：积木问题；深度优先的正例：邮递员问题，反例：国际象棋。3.2答：衡量标准为：这组子状态中有没有目标状态，如果有，则选择该节点并且搜索成功；若没有，则按照某种控制策略从已生成的状态中再选择一个状态作为当前状态重复搜索过程。3.3答：(1)广度优先搜索：该程序必须找到解，并且最好是最优解； (2)广度优先搜索：医生要根据病人的各种病状判断病人的病； (3)深度优先搜索：该程序要求一定要找到目标路径； (4)深度优先搜索：该程序要求找到最优解； (5)广度优先搜索：不能确定它们是否等同，既不能确定它们是否有等同解。3.4答：对于四皇后问题，如果放一个皇后的耗散值为1的话，则任何一个解的耗散值都是4。因此如果h是对该耗散值的估计，是没有意义的。对于像四皇后这样的问题，启发函数应该是对找到解的可能性的评价。利用一个位置放皇后后，消去的对角线的长度来进行评价。3.5答：定义h1=M+C-2B，其中M，C分别是在河的左岸的传教士人数和野人人数。B1表示船在左岸，B0表示船在右岸。也可以定义h2=M+C。h1是满足A*条件的，而h2不满足。要说明h2M+C不满足A*条件是很容易的，只需要给出一个反例就可以了。比如状态(1, 1, 1)，h2=M+C=1+1=2，而实际上只要一次摆渡就可以达到目标状态，其最优路径的耗散值为1。所以不满足A*的条件。下面我们来证明h1M+C-2B是满足A*条件的。我们分两种情况考虑。先考虑船在左岸的情况。如果不考虑限制条件，也就是说，船一次可以将三人从左岸运到右岸，然后再有一个人将船送回来。这样，船一个来回可以运过河2人，而船仍然在左岸。而最后剩下的三个人，则可以一次将他们全部从左岸运到右岸。所以，在不考虑限制条件的情况下，也至少需要摆渡次。其中分子上的3表示剩下三个留待最后一次运过去。除以2是因为一个来回可以运过去2人，需要个来回，而来回数不能是小数，需要向上取整，这个用符号表示。而乘以2是因为一个来回相当于两次摆渡，所以要乘以2。而最后的1，则表示将剩下的3个运过去，需要一次摆渡。化简有：再考虑船在右岸的情况。同样不考虑限制条件。船在右岸，需要一个人将船运到左岸。因此对于状态(M，C，0)来说，其所需要的最少摆渡数，相当于船在左岸时状态(M+1，C，1)或(M，C+1，1)所需要的最少摆渡数，再加上第一次将船从右岸送到左岸的一次摆渡数。因此所需要的最少摆渡数为：(M+C+1)-2+1 。其中(M+C+1)的1表示送船回到左岸的那个人，而最后边的1，表示送船到左岸时的一次摆渡。化简有：(M+C+1)-2+1=M+C。综合船在左岸和船在右岸两种情况下，所需要的最少摆渡次数用一个式子表示为：M+C-2B。其中B1表示船在左岸，B0表示船在右岸。 由于该摆渡次数是在不考虑限制条件下，推出的最少所需要的摆渡次数。因此，当有限制条件时，最优的摆渡次数只能大于等于该摆渡次数。所以该启发函数h是满足A*条件的。3.6答：在搜索期间改善h函数，是一种动态改变h函数的方法。像改进的A*算法中，对NEXT中的节点按g值的大小选择待扩展的节点，相当于令这些节点的h0，就是动态修改h函数的一种方法。由定理2：若h(n)满足单调限制，则由A*所扩展的节点序列，其f值是非递减的，即f(ni)f(nj)），当h满足单调条件时，A*所扩展的节点序列，其f是非递减的。对于任何节点i，j，如果j是i的子节点，则有f(i)f(j)。利用该性质，我们可以提出另一种动态修改h函数的方法：f(j)=max(f(i), f(j)以f(j)作为节点j的f值。f值的改变，隐含了h值的改变。当h不满足单调条件时，经过这样修正后的h具有一定的单调性质，可以减少重复节点的可能性。3.7答：像这种类型的问题，由于涉及到城市距离或旅行费用，所以利用代价树广度优先搜索求解。为此，首先必须将旅行交通图转换为代价树，转换方法为：从初始节点A开始，把与它直接相邻的节点作为他的后继节点，对其他节点也作同样的扩展，但若一个节点以作为某节点的前驱节点，则它就不能再作为该结点的后继结点。另外，图中节点除了初始节点A之外，其它的节点都有可能在代价树中多次出现，为了区分它们的多次出现，分别用下标1,2标出。但他们却是图中的同一个节点。设估价函数f(n)=d(n)+w(n)，其中d(n)为状态的深度，w(n)为城市间的距离。代价树如下所示：ACEBDA定义h1=n*k，其中n是还未走过的城市数，k是还未走过的城市间距离的最小值。 h2，其中n是还未走过的城市数，ki是还未走过的城市间距离中n个最小的距离。 显然这两个h函数均满足A*条件。3.8答：可定义h为：hB右边的W的数目设j节点是i节点的子节点，则根据走法不同，h(i)-h(j)的值和C(i, j)分为如下几种情况：（1）B或W走到了相邻的一个空格位置，此时： h(i)-h(j)=0, C(i,j)=1；（2）W跳过了1或2个W，此时 h(i)-h(j)=0, C(i,j)=1或2； （3）W向右跳过了一个B（可能同时包含一个W），此时： h(i)-h(j)=-1, C(i,j)=1或2；（4）W向右跳过了两个B，此时： h(i)-h(j)=-2, C(i,j)=2； （5）W向左跳过了一个B（可能同时包含一个W），此时： h(i)-h(j)=1, C(i,j)=1或2； （6）W向左跳过了两个B，此时： h(i)-h(j)=2, C(i,j)=2； （7）B跳过了1或2个B，此时 h(i)-h(j)=0, C(i,j)=1或2； （8）B向右跳过了一个W（可能同时包含一个B），此时： h(i)-h(j)=1, C(i,j)=1或2；（9）B向右跳过了两个W，此时： h(i)-h(j)=2, C(i,j)=2；（10）B向左跳过了一个W（可能同时包含一个B），此时： h(i)-h(j)=-1, C(i,j)=1或2； （11）B向左跳过了两个W，此时： h(i)-h(j)=-2, C(i,j)=2；纵上所述，无论是哪一种情况，具有:h(i)-h(j)C(i,j)。且容易验证h(t)=0，所以该h是单调的。由于h满足单调条件，所以也一定有h(n)h*(n)，即满足A*条件。3.9答： 3.10答：(1)余一棋的弈法如下：两棋手可以从5个钱币堆中轮流拿走一个、两个或三个钱币，拣起最后一个钱币者算输。试通过博弈证明，后走的选手必胜，并给出一个简单的特征标记来表示取胜策略。为了方便起见，用(AB)()()这样的表表示一个状态。这样得到搜索图如下： (2)八数码问题 空格：Up,Left,Down,Right3.11答：(1)与/或图的解图：那些可解结点的子图，包含一结点到目的结点集的、连通的可解结点的子图。在问题的完整的隐含图中扩展生成出包含初始结点和目的结点集合的连通的明显子图。(2)算法AO*：必须对当前已生成出的与或图中的所有结点实施其每解点是否为可解结点的标注过程，如果起始结点被标注为可解的，则搜索过程可成功地结束；如果起始结点还不能被标注为可解的，则应当继续扩展生成结点（尽可能地记录，所有生成的结点中，哪些结点被标注了可解的，以便减少下一次标注过程的工作量）；同样地，对不可解结点也同样如此。 利用结点的可解/不可解性质，能从搜索图中删去可解结点的任何不可解结点的子结点；同样地，能删去不可解结点的所有的子结点（搜索这些被删除的结点是没有意义的，而只会降低搜索的效率）。两个主要过程的反复：自上而下的图生长过程，并通过跟踪有标记的连接符寻找一个候选局部解图自下而上的估价函数值的修正、连接符的标记和SOLVED的标注过程(3)3.12答：此题要求按照课中例题的方式，给出算法，以下是每个循环结束时的搜索图。上面这种做法比较简单，也可以如下做：3.13答：略3.14答：博弈搜索通常被限制在一定的范围，搜索的目标是确定一步好的走法（好棋），等对手回手后，再继续搜索。因此，博弈搜索过程总是由当前状态向目标状态搜索，而不是由目标状态向当前状态搜索。这类博弈的实例有西洋跳棋等。3.15答：8（3，0，8）（7，8，3）、（0，6）、（8，9）（7,6）、（8,6,5）、（2,3）、（0,-2）、（6,2）、（5,8）、（9,2） 3.16答： 见上图3.17答：略3.18答：剪裁算法. 剪裁若极小层的(先辈层)则中止这个MAX以下的搜索 算法如下： double alphabeta( int depth, double alpha, double beta, Position p); /* alpha是MAX的当前值 beta是MIN的当前值,depth 是在搜索树中的深度,p是所求结点的位置*/ double t; if( depth=0 ) return evaluate(p); /* 如果P是叶结点,算出P的值 */ for( i=1; i alpha&MAX) if(t beta) return t; /*直接返回*/ else alpha = t; if( talpha&MIN) if(t beta) return t; /*直接返回*/ else alpha=t; return alpha; 3.19-3.22 答：略7