algorithm - 哪种算法可以解决我的婚礼餐 table 问题？

Question

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

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

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

在正确方向上的任何一点都会受到赞赏。

Answer 1

如果您需要精确解，请将其表述为 0-1 整数规划并使用 GLPK 求解。

如果人 i 被分配到表 j，则 x_ij 为 1，否则为 0。考虑以下约束集:

(i) sum_{j=1...y} x_ij = 1 对于 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) 防止表过载。约束条件 (iii) 是为每个不能坐在一起的人对 (i,k) 定义的。

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