algorithm - 实现一种算法以在餐 table 座位上分配客人

Question

这个问题在这里已经有了答案:




10年前关闭。

Possible Duplicate:
Seat guests based on prioritized parameters

我一直在努力解决这个问题。我只是无法绕过它。如果更聪明或有更多算法和/或数学洞察力的人可以向我解释我应该如何进行，将不胜感激。

客户正在安排各种事件，从餐厅到大型 field 不等。我的客户软件的目标是为客人提供短信/电子邮件/纸质票，说明客人到达事件时应该坐在哪里。座位(客人应该坐在哪里)必须手动控制，有些 table 是“VIP”等。我正在研究一种算法，可以通过让用户确定一些参数来帮助用户，例如客人所属的公司和客人可以说哪种语言。今天，就座过程是在大型白板上手工制作的(如果事件是 1k+ 客人，则一次一个部分)。

我的工作是稍微自动化一下，不是完全自动化，而是“足够好”。我构建了一个应用程序，可以直观地呈现 table 、椅子(座位)和客人。但是，仍然缺少最重要的功能；能够根据用户选择的参数将客人分配到现有的 table 和座位上。

参数是每个客人的任意数量的数据，例如:“39 岁，男性，Redwine Corp，CTO，英语和意大利语”。用户获取这些(所有客人都有相同的数据字段)并按重要性顺序对它们进行排序。每个参数也必须设置为“next to”或“apart from”。例如，用户可以控制说同一种语言的客人应该坐在一起，但在同一家公司工作的客人应该分开坐。

鉴于此，我将要实现的函数定义是这样的: function getGuestSeatings(tables, seats, guests, parameters)并返回一组哪些客人应该坐在哪些座位上。参数 tables , seats和 guests包含您选择的信息，但最重要的可能是椅子的 X、Y。结合椅子连接到哪张 table 的信息，应该足以计算出“足够好”的客人坐姿配置。当然， parameters变量包含有关参数优先级的信息，以及它是“seat-next-to”还是“seat-apart-from”参数。

我要问的问题是:可以使用什么算法来提供解决方案，以及如何实现它？数学答案可能没有用，所以为了安全起见，我建议使用代码(JS/C/C#)或伪代码。

我将为您提供更多信息，这些信息可能会或可能不会填补解决方案的任何空白(我将在此处补充您的评论反馈):

表格可以是椭圆形或矩形

如果没有符合标准(优先参数)的座位配置，那么我仍然想要一个“足够好”的解决方案，即使它不是最好的

我知道调查所有可能性可能会占用内存

也许某种延迟加载的基于点的树系统就足够了？只是调查看起来很有希望的路径而忽略其他路径......？

这是一个模型，可让您了解软件背后的想法:

Answer 1

Simulated Annealing.

这个想法是你有一个最初的人分配到座位，你有一个“善良”的功能。
你想最大化善函数。
粗略地说，你这样做的方式是随机切换人的座位，如果这导致函数的值更高，你就从那里重新开始。
如果切换导致优度函数的值较低，您可能仍会随机接受它，这可以帮助您避免局部最大值。
这称为 Metropolis-Hastings .

你让它运行数千次，看看你得到了什么。