我的婚礼有 x 位客人，有 y 张桌子，有 z 个座位。客人A可以与客人B同桌，客人C不能与客人D同桌，......
给定所有客人之间所有连接的数据集，是否有已知的算法可以解决此类问题？
我确信这种问题有一个抽象的父问题，称为“问题 x”或其他问题，或者它可能是问题 a 和问题 b 的组合，可以通过组合算法 y 和 z 来解决
任何方向正确的点都会受到赞赏。
如果需要精确解，请将其制定为 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
(iii) x_ij + x_kj
(iv) x_ij 是二进制的
约束 (i) 确保每个人都被分配。约束 (ii) 防止表过载。约束 (iii) 是为不能坐在一起的每一对 (i,k) 人定义的。
只要问题不是太大，将其插入 GLPK、CPLEX 或 GUROBI 即可开始工作。正如其他人提到的，NP 硬度意味着事情可能会变得丑陋。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
