我有x位客人参加我的婚礼和y桌子和z座位。客人A可以和客人B坐在同一张桌子上，客人C不能和客人D坐在同一张桌子上，....
给定所有客人之间所有连接的数据集，是否有一种已知的算法可以解决这类问题？
我确信这种问题有一个抽象的父母称为“问题x”或某种东西，或者它可能是问题a和问题b的组合，可以通过组合算法y和z来解决
正确方向的任何一点都值得赞赏。
我有x位客人参加我的婚礼和y桌子和z座位。客人A可以和客人B坐在同一张桌子上，客人C不能和客人D坐在同一张桌子上，....
给定所有客人之间所有连接的数据集，是否有一种已知的算法可以解决这类问题？
我确信这种问题有一个抽象的父母称为“问题x”或某种东西，或者它可能是问题a和问题b的组合，可以通过组合算法y和z来解决
正确方向的任何一点都值得赞赏。
如果您需要精确的解决方案，请将其表示为0-1整数程序并使用GLPK来解决它。
如果将i分配给表j，则将x_ij设为1，否则设为0。考虑以下约束集：
（i）对于i = 1 ... x，sum_ {j = 1 ... y} x_ij = 1
（ii）对于j = 1 ... y，sum_ {i = 1 ... x} x_ij <= z
（iii）对于j = 1 ... y，x_ij + x_kj <= 1
（iv）x_ij是二进制的
约束（i）确保每个人都被分配。约束（ii）防止表超载。约束（iii）是针对不能坐在一起的每个人对（i，k）定义的。
将其插入GLPK，CPLEX或GUROBI，只要问题不是太大，您就可以开展业务。正如其他人所提到的那样，NP硬度意味着事情会变得丑陋。
在一般情况下，这个问题是NP难的，所以如果表或客户的数量很大，你不应该期望找到一个通用的解决方案。这个问题是一个变种 这个早期的问题 根据他们的偏好要求将人们分成不同的房子，你可以通过简单地给每个桌子足够的容量来容纳每一个客人来减少这个问题（这是NP难的）。
如果每个桌子的人数很少而且客人数量很少，那么你可以通过尝试每一个可能的任务来强制解决问题。另一个选择是尝试随机猜测一些解决方案，然后逐步修改它们以尝试找到有效的解决方案（例如，使用爬山算法）。
希望这可以帮助！
这是一个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，有多少未定位的客人能够填充剩余的座位。然后，当您将客人分配到桌子而不是随机选择时，您将优先选择具有大量剩余席位的桌子以及能够坐在其中的人数较少。
在实践中，如果像这样的启发式方法在尝试几百个随机尝试后不起作用，那么它可能是一个难以解决的问题。
我知道这个问题是在几年前被问到的，但对于那些遇到类似问题的人来说仍然存在。
问题的定义
我的问题很相似：考虑到一些偏好，在婚礼上让人坐在哪里？它与初始问题不完全相同，但正确设置首选项，您可以制定初始问题。
我没有读到有关这些复杂问题以及解决问题的方法。我只是想到了另一种方法。我确信它不是解决问题的最佳方式，但它很有效并且易于实现。
该方法
我选择了一个模型，其中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的总和除以表的数量。平均评级是我打算最大化的评级。
该算法的思想如下。想象一下，你有一个初步的解决方案（例如，人们随机坐在桌子旁边）。然后，如果你用另一张桌子的人j切换一个人的表，会发生什么？两个表的评级都会改变。我们将这些潜在的变化保存在有序向量中。最后，我们将有一个结构向量，每个结构包含当人与人j交换时评级的变化（两个表的评级变化之和）。当你有所有潜在的变化时，我们迭代向量，从评级的最大变化开始，然后 转换人员。要采取的步骤详述如下。
算法
1）计算结构矢量，其中包含对被切换人员的参考，他们来自的表格，以及每个表格在切换期间将经历的评级差异的总和。我们称之为整体评级变化。
2）迭代结构向量：如果总体评级变化为正，则用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），那么任何设置都是一个解决方案。
我希望这有帮助。我知道这是一个很长的解释，我希望它足够清楚。如果您想了解更多详情，请告诉我。