C#實現匈牙利算法(2)

Step 3. 檢驗可否完成僅含零的完全指派,若不能,則畫出最少數目的垂直與水平的刪 除線來包含所有的零至少一次.

[tr=red][tr=red] 0

0 8 2 5 11 0 5 4 2 3 0 0 0 11 4 5

　Step 4. 找出未被畫線的元素中之最小值 K,將含有此些未被畫線的元素的各列所有 元素減去K (Step 4.1),若造成負值,則將該欄加上K (Step 4.2).形成新矩陣後回到Step 2.

Step 4.1

[tr=red][tr=red] -2

-2 6 0 3 11 0 5 4 2 3 0 0 -2 9 2 3

　Step 4.2

0 6 0 3 13 0 5 4 4 3 0 0 0 9 2 3

形成新矩陣 Step 2.

0 6 0 3 13 0 5 4 4 3 0 0 0 9 2 3

　由上表知,指派順序為 (2,2), (4,1), (1,3), (3,4),可得到完全指派.

課程1　　　課程2　　課程3　 　課程4

教授A 9 教授B 4 教授C 11 教授D 4

總准備時間為 9+4+11+4 = 28 為最佳解.