匈牙利算法和多種因素

Question

我有一種情況，我需要分配給幾個人的事件。如果我們只是以一個價格作爲因素，那就沒有問題，但是有很多因素可以進來。

首先，一些背景。這是一個非營利組織，它爲因任何原因住院的兒童提供故事時間，所以他們依靠志願工作來這樣做。所以，因爲它們依賴於人們的良好意願，他們給人們儘可能多的工作，因爲人們可以/想做的事，而變化，如：

• 有些人只能做早晨，和其他一些人只能做的下午;
• 有些人只能做星期一和星期四，其他人不能去八月或十二月;
• 有些人每月只能去一次，其他人可以去4次（甚至其他人在這些行動中被賦予「優先權」，因爲他們更有經驗並且可以每月可以做10次）

所以，我有點想出了前兩個。由於匈牙利算法是關於價格的，所以我會給他們一個愚蠢的高價格，因爲他們不能去的時間。但是，你會怎麼做其他人？

我想過給他們一些分數。大致有以下幾點：一個人一個月可以做到這一點的成本大約是1000分。如果某人可以每月去10次，那麼這個人的成本是100點（1000除以10）。此外，分發這種方式是增加每當一個單獨的行動將完成，像這樣（被選擇的人對他們的相關成本。*）的價格：

第一次迭代

  | August 1st 2009 
Person A | 1000 
Person B | 500 * 

第二次迭代

  | August 8th 2009 
Person A | 1000 * 
Person B | 1000 

這將是在所有人之間進行相應分配的方式，給予多次優先處理的人。

你覺得怎麼樣？你會怎麼做？

Answer 1

這是一個調度/優化問題，所以關鍵問題是「你試圖最大化什麼數量」？我想你會希望最大限度地發揮所有志願者在沒有衝突的情況下工作的總時數，這取決於每個志願者的時間安排約束。你還提到優先考慮有更多經驗的志願者，所以聽起來好像你在說「有些志願者比其他人更喜歡」。

這是一個典型的bipartite matching problem。見例如由Steven Skiena撰寫的The Algorithm Design Manual（第二版）的第498頁。基本的方法是構造一個圖表，其頂點代表志願者集合，以及您嘗試填充的時間段集合。 Edges將志願者鏈接到有效的時間段。那麼最佳解決方案是最大可能的一組邊緣，其中不重複志願者或時隙。這是一個匹配。

你的一些志願者可能可以做多個插槽;這可以通過多次複製該志願者頂點來建模。

如果您想實施志願者的優先順序，那麼這將有效地爲每個邊添加權重，爲該任務的志願者的體驗建模。在這種情況下，如你所想，你將需要像匈牙利算法之類的東西。如果沒有這個可以逃脫，那麼你可以將這個問題轉換成等效的flow graph，並應用網絡流算法。這裏是code that implements both weighted and unweighted matching的一個例子。

如果你想了解更多細節，包括其他選擇，以及更多的實現鏈接，我強烈建議你自己找一份算法設計手冊 - 這是一個非常清晰和實用的參考。