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

1、KM算法是通通过给每每个顶点点一个标标号（叫叫做顶标标）来把把求最大大权匹配配的问题题转化为为求完备备匹配的的问题的的。设顶顶点Xi的顶标为为Ai，顶点Yi的顶标为为Bi，顶点Xi与Yj之间的边边权为wi,j。在算法法执行过过程中的的任一时时刻，对对于任一一条边(i,j)，Ai+Bj=wi,j始终成成立。KM算法的正正确性基基于以下下定理：若若由由二分图图中所有有满足Ai+Bj=wi,j的边(i,j)构成的子子图（称称做相等等子图）有完备备匹配，那么这这个完备备匹配就就是二分分图的最最大权匹匹配。初初始时时为了使使Ai+Bj=wi,j恒成立，令Ai为所有与与顶点Xi关联的边边的最大大权，Bj=

2、0。如果当当前的相相等子图图没有完完备匹配配，就按按下面的的方法修修改顶标标以使扩扩大相等等子图，直到相相等子图图具有完完备匹配配为止。我我们们求当前前相等子子图的完完备匹配配失败了了，是因因为对于于某个X顶点，我我们找不不到一条条从它出出发的交交错路。这时我我们获得得了一棵棵交错树树，它的的叶子结结点全部部是X顶点。现现在我们们把交错错树中X顶点的顶顶标全都都减小某某个值d，Y顶点的顶顶标全都都增加同同一个值值d.d =minAi+Bj-wi,j |Xi在交错树树中，Yi不在交错错树中状态空间间搜索胡俊峰2013-11-29状态空间间搜索适用范围围和意义义盲目搜索索方法优化搜索索技巧参考习题

3、题推荐材料料状态空间间搜索适用范围围和意义义盲目搜索索方法优化搜索索技巧参考习题题推荐材料料状态空间间搜索适用范围围和意义义盲目搜索索方法优化搜索索技巧参考习题题推荐材料料盲目搜索索方法定义状态(state)对问题在在某一时时刻进展展情况的的数学描描述状态转移移(state-transition)问题从一一种状态态到转移移到另一一种（或或几种)状态的操操作状态空间间(statespace)问题可以以处于的的所有状状态盲目搜索索算法深度优先先搜索广度优先先搜索*随机化化搜索深度优先先搜索(Depth-firstSearch)搜索顺序序：1-2-4-8-“走迷宫”深度优先先搜索实现：栈栈式和递递归

4、空间开销销：栈栈的深度度非递归的的实现框框架void Dfs(inta)while(栈不为且且尚未到到达目标标状态)取出(pop)栈顶元素素进行扩扩展将扩展出出的元素素依次压压入(push)栈栈的应用用迷宫老老鼠解决方案案尽可能前前进，回回溯，记记录访问问过的状状态具体：依次探查查所有可可能的没没有被探探查过的的方向对探查过过的位置置进行标标记无法继续续前进则则回溯在某一位位置（i,j)进行试探探:N(i-1,j)w(i,j-1)(i,j)E(i,j+1)S(i+1,j)drection42令k取0,1,2,3之一，则则试探位位置为：g =i+ directionk0;h=j +directi

5、onk1;算法设计计走一步，记一步步。方向试探探前进push (current)无法前进进current= pop( )求解迷宫宫中一条条路径的的方法：从入口开开始，对对每个当前位置置沿（E,S,W,N)四个方向向逐一进进行试探探，当选选定一个个可通行行的方向向后，把把当前所在位置置及所选的的方向记记录下来来，然后后从下一一个位置置开始继继续探索索；若在在当前位位置探索索不到可可通行的的方向，则沿原原路一步步一步退退回来，每后退退一步，接着在在该点试试尚未试试过的一一个方向向。如此此重复直直到到达达出口。用一个栈栈记录走走过的位位置，栈中每每个元素素包括三三项，分分别记录录当前位位置的行行坐标

6、、列坐标标以及在在该位置置上所选选的方向向（即directon数组的下下标值）。广度优先先搜索(Breadth-firstSearch)搜索顺序序：1-2-3-4-5-广度优先先搜索实现：队队列空间开销销：可可扩展结结点+已扩展结结点标记记广度优先先搜索的的实现框框架void BFS()while(队列可扩扩展且尚尚未到达达目标状状态)从队首依依次取出出队列中中未扩展展的结点点进行扩扩展，并将新新结点加加入队尾尾。农夫、狼狼、羊、菜过河河状态：（0，1，0，1）0，1分别代表表两岸操作（算算符）4种：运farmer、wolf运farmer、sheep运farmer、cabbage运farmer

7、状态空间间大小？24=16Map2222可以转化化为迷宫宫问题？状态=路路口操作=通通路限制条件件=死胡胡同无形的迷迷宫。地毯式搜搜索！01234567891011121314。如何求得得最优解解？广度优先先搜索层层推进进搜索的层层数不超超过答案案所在的的层数01234567891011121314。广度优先先搜索01234567891011121314。队列的特特点队列是一种特特殊的线线性表，只允许许在表的的一端有有插入操操作，而而在另一一端有删删除操作作。队头：允许删删除的这这一端叫叫队列的的头。队尾：允许插插入的这这一端端叫队列列的尾。空队列：当队列列中没有有任何元元素时，称为空队列。进

8、队/出队：队列的的插入操操作通常常称为进队列或入队列，队列的的删除操操作通常常称为退队列或出队列。队列的基基本概念念：队列也称称作先进进先出表表（FirstInFirstOut，FIFO表）。支持持队尾插插入，队队头删除除操作。a0a1a2an-1入队列队头队尾出队列队列的示示意图队列ADTADTQueueisoperationsQueuecreateEmptyQueue (void );/创建一个个空队列列。intisEmptyQueue (Queuequ);/判队列qu是否为空空队列。void enQueue(Queuequ,DataTypex);/往队列qu尾部插入入一个值值为x的元素。

9、void deQueue(Queuequ);/从队列qu头部删除除一个元元素。DataTypefrontQueue (Queuequ);/求队列qu头部元素素的值。endADTQueue基于环形形存储结结构的队队列实现现a1a2a3a4anfrontrearmodMAXSIZEenQueue:rear =(rear+1)%MAXSIZEqBufferrear =inData;deQueue:outData =qBufferrear;rear =(rear+1)%MAXSIZE ;基于环形形存储结结构的队队列实现现把数组paqu-qMAXNUM从逻辑上上看成一一个环，这种队队列称为为环形队列列。

10、当表中已已有MAXNUM1个结点时时，如果果还要插插入，paqu-r和paqu-f就会重合合，而这这与空队队列的情情形相混混。为区分空空队列与与满队列列两种情情况的环环形队列列，一般般是牺牲牲队列中中的一个个结点，当队列列中已有有MAXNUM1个结点时时就称满满，再要要插入就就发生溢溢出.paqu-rpaqu-f图(a)空队列a1a2a7a6a5a4a3paqu-fpaqu-r图(b)队列满，判断(paqu-r +1) = = paqu-f环形队列列顺序结构构队列的的类型定定义顺序结构构队列的的操作定定义（ADT）Bitwise XORIllustration 1 0 1 0 1 0 1 0

11、0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0kijk =ijk =ij j= k深度与广广度优先先搜索比比较深度优先先搜索栈式结构构空间开销销小最优解需需遍历所所有解才才能确定定广度优先先搜索队列结构构空间开销销大最先找到到最优解解同学补充充？状态表示示及状态态变换（生成）用一个整整数表达达一个状状态：109用1-8表示8个数字，9表示空位位相对于x所在位置置，Up,down,left,right四个位置置的数字字有可能能移动。位置变换换：+3,-3,+1,-1数值变化化：(d1-d2)(ten_p(d2)-ten_p(d1)广度优先先搜索的的变形双向广度度优先搜搜索双向广度

12、度优先搜搜索搜索顺序序两个队列列（分别别来自初初始结点点和目标标结点的的扩展）交替扩扩展，每每次都选选择较小小的一个个队列进进行扩展展。优势扩展结点点数明显显减少存储需求求降低条件初始状态态和目标标状态唯唯一只适用于于最优解解问题完全二叉叉树、堆堆、优先先队列A*算法：F =G+ H搜索与博博弈经典游戏戏博弈树与与极大极极小过程程alpha-beta剪枝棋类游戏戏设计概念与研研究领域域什么是博博弈？谷歌说：百度知道道：人生是永永不停息息的博弈弈过程，博弈意意味着通通过选择择合适策策略达到到合意结结果。作作为博弈弈者，最最佳策略略是最大大程度地地利用游游戏规则则；作为为社会的的最佳策策略，是是通

13、过规规则引导导社会整整体福利利的增加加。“博弈”这这个词听听起来高高深莫测测，其实实它就是是“游戏戏”的意意思。更更准确点点说，是是可以分分出胜负负的游戏戏。博弈弈论如果果直译就就是“游游戏理论论”。不不妨说，博弈论论是通过过“玩游游戏”获获得人生生竞争知知识的。研究领域域博弈算法法计算机的的优势快速，内内存大更严密人工智能能领域主要研究究领域挑战条件：两两方、公公平。博弈树双方博弈弈背后隐式图：我们可可以把所所处的局局面看作作是一个个状态。那么博博弈的过过程就可可以看成成是在状状态空间间中遍历历。博弈树：由于双双方博弈弈的过程程具有明明显的层层次关系系，我们们可以依依此构建建一棵博博弈树。【

14、图】象棋的4层博弈树树博弈树博弈树上上的搜索索数量级极极大中国象棋棋，平均均一次40种走法,5层就有108个节点。只能向下下搜索几几层为几层后后的状态态给出估估值自下而上上依次对对每个状状态进行行估值极大极小小过程约定双方方都用最最好的策策略把(甲方得分分-乙方得分分)作为一个个局面的的估值。MAX/MIN节点甲方：在在子节点点中选择择估值最最大的节节点(MAX)。即Score(A)= MaxAi|AiF(A)。乙方：在在子节点点中选择择估值最最小的节节点(MIN)。即Score(B)= MinBi|BiF(B)。【图】一字棋极极大极小小过程【图】伪代码(极大极小小算法)负极大值值算法极大极小小算法的的改进修改了返返回估值值的符号号避免了极极大极小小的交替替【图】伪代码（负极大大值算法法）-剪枝，值MAX节点的值：当前前已经展展开的几几个后继继节点中中的最大大值。它它是该结结点估值值的下界界。MIN节点的值：当前前已经展展开的几几个后继继节点中中的最小小值。它它是该结结点估值值的上界界。易见规律律：一个正在在展开的的MAX结点的值永不下降降。一个正在在展开的的