第二章与或图搜索问题

2.1基本概念与或图是一个超图，节点间通过连接符连接。k-连接符：k1为“与”节点，k=1为“或”节点…...k个第二章与或图搜索2与或图n0n1n5n4n8n7n6n3n2n0有2个外向连接符，分别为1-连接符（n1),2-连接符（n4,n5);n8是n4的或子节点，同时又是n5的与子节点与或图搜索问题目标目标初始节点n0n1n5n4n8n7n6n3n2搜索的目的:考察n0到目标（终节点）集合N={n7,n8}是否有解并找到解图能解节点终止（目标）节点可解若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点才能解。若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。端节点：无子节点的节点不能解节点没有后裔的非终节点（端节点）是不能解节点。若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解。若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不能解。节点耗散值的递推计算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N为终节点集,Cn为连接符的耗散值…...i个nn1n2ni解图（对于无环与或图而言）递归定义：一个与或图G中，从节点n到节点集N的解图记为G’，G’是G的子图1.如果n是N的一个元素，则G’由单一节点n组成；2.如果n有一个外向连接符k指向节点{n1,n2,…,nk}使得从每一个ni到N有一个解图，则G’由n、连接符k和每一个ni到N的解图组成；3.否则n到N不存在解图。7目标n7目标n8初始节点n0•解图1：n4n5n6n3n2n1K(n0,N)=2+k(n4,N)+k(n5,N)=2+1+k(n8,N)+2+k(n7,N)+k(n8,N)=5目标n7目标n8初始节点n0•解图2：n4n5n6n3n2n1K(n0,N)=1+k(n1,N)=1+1+k(n3,N)=2+2+k(n5,N)+k(n6,N)=4+2+k(n7,N)+k(n8,N)+2+k(n7,N)+k(n8,N)=8目标n7目标n8初始节点n0•解图3：n4n5n6n3n2n1K(n0,N)=2+k(n4,N)+k(n5,N)=3+2k(n5,N)=3+2×2=7AO*算法思路:对局部图的评价目标目标初始节点abc两个过程扩展节点的图生成过程（自上而下）从最优的局部图中选择一个节点扩展计算耗散值的过程（自下而上）对当前的局部图重新计算耗散值判断祖先节点的可解/不可解性删去无用的后裔节点AO*算法举例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0设：K连接符的耗散值为K目标目标初始节点n0n1n2n3n4n5n6n7n8目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n1(2)n4(1)n5(1)初始耗散：q(n0)=h(n0)=3红色连接耗散：2+1+1=4黄色连接图耗散：1+2=3q(n0)=min{3,4}=3指针指向黄色连接符，n0,n1以及连接符构成局部解图；下一步选择n1进行扩展.h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点n0n4(1)n5(1)红色：4黄色：6n1n2(4)n3(4)2,5*h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0初始q(n1)=h(n1)=2;扩展后：q(n1)=min{1+4,1+4}=52;向上修改耗散：q(n0)=min{1+5,4}=4修改指针指向红色连接符，n0,n4,n5以及2-连接符构成待扩展局部解图；目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5*n6(2)n7(0)n8(0)2*h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0初始q(n5)=h(n5)=1;扩展后q(n5)=min{1+2,2+0+0}=2;指针选择2-连接；q(n0)=min{6,2+2+1}=5；目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5*n6(2)n7(0)n8(0)2*h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0n7,n8为终节点，故可解；于是，标记n5可解；n0尚未可解；选择红色局部图继续扩展(n4非终节点）目标目标初始节点n0n1n2n3n4n5n6n7n8红色：5黄色：6初始节点n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)21h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0q(n4)=1，不变，q(n0)=5不变。n4可解；故n0可解，算法成功退出。19AO*算法与A*的比较性质1）AO*应用于与或图搜索，搜索的是解图；而A*则应用于一般图的搜索，搜索的是解路径。2）AO*选择估价最小的局部解图优先扩展；而A*选择估价最小的路径（节点序列）加以优先扩展。3）AO*无需考虑评价函数f(n)的分量g(n)，只需对新扩展出的节点n计算h(n)，并倒推修正上层节点估值;而A*则需同时计算分量g(n)和h(n)，以评价节点n是否在代价最小的路径上。4）AO*存放候选的待扩展局部解图，并依据fi(n0)值排序(i个连接符）；而A*则应用OPEN表和CLOSE表分别存放待扩展节点和已扩展节点，并依据f(n)值排序。当h(n)≤h*(n)且h(n)满足单调性约束时，AO*一定能找到最佳解图。博弈问题与博弈树搜索博弈过程：二人零和：博弈结果只有胜、负、平三种情况全信息：当前及过往局势全开放非偶然：双方都理智决定行为（选择最有利于己方的策略）博弈树构成初始格局记为S0“AND”和“OR”逐层交替出现，己方扩展的为“OR”(MAX)，对方为“AND”(MIN)使己方获胜的终局状态为可解节点，对方获胜的为不可解节点因此，博弈树可以看成一个与或图（树），双方均可以在上搜索使己方获胜的解图（未必存在）分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）（3,1,1,1,1）（2,2,1,1,1）N（2,1,1,1,1,1）对方（MIN）先走,与节点我方（MAX）后走,或节点注：若有n0至N的解图，则我方必胜n0MINMINMINMAXMAX22分钱币问题（7）（6,1）（5,2）（4,3）（5,1,1）（4,2,1）（3,2,2）（3,3,1）（4,1,1,1）（3,2,1,1）（2,2,2,1）n1（3,1,1,1,1）（2,2,1,1,1）（2,1,1,1,1,1）n2我方（MAX）先走,或节点对方（MIN）后走,与节点注：若有n0至{n1,n2}的解图，则我方胜;但不存在！n0MAXMAXMAXMINMINMIN中国象棋一盘棋平均走50步，总状态数约为10161假设1毫微秒走一步，约需10145年。结论：对于许多博弈问题（国际跳棋、围棋等），不可能穷举。极小极大分析法不生成（也无法生成）完整的博弈树（因而也不搜索解图）；而是在有限的深度范围内，引入节点评估值，进而寻求当前较好的一种走法；模拟人类对弈的思维。当前己方所处状态作为根节点，按照宽度优先搜索策略，扩展出预定深度（偶数，成对）的与或搜索树，端节点用给定的估价函数估值，交替使用极小-极大的原则，倒推上层节点估值，直至根节点。对己方有利的估值大，反之对对方有利。博弈树扩展深度越大越精确，但计算量庞大，通常一定深度。24极小极大过程（4步，从端节点倒推评估值）05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小ab例：一字棋，井字游戏(Tic-Tac-Toe;)A方：a棋；B方：b棋；扩展深度：2层ab估价函数e(p)定义：＋∞,p是A方胜局－∞,p是B方胜局e(+p)-e(-p),p是未定局0,p是和局e(p)＝e(+p)：可使a成为三子一线的数目e(-p)：可使b成为三子一线的数目e(+p)=4;e(-p)=6;e(p)=-2,对B方有利。babababababababababababaaaa1010-1-10-10-212-1-211因此，MAX选择估值1走法；MIN选择之后，重新搜索。MAXMIN我方先手bbbbbaa2a1b1abba1bababa2a0bababa0ababa11bbaaaabb1a1aaabaa0bbaa0bbaa0bba0bb11abaababb11abababa1ba2bbaababaaa00babaaba0b0baba0129极小极大过程的简化？05-333-3022-30-23541-30689-30-33-3-3-21-36-30316011极大极小-剪枝边生成估值边计算倒推值，从而剪去某些分支的技术极大节点的下界为。极小节点的上界为。顺序：剪枝顺序自左至右或自右至左剪枝的条件：后辈节点的值≤祖先节点的值时，剪枝后辈节点的值≥祖先节点的值时，剪枝简记为：极小≤极大，剪枝极大≥极小，剪枝86-31453-350-剪枝（续）3-3022-30-2309-300-303305411-31661abcdefghijkmn32-剪枝注意点1)在不同类型节点间比较：极大VS极小2)与“先辈层”而不只是“父辈层”有值的节点比较3)只有节点值固定后，才能向上层传递4)-剪枝不影响极大极小算法的结果5)边生成节点边剪枝，而不是预生成搜索全图。