哪种算法可以解决我的婚宴桌问题? [英] Which algorithm could solve my wedding table issue?

问题描述

我有x位客人参加我的婚礼，y位桌子有z个座位.来宾A可以与来宾B坐在同一张桌子上，而来宾C不能与来宾D放在同一张桌子上，....

I have x guests for my wedding and y tables with z seats. Guest A can sit on the same table as guest B and guest C can not sit on the same table as guest D, ....

给出所有来宾之间所有连接的数据集，是否有已知的算法可以解决此类问题?

Given a dataset of all connection between all guests , is there a known algorithm which can solve this kind of issue?

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

I am sure this kind of problem has an abstract parent known as "problem x" or something or maybe it's a composition of problem a and problem b which can be solved by combining algorithm y and z

任何朝着正确方向的观点都会受到赞赏.

Any point in the right direction is appreciated.

推荐答案

如果需要精确的解决方案，请将其公式化为0-1整数程序，然后使用GLPK来解决.

If you require an exact solution, formulate it as an 0-1 integer program and use GLPK to solve it.

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

Let x_ij be 1 if person i is assigned to table j and 0 otherwise. Consider the following constraint set:

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

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

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

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

(iii)x_ij + x_kj< = 1表示j = 1 ... y

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

(iv)x_ij是二进制

(iv) x_ij is binary

约束(i)确保分配了每个人.约束(ii)防止表超载.为不能坐在一起的每个人对(i，k)定义了约束(iii).

Constraints (i) make sure everyone is assigned. Constraints (ii) prevents overloading a table. Constraints (iii) are defined for each person pair (i,k) that can't sit together.

将其插入GLPK，CPLEX或GUROBI，并且您的业务已经开始，前提是问题不是太大.正如其他人提到的那样，NP硬度意味着事情可能变得很丑.

Plug it into GLPK, CPLEX, or GUROBI and you're in business, provided that the problem is not too large. As the others have mentioned, NP-hardness means things could get ugly.

这篇关于哪种算法可以解决我的婚宴桌问题?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！