馬闊

【關(guān)鍵詞】任務(wù)分配 剪枝算法 匈牙利算法 體會

1 引言

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

2 匈牙利算法及思想

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

3 基于任務(wù)分配的剪枝優(yōu)化算法的理論

3.1 剪枝算法相關(guān)理論

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

剪枝算法定義2：

，為全局最優(yōu)分配的目標函數(shù)值。

剪枝算法定義3：

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

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

3.2 剪枝算法具體步驟

根據(jù)本文的設(shè)計，剪枝優(yōu)化算法使得付出代價最小的任務(wù)分配方法步驟為：

（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，這是進行剪枝算法的操作，這樣的算法就會讓代價矩陣的規(guī)模減少一階。

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

3.3 剪枝算法實例分析

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

4 結(jié)束語

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

參考文獻

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

[2]熊焱，吳微，張超.基于灰色關(guān)聯(lián)分析的高階神經(jīng)網(wǎng)絡(luò)剪枝算法[J].大連理工大學學報，2010（03）.

[3]武彤，程輝.用遺傳算法改進的BP神經(jīng)網(wǎng)絡(luò)剪枝算法來優(yōu)化決策樹模型[J].計算機科學，2013（z2）.