基于任務分配的剪枝算法優化體會

馬闊

【關鍵詞】任務分配 剪枝算法 匈牙利算法 體會

1 引言

隨著科技的不斷發展與進步，人們的生活節奏也在加快，低效率的工作不能夠很好的適應現代社會發展，因此過去慢節奏的工作方式已經被新方法所取代。在我們的日常工作中，常會面臨任務分配的問題，例如工作任務的分配；各小組之間的分配等，這樣的問題通常會用有多項任務讓多個人去完成，不同的人執行的效率不同得到的效果也不同，要確定出最合適的分配方案，才能讓整個的任務得到圓滿的完成，還能使整體任務付出的成本最小。其實這類的問題在很多領域中都可以見到，比如教育課程的分配、軍事應用的武器分配、勞動生產分配問題等等，過去此類的問題常會利用匈牙利算法進行解決，但是隨著匈牙利算法運算效率的降低，研究人員又提出了一種新的解決方法就是基于任務分配的剪枝算法，此算法提高了任務分配的速度與效率，本文就對匈牙利算法思想以及基于任務分配的剪枝算法進行具體的分析。

2 匈牙利算法及思想

匈牙利算法主要應用于指派問題上，比如車床加工問題，n個零件在m臺車床上加工，每個零件的加工時間與成本不同，那么最佳的任務分配就是要讓此任務的總成本最低。匈牙利算法在進行分配任務求解的時候，會對原代價矩陣進行多次的改變，讓原代價矩陣變成有很多0元素的新代價矩陣，將矩陣C的所有元素劃分為0和非0，得到不同行不同列的0元素最大數目與0元素最少的直線數相等。匈牙利算法在進行簡化的過程中為了達到行列減少的目的，會對成本矩陣進行迭代并且多次對零元素進行尋找、選擇與刪除，這樣一來使得邏輯變得復雜，運算效率也慢慢降低。因此重新分析任務分配問題的特點提出了一種新的快速優化算法——剪枝算法。

3 基于任務分配的剪枝優化算法的理論

3.1 剪枝算法相關理論

剪枝優化算法也稱為快速降階優化算法，其目的就是將矩陣快速降階，實現操作簡單化。剪枝算法定義1：，，顯然，1與2分別為部分分配=1或=1的降價指派問題。1，2包含于。

剪枝算法定義2：

，為全局最優分配的目標函數值。

剪枝算法定義3：

。將確定好的部分分配方案的代價元素值設為0，C1與C2的計算為：

，這時C1的0元素不能再進行分配，E1求解無人機對對個目標的任務分配問題，將空間變小這就稱為剪枝算法。如果代價值最大就是最佳的任務分配指標，那么選擇=1就是最佳方案的解，將其對應的行與列去除，就成為降級了一階的求解方案，按照以上方法進行，直到代價矩陣剩下一個元素，即整個任務分配得到最佳的解決方案。

3.2 剪枝算法具體步驟

根據本文的設計，剪枝優化算法使得付出代價最小的任務分配方法步驟為：

（1）初始化=1，i，j=1，2，3，4……，n。

（2）條件滿足L=argmax（-）X k≠m；i，k，m=1，2，3……n的行號，然后選擇=1，同時將標記成true，即為選中。

（3）剪枝算法，讓然后將與之同行列的元素標記成false，這是進行剪枝算法的操作，這樣的算法就會讓代價矩陣的規模減少一階。

（4）降低了一階的代價矩陣中如果有沒有進行標記的矩陣，就可以重復這些步驟，直到代價矩陣變為最低的1×1矩陣并且標記為true，任務分配問題得到解決。通過以上算法的分析不難看出，在利用剪枝算法進行求解矩陣分配問題的時候，要用循環進行（n-1）次操作得到解，本文的基于任務分配的剪枝算法經過分析使計算的邏輯性得到簡化，是一種實現了邏輯簡單，高效率的計算方法。

3.3 剪枝算法實例分析

對于比較常見的指派問題，如果各主體間的代價矩陣給出了數據，利用文中的剪枝優化算法，經過多次的剪枝就能得到最佳的任務分配方案，并且每一步的剪枝都能夠得相應的解。需要說明：剪枝算法也有一定的缺陷，即它的適用范圍只能用于求解代價矩陣的元素，并且其中元素不能出現負值。一旦代價矩陣中正負數都有時，讓先找出最小的負數，然后將每一個代價元素增加相同的正數，這樣就有效解決了代價矩陣中都為非負值的條件，最后就可以利用上文中的剪枝算法對問題進行求解，可以看出，相比于匈牙利算法，剪枝優化算法才是對矩陣元素增加正數卻并不影響問題解決的最佳方式。

4 結束語

綜上所述，本文開始對匈牙利算法與思想進行簡要的分析，然后由匈牙利算法的低效率引申出一種更好解決任務分配問題的新算法，即剪枝優化算法，再對剪枝算法的定義與步驟進行詳細的說明，得出剪枝算法是最佳的解決方法，它將求解的范圍慢慢變小得出解答，有效的節省了運算時間，降低了負載率，也提高了計算機的利用率，相信未來基于任務分配的剪枝算法會得到更多的應用，獲得更大的發展。

參考文獻

[1]陸洋，施侃樂，雍俊海.細分法求解點投影問題時的剪枝算法[J].計算機輔助設計與圖形學學報，2014（04）.

[2]熊焱，吳微，張超.基于灰色關聯分析的高階神經網絡剪枝算法[J].大連理工大學學報，2010（03）.

[3]武彤，程輝.用遺傳算法改進的BP神經網絡剪枝算法來優化決策樹模型[J].計算機科學，2013（z2）.