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

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

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

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

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