二分圖匹配-匈牙利算法和km算法簡介-全文預覽
【正文】 重要的性質。同樣，把豎直方向的塊也編上號。因此，我們很自然想到了下面這種簡單的模型：以空地為頂點，有沖突的空地間連邊，我們可以得到右邊的這個圖：例題 1 Place the Robots（ ZOJ）模型一546783211 23 46578在問題的原型中，草地，墻這些信息不是我們所關心的，我們關心的只是空地和空地之間的聯(lián)系。在同一行或同一列的兩個機器人，若它們之間沒有墻，則它們可以互相攻擊。然后調整 lx和 ly：對于訪問過的 x頂點，將它的可行標減去 d，對于所有訪問過的 y頂點，將它的可行標增加 d。證明很容易。v實際模型：某公司有職員 x1,x2,…,x n,他們去做工作 y1,y2,…,y n,每個職員做各項工作的效益未必一致，需要制定一個分工方案，使得人盡其才，讓公司獲得的總效益最大。vBmatch := 0。v until stsf。v exit。v i := t。v while true dov beginv t := match1[j]。v repeat匈牙利算法v for i:=1 to n dov if (father[i]=0)and(a[queue[st],i]=1) thenv beginv if match2[i]0 thenv beginv inc(sf)。v beginv queue[1] := k。v3－ M為 G的最大匹配當且僅當不存在相對于M的增廣路徑。因此，需要尋求一種更加高效的算法。 112233445最大匹配v給定一個二分圖 G，在 G的一個子圖 M中， M的邊集 {E}中的任意兩條邊都不依附于同一個頂點，則稱 M是一個匹配。二分圖匹配匈牙利算法和 KM算法簡介二分圖的概念v二分圖又稱作二部圖，是圖論中的一種特殊模型。則稱圖 G為二分圖。但是這個算法的復雜度為邊數(shù)的指數(shù)級函數(shù)。v2－ P經(jīng)過取反操作可以得到一個更大的匹配M’。v
研究報告相關推薦
鄂ICP備17016276號-1