javascript - 根据优先参数为客人安排座位

Question

以下数据模型表示带有座位和客人的 table ，在允许用户创建 table 和座位的应用程序中，可视化地使用 HTML5。

// The data model
var data = {
    guests: [], // id, name, tags
    tables: [], // id, seats
    seats: [], // id, guest
    tags: [] // id, name
};

客人身上附有标签(某种类别)。可以对这些标签进行优先排序，并将其设置为“分组”或“取消分组”参数。然后用户点击“就座”，客人就座(看似随机)，同时尊重优先参数。

完整示例:http://jsfiddle.net/kBp49/2/ (在 JS 面板中寻找“SOLUTION GOES HERE”)

问题是我如何实现让客人坐在 table 旁的功能，同时考虑到一些客人应该坐在一起，而其他客人应该分开坐其他为了创造最好的座位配置之一？客人人数可以超过 1000，但不能超过 2000。

现实生活中的例子，阐明问题

假设我们有 3 个表。他们各有4个席位。假设我们有 9 位客人来填满这些 table 。它们如下:

1. 客人 1，犹太人，来自美国
2. 客人 2，来自英国的犹太人
3. 来自美国的客人 3，Christian
4. 嘉宾 4，Christian，来自英国
5. 嘉宾 5，Christian，来自瑞典
6. 嘉宾 6，无神论者，来自英国
7. 嘉宾 7，无神论者，来自瑞典
8. 客人 8，穆斯林，来自沙特阿拉伯
9. 客人 9，穆斯林，来自英国

现在，用户像这样对参数进行优先级排序。首先是最重要的。

1. 我希望信仰相同的人分开坐
2. 我希望地理位置相同的人坐在一起

没关系:

1. 表 1:客人:1、3、7、8
2. 表 2:客人:2、4、6、9
3. 表 3:嘉宾:5 位

更新一种解决方案可能是 Minimax 算法。它将为每种可能性计算一个分数，并提供找到的最佳解决方案(在计算后，比如 10 秒后找到)。算法是我需要帮助的，实现本身当然需要只有我才能做出的决定。

Answer 1

这个问题没有最佳答案，因为没有最佳座位安排 - 事实上我认为你说好的安排可能很糟糕 - 如果你被迫使用三张 table ，你可以每张 table 最多坐 4 个座位，您可能应该在每张 table 上坐三个人，这样就没有人会独自坐下。然而，这是吹毛求疵，并且回避了问题的基础。

我可以设想一些算法。

首先，你可以把每一个“标签”看成是N维空间中的一个维度(这听起来比实际要复杂得多)。例如，在区域维度中，您可以为每个国家/地区分配一个整数值，区域空间的维度会将这些整数中的每一个作为潜在值。然后，将每位客人作为一个点放置在这个 N 维空间中，并为每张 table 选择在该空间中距离最近的客人。您可以通过在构建空间时忽略某些特征来支持优先级 - 即，如果您不想按宗教分组，则在构建空间时不要包括宗教，或者如果您主动希望将具有“相似”宗教的人分开，您可以修改您的距离计算以在该维度中具有反比关系。该算法可能具有良好的性能，具体取决于特征的数量(即维度)和点的数量 - 这基本上就是他们创建推荐引擎的方式。

如果您想要一些简单但缓慢的事情，您可以使用蛮力算法:即对于每位客人，查看每个有成员的 table ，如果这些成员在您的优先级中不受欢迎，请坐在新的 table ​​子上。如果不存在新表，则选择具有最少不良成员的表。这可能非常简单!

最后，您可以对客人进行预处理，并计算:有多少人来自区域 x，有多少人来自宗教 y，...然后，一旦有了这些统计数据，您就可以创建表格 (取决于优先级)例如:加拿大餐 table 、英国餐 table ……，然后让客人坐在符合他们描述的任何餐 table 上。这是否可行取决于输入集。

我希望这对您有所帮助，并为您提供一些有关如何解决此问题的想法:)