KM算法是通过给每个顶点一个标号(叫做顶标)来把求最大

KM算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[i]，顶点Yi的顶标为B[i]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[i]+B[j]=w[i,j]始终成立。KM算法的正确性基于以下定理：若由二分图中所有满足A[i]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。初始时为了使A[i]+B[j]=w[i,j]恒成立，令A[i]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d.d=min{A[i]+B[j]-w[i,j]|Xi在交错树中，Yi不在交错树中}状态空间搜索胡俊峰2013-11-29状态空间搜索适用范围和意义盲目搜索方法优化搜索技巧参考习题推荐材料状态空间搜索适用范围和意义盲目搜索方法优化搜索技巧参考习题推荐材料状态空间搜索适用范围和意义盲目搜索方法优化搜索技巧参考习题推荐材料盲目搜索方法定义状态(state)对问题在某一时刻进展情况的数学描述状态转移(state-transition)问题从一种状态到转移到另一种（或几种)状态的操作状态空间(statespace)问题可以处于的所有状态盲目搜索算法深度优先搜索广度优先搜索*随机化搜索深度优先搜索(Depth-firstSearch)搜索顺序：1-2-4-8-…“走迷宫”深度优先搜索实现：栈式和递归空间开销：栈的深度非递归的实现框架voidDfs(inta){while(栈不为且尚未到达目标状态){取出(pop)栈顶元素进行扩展将扩展出的元素依次压入(push)栈}}栈的应用迷宫老鼠解决方案尽可能前进，回溯，记录访问过的状态…具体：依次探查所有可能的没有被探查过的方向对探查过的位置进行标记无法继续前进则回溯在某一位置（i,j)进行试探:N(i-1,j)w(i,j-1)(i,j)E(i,j+1)S(i+1,j)i增值j增值方向001E110S20-1W3-10Ndrection[4][2]令k取0,1,2,3之一，则试探位置为：g=i+direction[k][0];h=j+direction[k][1];算法设计走一步，记一步。方向试探前进push(current)无法前进current=pop()求解迷宫中一条路径的方法：从入口开始，对每个当前位置沿（E,S,W,N)四个方向逐一进行试探，当选定一个可通行的方向后，把当前所在位置及所选的方向记录下来，然后从下一个位置开始继续探索；若在当前位置探索不到可通行的方向，则沿原路一步一步退回来，每后退一步，接着在该点试尚未试过的一个方向。如此重复直到到达出口。用一个栈记录走过的位置，栈中每个元素包括三项，分别记录当前位置的行坐标、列坐标以及在该位置上所选的方向（即directon数组的下标值）。广度优先搜索(Breadth-firstSearch)搜索顺序：1-2-3-4-5-…广度优先搜索实现：队列空间开销：可扩展结点+已扩展结点标记广度优先搜索的实现框架voidBFS(){while(队列可扩展且尚未到达目标状态){从队首依次取出队列中未扩展的结点进行扩展，并将新结点加入队尾。}}农夫、狼、羊、菜过河状态：wolf,sheep,cabbage,farmer（0，1，0，1）0，1分别代表两岸操作（算符）4种：运farmer、wolf运farmer、sheep运farmer、cabbage运farmer状态空间大小？24=16Map[2][2][2][2]可以转化为迷宫问题？状态=路口操作=通路限制条件=死胡同无形的迷宫。。。。。。。。。地毯式搜索！01234567891011121314。。。。。。如何求得最优解？广度优先搜索层层推进搜索的层数不超过答案所在的层数01234567891011121314。。。。。。广度优先搜索01234567891011121314。。。。。。队列的特点队列是一种特殊的线性表，只允许在表的一端有插入操作，而在另一端有删除操作。队头：允许删除的这一端叫队列的头。队尾：允许插入的这一端叫队列的尾。空队列：当队列中没有任何元素时，称为空队列。进队/出队：队列的插入操作通常称为进队列或入队列，队列的删除操作通常称为退队列或出队列。队列的基本概念：队列也称作先进先出表（FirstInFirstOut，FIFO表）。支持队尾插入，队头删除操作。a0a1a2an-1入队列队头队尾出队列队列的示意图队列ADTADTQueueisoperationsQueuecreateEmptyQueue(void);//创建一个空队列。intisEmptyQueue(Queuequ);//判队列qu是否为空队列。voidenQueue(Queuequ,DataTypex);//往队列qu尾部插入一个值为x的元素。voiddeQueue(Queuequ);//从队列qu头部删除一个元素。DataTypefrontQueue(Queuequ);//求队列qu头部元素的值。endADTQueue基于环形存储结构的队列实现a1a2a3a4…anfrontrearmodMAXSIZEenQueue:{rear=(rear+1)%MAXSIZEqBuffer[rear]=inData;}deQueue:{outData=qBuffer[rear];rear=(rear+1)%MAXSIZE;}基于环形存储结构的队列实现把数组paqu-q[MAXNUM]从逻辑上看成一个环，这种队列称为环形队列。当表中已有MAXNUM－1个结点时，如果还要插入，paqu-r和paqu-f就会重合，而这与空队列的情形相混。为区分空队列与满队列两种情况的环形队列，一般是牺牲队列中的一个结点，当队列中已有MAXNUM－1个结点时就称满，再要插入就发生溢出.paqu-rpaqu-f图(a)空队列a1a2a7a6a5a4a3paqu-fpaqu-r图(b)队列满，判断(paqu-r+1)==paqu-f环形队列顺序结构队列的类型定义顺序结构队列的操作定义（ADT）BitwiseXORIllustration101010100000000101010100kijk=i^jk=i^j^j=k深度与广度优先搜索比较深度优先搜索栈式结构空间开销小最优解需遍历所有解才能确定广度优先搜索队列结构空间开销大最先找到最优解同学补充？状态表示及状态变换（生成）用一个整数表达一个状态：109用1-8表示8个数字，9表示空位相对于x所在位置，Up,down,left,right四个位置的数字有可能移动。位置变换：+3,-3,+1,-1数值变化：(d1-d2)(ten_p(d2))-ten_p(d1))广度优先搜索的变形双向广度优先搜索双向广度优先搜索搜索顺序两个队列（分别来自初始结点和目标结点的扩展）交替扩展，每次都选择较小的一个队列进行扩展。优势扩展结点数明显减少存储需求降低条件初始状态和目标状态唯一只适用于最优解问题完全二叉树、堆、优先队列A*算法：F=G+H搜索与博弈经典游戏博弈树与极大极小过程alpha-beta剪枝棋类游戏设计概念与研究领域什么是博弈？谷歌说：百度知道：人生是永不停息的博弈过程，博弈意味着通过选择合适策略达到合意结果。作为博弈者，最佳策略是最大程度地利用游戏规则；作为社会的最佳策略，是通过规则引导社会整体福利的增加。“博弈”这个词听起来高深莫测，其实它就是“游戏”的意思。更准确点说，是可以分出胜负的游戏。博弈论如果直译就是“游戏理论”。不妨说，博弈论是通过“玩游戏”获得人生竞争知识的。研究领域博弈算法计算机的优势快速，内存大更严密人工智能领域主要研究领域挑战条件：两方、公平。博弈树双方博弈背后隐式图：我们可以把所处的局面看作是一个状态。那么博弈的过程就可以看成是在状态空间中遍历。博弈树：由于双方博弈的过程具有明显的层次关系，我们可以依此构建一棵博弈树。【图】象棋的4层博弈树博弈树博弈树上的搜索数量级极大中国象棋，平均一次40种走法,5层就有10^8个节点。只能向下搜索几层为几层后的状态给出估值自下而上依次对每个状态进行估值极大极小过程约定双方都用最好的策略把(甲方得分-乙方得分)作为一个局面的估值。MAX/MIN节点甲方：在子节点中选择估值最大的节点(MAX)。即Score(A)=Max{Ai|Ai∈F(A)}。乙方：在子节点中选择估值最小的节点(MIN)。即Score(B)=Min{Bi|Bi∈F(B)}。【图】一字棋极大极小过程【图】伪代码(极大极小算法)负极大值算法极大极小算法的改进修改了返回估值的符号避免了极大极小的交替【图】伪代码（负极大值算法）α-β剪枝α，β值MAX节点的α值：当前已经展开的几个后继节点中的最大值。它是该结点估值的下界。MIN节点的β值：当前已经展开的几个后继节点中的最小值。它是该结点估值的上界。易见规律：一个正在展开的MAX结点的α值永不下降。一个正在展开的MIN结点的β值永不上升。α-β剪枝α-β剪枝α剪枝：如果当前MIN结点的β值不大于任何祖先节点的α值，则不再继续搜索该结点。β剪枝：如果当前MAX结点的α值不小于任何祖先节点的β值，则不再继续搜索该结点。【图】α-β剪枝【图】伪代码(α剪枝)【图】伪代码(β剪枝)注意12月1号提交期中大作业！ftp162.105.80.205期中作业目录压缩包用学号命名。两人组就用两个学号命名。欢迎觉得有创新的同学直接把大作业报告发给[e-mail]