11

我有 x 位客人参加我的婚礼，还有 y 桌有 z 个座位。客人 A 可以和客人 B 同桌，客人 C 不能和客人 D 同桌，...

给定所有客人之间所有连接的数据集，是否有可以解决此类问题的已知算法？

我确信这类问题有一个抽象的父对象，称为“问题 x”或其他东西，或者它可能是问题 a 和问题 b 的组合，可以通过结合算法 y 和 z 来解决

任何正确方向的观点都值得赞赏。

4

4 回答 4

7

如果您需要一个精确的解决方案，请将其公式化为一个 0-1 整数程序并使用 GLPK 来解决它。

如果将人 i 分配给表 j，则 x_ij 为 1，否则为 0。考虑以下约束集：

(i) sum_{j=1...y} x_ij = 1 for i=1...x

(ii) sum_{i=1...x} x_ij <= z for j=1...y

(iii) x_ij + x_kj <=1 对于 j=1...y

(iv) x_ij 是二进制的

约束 (i) 确保每个人都被分配。约束 (ii) 防止表过载。为不能坐在一起的每个人对 (i,k) 定义约束 (iii)。

将其插入 GLPK、CPLEX 或 GUROBI 中，只要问题不是太大，您就可以开展业务了。正如其他人所提到的，NP 硬度意味着事情可能会变得丑陋。

于 2013-10-02T19:31:27.220 回答
5

这个问题在一般情况下是 NP-hard，所以如果桌子或客人的数量很大，你不应该期望找到一个有效的通用解决方案。这个问题是这个早先问题的一个变体，它询问根据人们的喜好将人们分成不同的房子，你可以通过简单地给每张桌子足够的容量来容纳每一个来宾。

如果每张桌子的人数少而客人人数少，您可以通过尝试所有可能的分配来强制解决方案。另一种选择是尝试随机猜测一些解决方案，然后逐步修改它们以尝试找到可行的解决方案（例如，使用爬山算法）。

希望这可以帮助！

于 2013-10-02T17:55:36.080 回答
1

这是一个 NP 难题，因此您不会找到通用解决方案。事实上，即使找到能够坐在一张桌子上的 z 个客人也是 NP 难的。

但是，如果您没有太多的客人冲突，那么启发式可能会起作用。例如：

Pick an unseated guest G with a maximal number of incident edges (conflicts)
  If G has a conflict with someone seated at each table, then fail
  Else assign G at random to an available table
Repeat until all guests are seated

更好的启发式方法包括跟踪每位客人的所有可能的桌子。一开始，每位客人都可以坐在任何一张桌子上。

Pick an unseated guest G such that the size of G.availableTables is minimal
  If G.availableTables is empty, then fail
  Assign G at random to a table T from G.availableTables
  For each guest G2 who is in conflict with G
    remove T from the set G2.availableTables
Repeat until all guests are seated.

您还可以修改此启发式以使其更加强大，为每张桌子 T 跟踪有多少未就座的客人能够填补剩余的座位。然后，当您将客人分配到一张桌子时，您会优先选择剩余座位多且能够坐在其中的人较少的桌子，而不是随机选择。

在实践中，如果这样的启发式算法在尝试了数百次随机尝试后仍不起作用，那么这可能是一个难以解决的问题。

于 2013-10-02T19:19:51.287 回答
1

我知道这个问题是几年前提出的，但仍然是针对那些遇到类似问题的人。

问题的定义

我的问题是类似的：考虑到一些偏好，在婚礼上让人们坐在哪里？它与初始问题并不完全相同，但正确设置首选项，您可以制定初始问题。

我没有读到那些复杂的问题以及解决它的方法。我只是想到了另一种方法。我确信这不是解决问题的最佳方法，但它有效且易于实施。

该方法

我选择了一个模型，其中一个人可以表达自己想坐在或不坐在另一个人的同一张桌子上的愿望。我们称它们为权重。因此，Sara 可以通过引入重量（例如从 -5 到 5）来表达她的愿望，即坐在（5）或不坐在（-5）迈克尔的同一张桌子上。也许她不在乎（0），或者迈克尔很帅但有点小（2）或者他很好但闻起来很奇怪（-3）。

让 w_ij 是与我想和 j 坐在同一张桌子上的人的愿望相关的权重。请注意，w_ij 不一定等于 w_ji（Sara 可能喜欢 Michael，但可能 Michael 讨厌 Sara）。然后，让我们定义一个表的评分如下：

rating_table = 1/N * sum_i sum_j w_ij

其中 N 是餐桌上的人数。请注意，权重的总和是 Nx(N-1)/2 项（包括 0 项）的总和。想象一下 3 个人在 1 张桌子上，然后有 6 个重量，而不是 9 个（一个人不能希望和自己坐在同一张桌子上......）。

然后，平均评分是每个 rating_table 的总和除以表的数量。该平均评分是我打算最大化的评分。

该算法的思想如下。想象一下，您有一个初始解决方案（例如，人们随机坐在桌子旁）。那么，如果将一张桌子的一个人 i 与另一张桌子的一个人 j 互换会发生什么？两个表的评级都会改变。我们将这些潜在的变化保存在有序向量中。最后，我们将有一个结构向量，每个结构包含当人 i 与人 j 切换时的评分变化（两个表的评分变化之和）。当你有所有潜在的变化时，我们迭代向量，从评分的最大变化开始，然后切换人员。下面详细介绍要采取的步骤。

算法

1) 计算结构向量，其中包含对被切换人员的引用、他们来自的表格以及在切换期间每个表格将经历的评级差异的总和。让我们称之为整体评级变化。

2) 迭代结构向量：如果整体评分变化为正，则将人员 i 与 j 切换。假设人 i 来自 A 桌，而人 j 来自 B 桌。由于 A 桌和 B 桌的设置发生了变化，我们无法在这些桌子之间切换更多人。因此，如果向量包含与其中一个表相关的另一个开关，我们必须跳过它。循环结束后，我们可以重新开始。因此，在 1 个循环中每个表最多 1 个开关。

3) 继续切换，只要额定值的变化是正的并且在切换期间还没有使用表 A 和 B。请注意，一张表可能会增加 2，而第二张表可能会减少 1。整体变化仍然是积极的。

4）回到步骤1。现在我们可以再次在所有表之间切换。同样，我们只能在 1 个循环期间从表 A 和 B 切换人员一次。

5) 继续此操作，直到所有整体评级变化均为负数或 0。

因此，您可以智能地、有选择地分别从表 A 和 B 中选择人员 i 和 j，这样就会出现最佳的总体评分变化，并且您会继续进行，直到没有更好的解决方案存在为止。

该算法的缺点是第 1 步：您需要计算所有整体评分变化。但是对于甚至 1000 张桌子的事件，这应该不是问题。

独特的解决方案？

很多时候，您可以找到解决此问题的多种解决方案。想象一下，您使用上述算法找到了一种解决方案。然后，2 个人之间的任何切换都会产生 0 的整体变化是另一种解决方案。因此，找到 1 个解决方案后，很容易找到所有解决方案。

如果您找到了 1 个解决方案，并且您找到了一个总评级变化为 0 的开关，因此找到了一个新解决方案，您可以使用该新解决方案来找到另一个解决方案，依此类推。想象每个人都设置相同的权重（或者例如，没有人关心并且所有权重都是 0），那么任何设置都是解决方案。

我希望这有帮助。我知道这是一个很长的解释，我希望它足够清楚。如果您想了解更多详细信息，请告诉我。

于 2018-06-20T14:36:35.080 回答