与约束匹配

Question

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

示例：A 和 B 彼此讨厌，因此不应指派 A 和 B 为对方购买礼物。

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

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

在我看来，这就像某种图形问题，但我真的不知道要从哪个方向解决它。如何以编程方式解决此问题？是否有我可以使用/修改的现有算法？

Answer 1

本质上你的问题是众所周知的分配问题：

考虑一个二分图，其中每一侧都有所有人作为节点（是的，每个人都会出现两次：一次在左侧，一次在右侧）。然后，如果允许 A 向 B 发送礼物，则可以从左侧的人 A 添加一条边到右侧的人 B。然后，您可以应用例如匈牙利算法来找到最大化允许的礼物数量的分配。