开放空间坐位优化算法
由于公司的变动，我们必须重新安排我们的座位安排：一个房间里有 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 个人，我认为我们可以暴力破解所有可能的配置，但我想知道是否有更好的算法来解决此类问题？
As a result of changes in the company, we have to rearrange our sitting plan: one room with 10 desks in it. Some desks are more popular than others for number of reasons. One solution would be to draw a desk number from a hat. We think there is a better way to do it.
We have 10 desks and 10 people. Lets give every person in this contest 50 hypothetical tokens to bid on the desks. There is no limit of how much you bid on one desk, you can put all 50, which would be saying "I want to sit only here, period". You can also say "I do not care" by giving every desk 5 tokens.
Important note: nobody knows what other people are doing. Everyone has to decide based only on his/her best interest (sounds familiar?)
Now lets say we obtained these hypothetical results:
# | 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
Now, what we need to find is that one (or more) configuration(s) that gives us maximum satisfaction (i.e. people get desks they wanted taking into account all the bids and maximizing on the total of the group. Naturally the assumption is the more one bade on the desk the more he/she wants it).
Since there are only 10 people, I think we can brute force it looking into all possible configurations, but I was wondering it there is a better algorithm for solving this kind of problems?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您似乎正在查看分配问题，可以使用匈牙利算法。这是一个经过充分研究的问题，您可能会在网络上找到可供使用的代码。
在您的情况下，您可以使用 cost = 50 - bid 并使用上述内容（分配问题的任何解决方案）。
You seem to be looking at the Assignment Problem which can be solved using Hungarian Algorithm. This is a well researched problem and you will probably find code on the web, ready to use.
In your case you can use cost = 50 - bid and use the above (any solution to assignment problem).
甚至更快，如果您有 Excel，您也应该有一个可用的 SOLVER 版本。只需设置您的出价矩阵（10x10，带出价）、分配矩阵（10x10，带 0/1 分配），使用 sumproduct(bids,分配) 来计算分配的价值，使其成为您的目标函数，并添加约束，以便有只有一项“人员分配到办公桌”和“办公桌分配到人员”的分配。确保您有选项>选中“线性模型”框并“假设非负”并解决！我刚刚设置了一个示例 10x10 问题 - 似乎工作正常。
Even faster, if you have Excel you should have a version of SOLVER available as well. Just set up your bid matrix (10x10 with bids), assignment matrix (10x10 with 0/1 assignments), use sumproduct(bids,assignments) to calculate the value of an assignment, make that your objective function, and add constraints so the there's only one assignment of people to desks and desks to people. Make sure you have the options> "linear model" box checked and "assume non-negative" and solve away ! I just set up a sample 10x10 problem - seems to work OK.