km算法是通過給每個頂點一個標(biāo)號(叫做頂標(biāo))來把求最大(已修改)
2025-01-19 08:26 本頁面
【正文】 n KM算法是通過給每個頂點一個標(biāo)號（叫做頂標(biāo)）來把求最大權(quán)匹配的問題轉(zhuǎn)化為求完備匹配的問題的。設(shè)頂點 Xi的頂標(biāo)為 A[i]，頂點 Yi的頂標(biāo)為B[i]，頂點 Xi與 Yj之間的邊權(quán)為 w[i,j]。在算法執(zhí)行過程中的任一時刻，對于任一條邊 (i,j)， A[i]+B[j]=w[i,j]始終 成立。 KM算法的正確性基于以下定理： 若由二分圖中所有滿足 A[i]+B[j]=w[i,j]的邊 (i,j)構(gòu)成的子圖（稱做相等子圖）有完備匹配，那么這個完備匹配就是二分圖的最大權(quán)匹配?！ 〕跏紩r為了使 A[i]+B[j]=w[i,j]恒成立，令 A[i]為所有與頂點 Xi關(guān)聯(lián)的邊的最大權(quán)， B[j]=0。如果當(dāng)前的相等子圖沒有完備匹配，就按下面的方法修改頂標(biāo)以使擴大相等子圖，直到相等子圖具有完備匹配為止?！ ∥覀兦螽?dāng)前相等子圖的完備匹配失敗了，是因為對于某個 X頂點，我們找不到一條從它出發(fā)的交錯路。這時我們獲得了一棵交錯樹，它的葉子結(jié)點全部是 X頂點?，F(xiàn)在我們把交錯樹中 X頂點的頂標(biāo)全都減小某個值 d， Y頂點的頂標(biāo)全都增加同一個值 d.n d=min{A[i]+B[j]w[i,j]|Xi在交錯樹中， Yi不在交錯樹中 }狀態(tài)空間搜索胡俊峰20231129狀態(tài)空間搜索n 適用范圍和意義n 盲目搜索方法n 優(yōu)化搜索技巧n 參考習(xí)題n 推薦材料狀態(tài)空間搜索n 適用范圍和意義n 盲目搜索方法n 優(yōu)化搜索技巧n 參考習(xí)題n 推薦材料狀態(tài)空間搜索n 適用范圍和意義n 盲目搜索方法n 優(yōu)化搜索技巧n 參考習(xí)題n 推薦材料盲目搜索方法n 定義狀態(tài) (state)對問題在某一時刻進展情況的數(shù)學(xué)描述狀態(tài)轉(zhuǎn)移 (statetransition)問題從一種狀態(tài)到轉(zhuǎn)移到另一種（或幾種 )狀態(tài)的操作狀態(tài)空間 (statespace)問題可以處于的所有狀態(tài)盲目搜索算法n 深度優(yōu)先搜索n 廣度優(yōu)先搜索n *隨機化搜索深度優(yōu)先搜索 (DepthfirstSearch)搜索順序： 1248…“走迷宮 ”深度優(yōu)先搜索n 實現(xiàn)：棧式和遞歸n 空間開銷： 棧的深度非遞歸的實現(xiàn)框架voidDfs(inta){while(棧不為且尚未到達目標(biāo)狀態(tài) ){ 取出 (pop)棧頂元素進行擴展將擴展出的元素依次壓入 (push)棧}}棧的應(yīng)用迷宮老鼠解決方案n 盡可能前進，回溯，記錄訪問過的
外語相關(guān)推薦
鄂ICP備17016276號-1