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