language-agnostic - 座位图软件推荐(这样的野兽甚至存在吗？)

Question

我很快就要结婚了，正忙于安排座位，并且遇到了谁坐在哪里的常见问题:X 和 Y 必须坐在一起，但 A 和 B 不能互相站立等等。

我处理的数字并不大(因此手动选项可以正常工作)，但是出于极客的说服力，我想知道是否有任何软件可以为我执行此操作？

如果没有完全匹配，我应该寻找什么(问题空间、书籍、引用代码)来调整我的目的？

Answer 1

我是 PerfectTablePlan 的开发者。我在这里发帖以及 Joel's Business of Software . ;0)

组合问题，例如座位分配，在算法上是非常讨厌的。 NP-hard实际上。 60个座位60个座位的方法数是60个! (60阶乘)，这比已知宇宙中的原子数还多。

PerfectTablePlan 允许您指定 A 必须坐在 B 旁边，但不能靠近 C。它使用遗传算法自动分配座位。这在实践中非常有效——它通常会在几秒钟内为 100 位客人找到一个不错的解决方案。您可能需要为 1000 多名客人煮咖啡。在实践中，通常还需要进行一些拖放式微调，以应对变幻莫测的本地风俗和家庭政治(鲍勃叔叔有点聋，我们最好让他靠近顶级 table )。

您可以了解更多关于遗传算法的信息 here .

Ps/自动座位分配只是创建良好座位计划的一小部分。查看 PerfectTablePlan tour和 tips页面了解更多详情。