《算法設(shè)計與分析》課件 第9章 匹配與指派

算法設(shè)計與分析匹配與指派主要內(nèi)容基本概念基于圖的匈牙利算法基于矩陣的匈牙利算法基本概念：匹配基本概念：匹配例子基本概念：匹配例子基本概念：指派基本概念：指派例子矩陣模型圖模型主要內(nèi)容基本概念基于圖的匈牙利算法基于矩陣的匈牙利算法基于圖的匈牙利算法：匹配基于圖的匈牙利算法：例子基于圖的匈牙利算法：例子進(jìn)行逐個匹配，選擇匹配對(b1,w1)，(b2,w2)選取b3的匹配白點基于圖的匈牙利算法：例子基于圖的匈牙利算法：匹配增廣路徑具有以下特點基于圖的匈牙利算法：例子匹配黑點b4在匹配黑點b5

時，找不到未匹配的白點，試圖再次用增廣路徑來進(jìn)行重新匹配，圖中已經(jīng)無法找到一條增廣路徑，所以最優(yōu)匹配是4個匹配，分別是(b1,w2)，(b2,w3)，(b3,w1)，(b4,w4)，基于圖的匈牙利算法：匹配算法首先遍歷二分圖左邊部分的節(jié)點，在遍歷頂點i時，調(diào)用增廣路徑函數(shù)，試圖找到一條增廣路徑基于圖的匈牙利算法語句4-6對B部分所有頂點的visited屬性設(shè)置為0(表示未訪問)，這樣，每次尋找增廣路徑時，如果頂點的visited屬性為1，表示此頂點已經(jīng)在增廣路徑上，不能再訪問注意：增廣路徑函數(shù)augmentedPath參數(shù)一定是A部分的頂點找增廣路徑的本質(zhì)實際上就是深度優(yōu)先搜索因為深度優(yōu)先搜索的復(fù)雜度為O(n2)（二分圖），所以該算法的復(fù)雜度為O(n3)基于圖的匈牙利算法：指派基于圖的匈牙利算法：二分圖添加權(quán)重為0的邊，完全二分圖

基于圖的匈牙利算法為了解決指派問題，需要給每個節(jié)點標(biāo)注，用l(a)表給某一頂點a標(biāo)注，我們定義一個合法的標(biāo)注應(yīng)該滿足以下不等式基于圖的匈牙利算法：二分圖合法標(biāo)注平等圖基于圖的匈牙利算法：KM定理基于圖的匈牙利算法：KM定理基于圖的匈牙利算法有權(quán)二分圖上的匈牙利算法流程

基于圖的匈牙利算法可以讓A中的所有頂點的標(biāo)注都為0(l(a)=0,?a∈A)，B中頂點的標(biāo)注以所連邊的最大權(quán)重即可標(biāo)注完后，對B中的每個頂點，選擇與之相連的最大邊(如果有多條，全部選取)，從而和所有的頂點形成了一個平等圖?；趫D的匈牙利算法按照貪心算法選取即可，即對所有的邊按照從大到小進(jìn)行排序，之后依次選取可匹配邊即可，選出的邊形成了一個初始匹配如果這個初始匹配是個完美匹配，根據(jù)KM定理，最大匹配找到，算法結(jié)束，否則，就需要繼續(xù)尋找完美匹配基于圖的匈牙利算法基于圖的匈牙利算法基于圖的匈牙利算法基于圖的匈牙利算法基于圖的匈牙利算法基于圖的匈牙利算法基于圖的匈牙利算法基于圖的匈牙利算法基于圖的匈牙利算法基于圖的匈牙利算法按照KM定理，這個匹配是最大權(quán)重匹配基于圖的匈牙利算法基于圖的匈牙利算法主要內(nèi)容基本概念基于圖的匈牙利算法基于矩陣的匈牙利算法指派的數(shù)學(xué)模型指派的數(shù)學(xué)模型克尼格定理克尼格定理匈牙利算法流程找出每行的最小值，每行都減去相應(yīng)的最小值；對矩陣的每一行，找到一個0，如果這個0所有在的行和列沒有0*，則給這個0打星號0*；對矩陣的每一列，如果包含0*，則劃線；如果剛好有n條劃線，則找到最優(yōu)解，否則，執(zhí)行步驟4；尋找未被劃線覆蓋的0，如果有，則直接執(zhí)行步驟5;如果沒有，則找到所有沒有被劃線覆蓋的元素中最小元素，將最小元素加到所有劃了線的行中，并將所有未劃線的列減去此元素;將一個未被劃線覆蓋的0轉(zhuǎn)換為0′相同行不存在一個0?:找0?

所在行的0′(必然有)，再找0′所在列的0?，重復(fù)此步驟直到0′所在列再也沒有0?，對所有找到的0?

去掉?，并將所有0′轉(zhuǎn)變?yōu)??，回到步驟3；相同行存在一個0?:對這一行劃線，并取消0?

所在列的劃線，重復(fù)此步驟，直到找不出未被劃分覆蓋的0，回到步驟4匈牙利算法流程匈牙利算法流程步驟1步驟2步驟3步驟4（a）（b）（c）（d）（e）步驟5（f）匈牙利算法流程步驟5.2步驟5步驟5.1步驟3（g）（i）（j）（k）（l）步驟4（h）最優(yōu)匹配簡化匈牙利算法流程匈牙利算法的流程簡化為簡化匈牙利算法流程簡化匈牙利算法流程將所有還沒有被劃線覆蓋的元素(這些元素肯定大于0)減去最小值。此例中減去1簡化匈牙利算法流程尋找最少的劃線找到獨立的0對沒有獨立0的行打鉤尋找最少的劃線對已打√的行中所含0元素的列打√號再對所有打√的