我即将结婚，忙于制定座位表，遇到了通常的问题：X和Y必须坐在一起，但A和B不能相处等等。我处理的数字并不是很多（因此手动操作完全可行），但作为一个极客，我想知道是否有任何软件可以帮我完成这个任务？
如果找不到精确匹配的软件，我应该寻找什么（问题空间、书籍、参考代码）来调整以适应我的需求？
如果找不到精确匹配的软件，我应该寻找什么（问题空间、书籍、参考代码）来调整以适应我的需求？
7个回答
12
我是PerfectTablePlan的开发者。我在Joel's Business of Software上也发布了一些内容。 ;0)
组合问题，如座位分配，在算法上非常棘手。实际上是NP-hard问题。将60个客人安排在60个座位上的方式有60！（60的阶乘）种，这比已知宇宙中的原子数量还要多。
PerfectTablePlan允许您指定A必须坐在B旁边，但不能坐在C附近。它使用遗传算法自动分配座位。实际上，这在实践中效果很好 - 它通常可以在几秒钟内为100个客人找到一个不错的解决方案。对于1000+客人，您可能需要泡一杯咖啡。实际上，通常还需要进行一些拖放微调，以应对当地习俗和家庭政治的变幻莫测（Bob叔叔听力有点差，我们最好把他放在靠近主桌的位置）。
您可以在这里了解更多关于遗传算法的信息。
Ps/ 自动座位分配只是创建良好座位计划的一小部分。请参阅PerfectTablePlan tour 和 tips 页面以获取更多详细信息。
- Andy Brice
4
这不是一个离散的约束满足问题吗？当然，一个约束编程求解器可以很容易地解决这个问题吧？ - Marcin
顺便提一下，这并不是贬低您的产品特性，而是对于自制解决方案中可能会出现的问题，例如任何非文本内容都会带来麻烦。 - Marcin
如果你有100个客人，每个客人都有5个偏好，想要坐在或远离其他客人旁边，那么使用约束编程能否在标准台式电脑上几秒钟内解决这个问题？购买或编写一个约束编程求解器对于一款35美元的产品来说是否具有财务可行性？ - Andy Brice
本文展示了一个MINLP求解器花费36小时来解决一个107位客人的问题，即分配桌子而不是座位：http://www.improbable.com/news/2012/Optimal-seating-chart.pdf - Andy Brice
6
- Antonio Louro
1
尝试使用GLPK进行建模。整数线性规划适用于在基于图的问题中引入约束条件，这些问题具有多种可能的结果。
- Robert Elwell
1
我个人喜欢不指定座位：让人们坐在他们想坐的地方。
这可能会导致有意或无意的小圈子，但这意味着你不必担心它。
- warren
2
@nwahmeat：因为邀请者通常可以更有效地将有共同兴趣爱好的人分组，特别是如果这些人彼此并不认识。 - David Schmitt
84%的客人更喜欢有指定座位，参见：http://www.prweb.com/releases/2006/2/prweb344508.htm。;0) - Andy Brice
0
这听起来像是一个约束满足问题。你应该去查一下那些配备了约束求解器的逻辑编程系统。它们通常类似于Prolog，只不过对于可由其求解器求解的问题实际上是声明式的。
希望有一个易于使用的接口，可以从你喜欢的语言中获取数据并输出。
希望有一个易于使用的接口，可以从你喜欢的语言中获取数据并输出。
- Marcin
0
我曾经使用过一个程序，它非常适合这个需求...它是一个Java应用程序，你可以定义规则，然后它会创建满足规则的测试用例。文件扩展名是.als。
fact GateRules { all g:Gate | one g.loc // Gates have 1 Location
我会继续费尽心思想出程序名称。
编辑：它是Alloy 现在我想起来了，这可能不是理想的 - “固定配置的座位”概念可能有点难以建模。 我使用它的方式不同：定义规则（机场登机口在一个位置，只有一架飞机在跑道上），并测试函数的前后条件（在我降落飞机后，我是否可以在跑道上有多架飞机？）。
- AviewAnew
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接