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

,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,KM算法是,通,通过给,每,每个顶,点,点一个,标,标号（,叫,叫做顶,标,标）来,把,把求最,大,大权匹,配,配的问,题,题转化,为,为求完,备,备匹配,的,的问题,的,的。设,顶,顶点Xi的顶标,为,为Ai,，顶点Yi的顶标,为,为Bi，顶点Xi与Yj之间的,边,边权为wi,j。在算,法,法执行,过,过程中,的,的任一,时,时刻，,对,对于任,一,一条边(i,j)，Ai,+B,j,=w,i,j始终,成,成立。KM算法的,正,正确性,基,基于以,下,下定理,：,：,若,若,由,由二分,图,图中所,有,有满足Ai,+B,j,=,=wi,j,的边(i,j)构成的,子,子图（,称,称做相,等,等子图,）,）有完,备,备匹配,，,，那么,这,这个完,备,备匹配,就,就是二,分,分图的,最,最大权,匹,匹配。,初,初始,时,时为了,使,使Ai,+B,j,=w,i,j恒成立,，,，令Ai,为所有,与,与顶点Xi关联的,边,边的最,大,大权，Bj,=0。如果,当,当前的,相,相等子,图,图没有,完,完备匹,配,配，就,按,按下面,的,的方法,修,修改顶,标,标以使,扩,扩大相,等,等子图,，,，直到,相,相等子,图,图具有,完,完备匹,配,配为止,。,。,我,我,们,们求当,前,前相等,子,子图的,完,完备匹,配,配失败,了,了，是,因,因为对,于,于某个X顶点，,我,我们找,不,不到一,条,条从它,出,出发的,交,交错路,。,。这时,我,我们获,得,得了一,棵,棵交错,树,树，它,的,的叶子,结,结点全,部,部是X顶点。,现,现在我,们,们把交,错,错树中X顶点的,顶,顶标全,都,都减小,某,某个值d，Y顶点的,顶,顶标全,都,都增加,同,同一个,值,值d.,d =minAi,+B,j,-,-wi,j, |Xi在交错,树,树中，Yi不在交,错,错树中,状态空,间,间搜索,胡俊峰,2013-11-29,状态空,间,间搜索,适用范,围,围和意,义,义,盲目搜,索,索方法,优化搜,索,索技巧,参考习,题,题,推荐材,料,料,状态空,间,间搜索,适用范,围,围和意,义,义,盲目搜,索,索方法,优化搜,索,索技巧,参考习,题,题,推荐材,料,料,状态空,间,间搜索,适用范,围,围和意,义,义,盲目搜,索,索方法,优化搜,索,索技巧,参考习,题,题,推荐材,料,料,盲目搜,索,索方法,定义,状态(state,),),对问题,在,在某一,时,时刻进,展,展情况,的,的数学,描,描述,状态转,移,移(state,-,-transition),问题从,一,一种状,态,态到转,移,移到另,一,一种（,或,或几种)状态的,操,操作,状态空,间,间(statespace,),),问题可,以,以处于,的,的所有,状,状态,盲目搜,索,索算法,深度优,先,先搜索,广度优,先,先搜索,*随机,化,化搜索,深度优,先,先搜索(Depth,-,-firstSearch),搜索顺,序,序：1-2-4-8-,“走迷宫,”,”,深度优,先,先搜索,实现：,栈,栈式和,递,递归,空间开,销,销：,栈,栈的深,度,度,非递归,的,的实现,框,框架,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 +directionk,1,;,算法设,计,计,走一步,，,，记一,步,步。,方向试,探,探,前进push (current),无法前,进,进current,=,= pop,(,( ),求解迷,宫,宫中一,条,条路径,的,的方法,：,：,从入口,开,开始，,对,对每个当前位,置,置沿（E,S,W,N)四个方,向,向逐一,进,进行试,探,探，当,选,选定一,个,个可通,行,行的方,向,向后，,把,把当前所在位,置,置及所选,的,的方向,记,记录下,来,来，然,后,后从下,一,一个位,置,置开始,继,继续探,索,索；若,在,在当前,位,位置探,索,索不到,可,可通行,的,的方向,，,，则沿,原,原路一,步,步一步,退,退回来,，,，每后,退,退一步,，,，接着,在,在该点,试,试尚未,试,试过的,一,一个方,向,向。如,此,此重复,直,直到到,达,达出口,。,。,用一个,栈,栈记录,走,走过的,位,位置，栈中,每,每个元,素,素包括,三,三项，,分,分别记,录,录当前,位,位置的,行,行坐标,、,、列坐,标,标以及,在,在该位,置,置上所,选,选的方,向,向（即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,状态空,间,间大小,？,？24=16,Map,2,2,2,2,可以转,化,化为迷,宫,宫问题,？,？,状态=,路,路口,操作=,通,通路,限制条,件,件=死,胡,胡同,无形的,迷,迷宫。,。,。,。,。,。,地毯式,搜,搜索！,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,。,。,。,如何求,得,得最优,解,解？,广度优,先,先搜索,层层推,进,进,搜索的,层,层数不,超,超过答,案,案所在,的,的层数,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,。,。,。,广度优,先,先搜索,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,。,。,。,队列的,特,特点,队列是一种,特,特殊的,线,线性表,，,，只允,许,许在表,的,的一端,有,有插入,操,操作，,而,而在另,一,一端有,删,删除操,作,作。,队头：允许,删,删除的,这,这一端,叫,叫队列,的,的头。,队尾：允许,插,插入的,这,这一,端,端叫队,列,列的尾。,空队列：当队,列,列中没,有,有任何,元,元素时,，,，称为空队列。,进队/出队：队列,的,的插入,操,操作通,常,常称为进队列或入队列，队列,的,的删除,操,操作通,常,常称为退队列或出队列。,队列的,基,基本概,念,念：,队列也,称,称作先,进,进先出,表,表（FirstInFirstOut，FIFO表）。支,持,持队尾,插,插入，,队,队头删,除,除操作,。,a,0,a,1,a,2,a,n-1,入队列,队头,队尾,出队列,队列的,示,示意图,队列ADT,ADTQueueis,operations,QueuecreateEmptyQueue (void ),;,;,/,/创建一,个,个空队,列,列。,intisEmptyQueue (Queuequ,),);,/,/判队列qu是否为,空,空队列,。,。,void enQueue,(,(Queuequ,DataTypex,),);,/往队列qu尾部插,入,入一个,值,值为x的元素,。,。,void deQueue,(,(Queuequ,),);,/,/从队列qu头部删,除,除一个,元,元素。,DataTypefrontQueue (Queuequ,),);,/,/,/,/求队列qu头部元,素,素的值,。,。,endADTQueue,基于环,形,形存储,结,结构的,队,队列实,现,现,a1,a2,a3,a4,an,front,rear,modMAXSIZE,enQueue:,rear =,(,(rear,+,+1)%MAXSIZE,qBufferrear, =inData;,deQueue:,outData =qBufferrear;,rear =,(,(rear,+,+1)%MAXSIZE ;,基于环,形,形存储,结,结构的,队,队列实,现,现,把数组paqu-qMAXNUM从逻辑,上,上看成,一,一个环,，,，这种,队,队列称,为,为环形队,列,列。,当表中,已,已有MAXNUM1个结点,时,时，如,果,果还要,插,插入，,paqu-r和paqu-f就会重,合,合，而,这,这与空,队,队列的,情,情形相,混,混。,为区分,空,空队列,与,与满队,列,列两种,情,情况的,环,环形队,列,列，一,般,般是牺,牲,牲队列,中,中的一,个,个结点,，,，当队,列,列中已,有,有MAXNUM1个结点,时,时就称,满,满，再,要,要插入,就,就发生,溢,溢出.,paqu-r,paqu-f,图,(a),空队列,a,1,a,2,a,7,a,6,a,5,a,4,a,3,paqu-f,paqu-r,图,(b),队列满，判断,(,paqu-r,+1) = =,paqu-f,环形队,列,列,顺序结,构,构队列,的,的类型,定,定义,顺序结,构,构队列,的,的操作,定,定义（ADT）,Bitwise XORIllustration,1,0,1,0,1,0,1,0,0,0,0,0,0,0,0,1,0,1,0,1,0,1,0,0,k,i,j,k =i,j,k =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层就有108个节点,。,。,只能向,下,下搜索,几,几层,为几层,后,后的状,态,态给出,估,估值,自下而,上,上依次,对,对每个,状,状态进,行,行估值,极大极,小,小过程,约定双,方,方都用,最,最好的,策,策略,把(甲方得,分,分-乙方得,分,分)作为一,个,个局面,的,的估值,。,。,MAX,/,/MIN节点,甲方：,在,在子节,点,点中选,择,择估值,最,最大的,节,节点(MAX)。即Score(A),=,= MaxAi|Ai,F,(,(A),。,乙方：,在,在子节,点,点中选,择,择估值,最,最小的,节,节点(MIN)。,即Score(B),=,= MinBi|Bi,F,(,(B),。,【图】一字棋,极,极大极,小,小过程,【图】伪代码,(极大极,小,小算法),负极大,值,值算法,极大极,小,小算法,的,的改进,修改了,返,返回估,值,值的符,号,号,避免了,极,极大极,小,小的交,替,替,【图】伪代码,（,（负极,大,大值算,法,法）,-剪枝,，值,MAX节点的值：当,前,前已经,展,展开的,几,几个后,继,继节点,中,中的最,大,大值。,它,它是该,结,结点估,值,值的下,界,界。,MIN节点的值：当,前,前已经,展,展开的,几,几个后,继,继节点,中,中的最,小,小值。,它,它是该,结,结点估,值,值的上,界,界。,易见规,律,律：,一个正,在,在展开,的,的MAX结点的值永不下,降,降。,一个正,在,在展开,的,的MIN结点的值永不上,升,升。,-剪枝,-剪枝,剪枝：,如,如果当,前,前MIN结点的值不大,于,于任何,祖,祖先节,点,点的值，则,不,不再继,续,续搜索,该,该结点,。,。,剪枝：,如,如果当,前,前MAX结点的值不小,于,于任何,祖,祖先节,点,点的值，则,不,不再继,续,续搜索,该,该结点,。,。,【图】-剪枝,【图】伪代码,(剪枝),【图】伪代码,(剪枝),注意12月1号提交,期,期中大,作,作业！,ftp162.105,.,.80,.,.205期中作,业,业 目,录,录,压缩包,用,用学号,命,命名。,两人组,就,就用两,个,个学号,命,命名。,欢迎觉,得,得有创,新,新的同,学,学直接,把,把大作,业,业报告,发,发给hujfpku.edu,.,.cn,