KM算法是通過給每個頂點一個標號叫做頂標來把求最大

KM算法是通過給每個頂點一個標號（叫做頂標）來把求最大權匹配的問題轉化為求完備匹配的問題的。設頂點Xi的頂標為A[i]，頂點Yi的頂標為B

[i]，頂點Xi與Yj之間的邊權為w[i,j]。在算法執(zhí)行過程中的任一時刻，對于任一條邊(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關聯(lián)的邊的最大權，B[j]=0。如果當前的相等子圖沒有完備匹配，就按下面的方法修改頂標以使擴大相等子圖，直到相等子圖具有完備匹配為止。

我們求當前相等子圖的完備匹配失敗了，是因為對于某個X頂點，我們找不到一條從它出發(fā)的交錯路。這時我們獲得了一棵交錯樹，它的葉子結點全部是X頂點?，F(xiàn)在我們把交錯樹中X頂點的頂標全都減小某個值d，Y頂點的頂標全都增加同一個值d.d=min{A[i]+B[j]-w[i,j]|Xi在交錯樹中，Yi不在交錯樹中}

狀態(tài)空間搜索胡俊峰

2013-11-29狀態(tài)空間搜索適用范圍和意義盲目搜索方法優(yōu)化搜索技巧參考習題推薦材料狀態(tài)空間搜索適用范圍和意義盲目搜索方法優(yōu)化搜索技巧參考習題推薦材料狀態(tài)空間搜索適用范圍和意義盲目搜索方法優(yōu)化搜索技巧參考習題推薦材料盲目搜索方法定義狀態(tài)(state)對問題在某一時刻進展情況的數(shù)學描述狀態(tài)轉移(state-transition)問題從一種狀態(tài)到轉移到另一種（或幾種)狀態(tài)的操作狀態(tài)空間(statespace)問題可以處于的所有狀態(tài)盲目搜索算法深度優(yōu)先搜索廣度優(yōu)先搜索*隨機化搜索深度優(yōu)先搜索(Depth-firstSearch)搜索順序：1->2->4->8->…“走迷宮”

深度優(yōu)先搜索實現(xiàn)：棧式和遞歸空間開銷：棧的深度非遞歸的的實現(xiàn)框框架voidDfs(inta){while(棧不為且且尚未到到達目標標狀態(tài)){取出(pop)棧頂元素素進行擴擴展將擴展出出的元素素依次壓壓入(push)棧}}棧的應用用迷宮老老鼠解決方案案盡可能前前進，回回溯，記記錄訪問問過的狀狀態(tài)…具體：依次探查查所有可可能的沒沒有被探探查過的的方向對探查過過的位置置進行標標記無法繼續(xù)續(xù)前進則則回溯在某一位位置（i,j)進行試探探:N(i-1,j)w(i,j-1)(i,j)E(i,j+1)S(i+1,j)drection[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)四個方向向逐一進進行試探探，當選選定一個個可通行行的方向向后，把把當前所在位置置及所選的的方向記記錄下來來，然后后從下一一個位置置開始繼繼續(xù)探索索；若在在當前位位置探索索不到可可通行的的方向，，則沿原原路一步步一步退退回來，，每后退退一步，，接著在在該點試試尚未試試過的一一個方向向。如此此重復直直到到達達出口。。用一個棧棧記錄走走過的位位置，棧中每每個元素素包括三三項，分分別記錄錄當前位位置的行行坐標、、列坐標標以及在在該位置置上所選選的方向向（即directon數(shù)組的下標標值）。廣度優(yōu)先搜搜索(Breadth-firstSearch)搜索順序：：1->2->3->4->5->…廣度優(yōu)先搜搜索實現(xiàn)：隊列列空間開銷：：可擴展展結點+已擴展結點點標記廣度優(yōu)先搜搜索的實現(xiàn)現(xiàn)框架voidBFS(){while(隊列可擴展展且尚未到到達目標狀狀態(tài)){從隊首依次次取出隊列列中未擴展展的結點進進行擴展展，并將新新結點加入入隊尾。}}農(nóng)夫、狼、、羊、菜過過河狀態(tài)：<wolf,sheep,cabbage,farmer>（0，1，0，1）0，1分別代表兩兩岸操作（算符符）4種：運farmer、wolf運farmer、sheep運farmer、cabbage運farmer狀態(tài)空間大大??？24=16Map[2][2][2][2]可以轉化為為迷宮問題題？狀態(tài)=路口口操作=通路路限制條件=死胡同無形的迷宮宮。。。。。。。。。。地毯式搜索索！01234567891011121314。。。。。。。如何求得最最優(yōu)解？廣度優(yōu)先搜搜索層層推進搜索的層數(shù)數(shù)不超過答答案所在的的層數(shù)01234567891011121314。。。。。。。廣度優(yōu)先搜索索01234567891011121314。。。。。。。隊列的特點隊列是一種特殊的的線性表，只只允許在表的的一端有插入入操作，而在在另一端有刪刪除操作。隊頭：允許刪除的的這一端叫隊隊列的頭。隊尾：允許插入的的這一端叫叫隊列的尾。空隊列：當隊列中沒沒有任何元素素時，稱為空隊列。進隊/出隊：隊列的插入入操作通常稱稱為進隊列或入隊列，隊列的刪除除操作通常稱稱為退隊列或出隊列。隊列的基本概概念：隊列也稱作先先進先出表（（FirstInFirstOut，F(xiàn)IFO表）。支持隊尾尾插入，隊頭頭刪除操作。a0a1a2an-1入隊列隊頭隊尾出隊列隊列的示意圖圖隊列ADTADTQueueisoperationsQueuecreateEmptyQueue(void);//創(chuàng)建一個空隊隊列。intisEmptyQueue(Queuequ);//判隊列qu是否為空隊列列。voidenQueue(Queuequ,DataTypex);//往隊列qu尾部插入一個個值為x的元素。voiddeQueue(Queuequ);//從隊列qu頭部刪除一個個元素。DataTypefrontQueue(Queuequ);//求隊列qu頭部元素的值值。endADTQueue基于環(huán)形存儲儲結構的隊列列實現(xiàn)a1a2a3a4…anfrontrearmodMAXSIZEenQueue:{rear=(rear+1)%MAXSIZEqBuffer[rear]=inData;}deQueue:{outData=qBuffer[rear];rear=(rear+1)%MAXSIZE;}基于環(huán)形存儲儲結構的隊列列實現(xiàn)把數(shù)組paqu->q[MAXNUM]從邏輯上看成成一個環(huán)，這這種隊列稱為為環(huán)形隊列。當表中已有MAXNUM－1個結點時，如如果還要插入入，paqu->r和paqu->f就會重合，而而這與空隊列列的情形相混混。為區(qū)分空隊列列與滿隊列兩兩種情況的環(huán)環(huán)形隊列，一一般是犧牲隊隊列中的一個個結點，當隊隊列中已有MAXNUM－1個結點時就稱稱滿，再要插插入就發(fā)生溢溢出.paqu->rpaqu->f圖(a)空隊列a1a2a7a6a5a4a3paqu->fpaqu->r圖(b)隊列滿，判斷(paqu->r+1)==paqu->f環(huán)形隊列順序結構隊列列的類型定義義順序結構隊列列的操作定義義（ADT）BitwiseXORIllustration

1

0

1

0

1

0

1

0

0

0

0

0

0

0

0

1

0

1

0

1

0

1

0

0kijk=i^jk=i^j^j=k深度與廣度優(yōu)優(yōu)先搜索比較較深度優(yōu)先搜索索棧式結構空間開銷小最優(yōu)解需遍歷歷所有解才能能確定廣度優(yōu)先搜索索隊列結構空間開銷大最先找到最優(yōu)優(yōu)解同學補充？狀態(tài)表示及狀狀態(tài)變換（生生成）用一個整數(shù)表表達一個狀態(tài)態(tài)：109用1-8表示8個數(shù)字，9表示空位相對于x所在位置，Up,down,left,right四個位置的數(shù)數(shù)字有可能移移動。位置變換：+3,-3,+1,-1數(shù)值變化：(d1-d2)(ten_p(d2))-ten_p(d1))廣度優(yōu)先搜索索的變形雙向廣度優(yōu)先先搜索雙向廣度優(yōu)先先搜索搜索順序兩個隊列（分分別來自初始始結點和目標標結點的擴展展）交替擴展展，每次都選選擇較小的一一個隊列進行行擴展。優(yōu)勢擴展結點數(shù)明明顯減少存儲需求降低低條件初始狀態(tài)和目目標狀態(tài)唯一一只適用于最優(yōu)優(yōu)解問題完全二叉樹、、堆、優(yōu)先隊隊列A*算法：F=G+H搜索與博弈經(jīng)典游戲博弈樹與極大大極小過程alpha-beta剪枝棋類游戲設計計概念與研究領領域什么是博弈？？谷歌說：百度知道：人生是永不停停息的博弈過過程，博弈意意味著通過選選擇合適策略略達到合意結結果。作為博博弈者，最佳佳策略是最大大程度地利用用游戲規(guī)則；；作為社會的的最佳策略，，是通過規(guī)則則引導社會整整體福利的增增加?！安┺摹边@個詞詞聽起來高深深莫測，其實實它就是“游游戲”的意思思。更準確點點說，是可以以分出勝負的的游戲。博弈弈論如果直譯譯就是“游戲戲理論”。不不妨說，博弈弈論是通過““玩游戲”獲獲得人生競爭爭知識的。研究領域博弈算法計算機的優(yōu)勢勢快速，內存大大更嚴密人工智能領域域主要研究領域域挑戰(zhàn)條件：兩方、、公平。博弈樹雙方博弈背后后隱式圖：我們們可以把所處處的局面看作作是一個狀態(tài)態(tài)。那么博弈弈的過程就可可以看成是在在狀態(tài)空間中中遍歷。博弈樹：由于于雙方博弈的的過程具有明明顯的層次關關系，我們可可以依此構建建一棵博弈樹樹?！緢D】象棋的4層博博弈弈樹樹博弈弈樹樹博弈弈樹樹上上的的搜搜索索數(shù)量量級級極極大大中國國象象棋棋，，平平均均一一次次40種走走法法,5層就就有有10^8個節(jié)節(jié)點點。。只能能向向下下搜搜索索幾幾層層為幾幾層層后后的的狀狀態(tài)態(tài)給給出出估估值值自下下而而上上依依次次對對每每個個狀狀態(tài)態(tài)進進行行估估值值極大大極極小小過過程程約定定雙雙方方都都用用最最好好的的策策略略把(甲方方得得分分-乙方方得得分分)作為為一一個個局局面面的的估估值值。。MAX/MIN節(jié)點點甲方方：：在在子子節(jié)節(jié)點點中中選選擇擇估估值值最最大大的的節(jié)節(jié)點點(MAX)。即即Score(A)=Max{Ai|Ai∈∈F(A)}。乙方：：在子子節(jié)點點中選選擇估估值最最小的的節(jié)點點(MIN)。即Score(B)=Min{Bi|Bi∈∈F(B)}。【圖】一字棋棋極大大極小小過程程【圖】偽代碼碼(極大極極小算算法)負極大大值算算法極大極極小算算法的的改進進修改了了返回回估值值的符符號避免了了極大大極小小的交交替【圖】偽代碼碼（負負極大大值算算法））α-β剪枝α，β值MAX節(jié)點的的α值：當