algorithm - 与约束匹配

Question

为了好玩，我正在创建一个程序，为 secret 圣诞老人的礼物交换生成合作伙伴。然而，在这个设置中，不是随机生成对，而是允许约束。

例子:A 和 B 互相讨厌，所以 A 和 B 都不应该被分配给对方买礼物。

第二个例子:C 去年给 D 买了一件礼物。不应指定 C 为 D 购买礼物，但仍应允许 D 为 C 购买礼物。

一般来说，我想生成一个从集合到自身的双射函数，但该函数需要对约束敏感。如果约束条件太多以至于无法解决问题，例程应该返回错误或其他内容。

这在我看来像是某种图形问题，但我真的不知道该往哪个方向去解决它。我怎样才能以编程方式解决这个问题？是否有我可以使用/修改的现有算法？

Answer 1

基本上你的问题是众所周知的assignment problem :

考虑一个二分图，其中每一侧都将所有人作为节点(是的，每个人将出现两次:一次在左侧，一次在右侧)。然后，如果允许 A 向 B 发送礼物，则可以从左侧的人 A 到右侧的人 B 添加边。然后您可以申请，例如 Hungarian algorithm找到最大化允许礼物数量的分配。