本文關(guān)鍵詞：匈牙利算法，由筆耕文化傳播整理發(fā)布。

【算法題】任務(wù)分配問題---匈牙利算法

一、問題描述

問題描述：N個人分配N項任務(wù)，一個人只能分配一項任務(wù)，一項任務(wù)只能分配給一個人，將一項任務(wù)分配給一個人是需要支付報酬，如何分配任務(wù)，保證支付的報酬總數(shù)最小。

問題數(shù)學(xué)描述：

二、實例分析---窮舉法

在講將匈牙利算法解決任務(wù)問題之前，先分析幾個具體實例。

以3個工作人員和3項任務(wù)為實例，下圖為薪酬圖表和根據(jù)薪酬圖表所得的cost矩陣。

利用最簡單的方法(窮舉法)進行求解，計算出所有分配情況的總薪酬開銷，然后求最小值。

total_cost1 = 250 + 600 + 250 = 1100;  x00 = 1,x11 = 1,x22 = 1;

total_cost2 = 250 + 350 + 400 = 1000;  x00 = 1,x12 = 1,x21 = 1;

total_cost3 = 400 + 400 + 250 = 1050;  x01 = 1,x10 = 1,x22 = 1;

total_cost4 = 400 + 350 + 200 = 950;   x01 = 1,x12 = 1,x20 = 1;  //最優(yōu)分配

total_cost5 = 350 + 400 + 400 = 1150; x02 = 1,x10 = 1,x21 = 1;

total_cost6 = 350 + 600 + 250 = 1150; x02 = 1,x11 = 1,x22 = 1;

對于任務(wù)數(shù)和人員數(shù)較少時，可利用窮舉法計算結(jié)果。

若將N任務(wù)分配給N個人員，其包含的所有分配情況數(shù)目為N!，N增大時，窮舉法將難以完成任務(wù)。

三、匈牙利算法

下面簡要介紹匈牙利算法。

其基本的理論基礎(chǔ)是針對cost矩陣，將cost矩陣的一行或一列數(shù)據(jù)加上或減去一個數(shù)，其最優(yōu)任務(wù)分配求解問題不變。

算法的基本步驟如下：

四、實例分析---匈牙利算法

下面結(jié)合具體實例，分析匈牙利算法如何解決任務(wù)分配問題。

以N = 4為實例，下圖為cost列表和cost矩陣。

Step1.從第1行減去75，第2行減去35，第3行減去90，第4行減去45。

Step2.從第1列減去0，第2列減去0，，第3列減去0，第4列減去5。

Step3.利用最少的水平線或垂直線覆蓋所有的0。

Step4.由于水平線和垂直線的總數(shù)是3，少于4，進入Step5。

Step5.沒有被覆蓋的最小值是5，沒有被覆蓋的每行減去最小值5，被覆蓋的每列加上最小值5，然后跳轉(zhuǎn)到步驟3.

Step3.利用最少的水平線或垂直線覆蓋所有的0。

Step4.由于水平線和垂直線的總數(shù)是3，少于4，進入Step5。

Step5.沒有被覆蓋的最小值是20，沒有被覆蓋的每行減去最小值20，被覆蓋的每列加上最小值20，然后跳轉(zhuǎn)到步驟3.

Step3.利用最少的水平線或垂直線覆蓋所有的0。

Step4.由于水平線和垂直線的總數(shù)是4，算法結(jié)束，分配結(jié)果如下圖所示。

其中，黃色框表示分配結(jié)果，左邊矩陣的最優(yōu)分配等價于左邊矩陣的最優(yōu)分配。

五、參考資料

?module=Static&d1=tutorials&d2=hungarianAlgorithm

posted @

  本文關(guān)鍵詞：匈牙利算法，由筆耕文化傳播整理發(fā)布。