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