帶回溯的Kuhn-Munkres多對多指派算法研究.pdf

1、本文的目的在于解決多對多的指派問題。在現(xiàn)實(shí)生活和生產(chǎn)管理中，都會出現(xiàn)資源調(diào)度、任務(wù)分配、作業(yè)分配等問題，例如，如何制定公交/地鐵的時(shí)刻安排表，如何分配任務(wù)給員工等使得利益/效率最大化(最小化)。這類問題其實(shí)就是根據(jù)代理的能力或?qū)ｉL等，指派代理去擔(dān)任某項(xiàng)任務(wù)。如何指派任務(wù)給代理，使得完成所有任務(wù)所需要的時(shí)間最小或效率最高的問題稱為指派問題。指派問題的解決方法有多種，常用的經(jīng)典高效方法是KM算法，但是KM算法只能解決一對一或一對多的指派問題

2、，不能解決多對多的指派問題。多對多的指派問題則允許一個(gè)代理執(zhí)行多項(xiàng)任務(wù)，而一個(gè)任務(wù)可以指派給多個(gè)代理執(zhí)行。在生活中，多對多的指派問題非常普遍，而且多對多指派問題還是開問題。
　　為了解決多對多的指派問題，本文引入了二分圖和匹配的相關(guān)理論知識，并對其進(jìn)行了分析介紹，給出了K-M定理并討論了KM算法及其計(jì)算過程。接著，對多對多的指派問題進(jìn)行形式化描述定義，但是多對多指派問題的二分圖是一個(gè)二階結(jié)構(gòu)，為了減少多對多二分圖的二階問題的復(fù)雜度

3、，我們把其進(jìn)行擴(kuò)展成為一階的層次結(jié)構(gòu)，并通過二分圖的最優(yōu)化定理證明了多對多二分圖最大權(quán)匹配。然后在 KM算法的基礎(chǔ)上進(jìn)行了改進(jìn)，并引入了回溯的機(jī)制，從而提出了解決多對多指派問題的算法-KMB算法。對 KMB算法的實(shí)現(xiàn)步驟進(jìn)行了詳細(xì)描述，給出了 KMB算法的偽代碼以及算法流程圖，并通過KMB算法的流程圖證明該算法的時(shí)間復(fù)雜度為O(m3)。討論了KMB算法中遇到的關(guān)鍵問題：KMB回溯中的負(fù)數(shù)問題，并證明其不會對KMB的指派問題產(chǎn)生影響。

4、r>　　最后，本文使用KMB算法對指派問題進(jìn)行了隨機(jī)仿真實(shí)驗(yàn)，通過觀察多對多指派問題，我們注意到如果多對多指派問題沒有可行解，那么它并沒有停止運(yùn)行而是進(jìn)入了死循環(huán)。通過分析后給出了KMB處理的充分必要條件-基數(shù)約束檢測，并對給出對其的證明過程，對加入了充分必要條件的KMB算法進(jìn)行了隨機(jī)仿真實(shí)驗(yàn)，從而驗(yàn)證了該算法有效性和適用性，并且該算法高效。KMB算法解決了多對多的指派問題，為資源調(diào)度、作業(yè)分配、任務(wù)分配等指派工作提供了一個(gè)高效的解決方