開放空間優化算法

由於公司的變化，我們必須重新安排我們的休息計劃：一個房間裏有10個辦公桌。由於種種原因，一些辦公桌比其他辦公桌更受歡迎。一種解決方法是從帽子上劃出一個辦公桌號碼。我們認爲有更好的方法來做到這一點。開放空間優化算法

我們有10個辦公桌和10個人。讓本次比賽中的每個人都有50個假設的代幣在辦公桌上競標。您在一張桌子上投標的次數沒有限制，您可以放置全部50張，這就是「我只想坐在這裏，期間」。通過給予每張桌子5個代幣，你也可以說「我不在乎」。

重要提示：沒有人知道別人在做什麼。每個人都有權決定僅僅基於他/她的最佳利益（聽起來很熟悉？）

現在讓我們說，我們獲得的這些假設的結果：

# | Desk# >| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 
1 | Alise | 30 | 2 | 2 | 1 | 0 | 0 | 0 | 15 | 0 | 0 | = 50 
2 | Bob | 20 | 15 | 0 | 10 | 1 | 1 | 1 | 1 | 1 | 0 | = 50 
    ... 
10 | Zed | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | = 50

現在，我們需要找到的是一個（或多個）配置，這給了我們最大的滿意度（即人們得到他們想要的桌子時考慮到了所有的出價並最大限度地提高了整個團隊的人數。自然地，假設是桌子上的人越多，他/她想要的就越多）。

由於只有10人，我認爲我們可以蠻橫的強制它尋找所有可能的配置，但我想知道有一個更好的算法來解決這類問題？

來源

2010-06-11 Georgy Bolyuba

可能與http://en.wikipedia.org/wiki/Stable_marriage_problem – polygenelubricants 2010-06-11 13:13:11

有關我認爲在實踐中你可能想要更像最低限度的失望而不是最大的滿足感。或者至少有一些組合。 – 2010-06-11 13:27:57

@Doug：謝謝你的提示:)。有可能 – 2010-06-11 14:08:23

您似乎正在查看可使用Hungarian Algorithm解決的Assignment Problem。這是一個經過深入研究的問題，您可能會在網絡上找到可供使用的代碼。

在你的情況下，你可以使用成本= 50 - 投標並使用上述（任何解決方案分配問題）。

來源

2010-06-11 13:15:32

坦率地說，我很驚訝你的文化。似乎每次在算法中遇到一個問題時，你都會碰巧知道問題的名稱！ – 2010-06-11 18:10:47

@Matthieu：我會以此爲恭維:-)謝謝！我想是因爲我對算法很感興趣。希望在5年後我仍能記住所有這些。另外，人們通常會在這裏問一些已經解決的問題的版本，這樣可以幫助。 – 2010-06-11 18:24:55

@Matthieu：任何人都可以像這樣谷歌的問題。這是真正令人印象深刻的答案，像[this（link）]（http://stackoverflow.com/questions/2955318/creating-combinations-that-have-no-more-one-intersecting-element/2955527#2955527）。 – 2010-06-11 22:00:34

更快，如果你有Excel，你應該有一個版本的SOLVER。只需設置您的出價矩陣（10x10包含出價），分配矩陣（10x10包含0/1分配），使用sumproduct（出價，分配）來計算任務的價值，確定您的目標函數並添加約束條件，只有一人分配給辦公桌和書桌給人。確保你有選項>「線性模型」框選中，「假設非負」，並解決掉！我只是設置了一個10x10樣本問題 - 似乎工作正常。

來源

2010-06-11 21:01:04 Grembo

開放空間優化算法

回答

相關問題