开放空间优化算法

由于公司的变化，我们必须重新安排我们的休息计划：一个房间里有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

开放空间优化算法

回答

相关问题