it技術(shù)《匈牙利算法和km算法簡介》-文庫吧
2025-04-26 16:19 本頁面
【正文】 er),0)。 ? 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)。 ? queue[sf] := match2[i]。 ? father[i] := queue[st]。 ? end else 匈牙利算法 ? begin ? j := queue[st]。 ? while true do ? begin ? t := match1[j]。 ? match1[j] := i。 ? match2[i] := j。 ? if t = 0 then break。 ? i := t。 j := father[t]。 匈牙利算法 ? end。 ? find := 1。 ? exit。 ? end。 ? end。 ? inc(st)。 ? until stsf。 ? find := 0。 ? end。 匈牙利算法 ?在主程序中調(diào)用下面的程序即可得出最大匹配數(shù)。 ? Bmatch := 0。 ? For I:=1 to n do Bmatch := Bmatch + find(i)。 ? Writeln(Bmatch)。 ?一個關(guān)于二分圖的性質(zhì)： ?最大匹配數(shù)＋最大獨(dú)立集＝ X＋ Y 最佳匹配 ?如果邊上帶權(quán)的話，找出權(quán)和最大的匹配叫做求最佳匹配。 ?實際模型：某公司有職員 x1,x2,…,x n,他們?nèi)プ龉ぷ?y1,y2,…,y n,每個職員做各項工作的效益未必一致，需要制定一個分工方案，使得人盡其才，讓公司獲得的總效益最大。 ?數(shù)學(xué)模型： G是加權(quán)完全二分圖，求總權(quán)值最大的完備匹配。 KM算法 ?窮舉的效率－ n！，我們需要更加優(yōu)秀的算法。 ?定理： ?設(shè) M是一個帶權(quán)完全二分圖
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1