匹配约束 [英] Matching with constraints

问题描述

为了娱乐，我正在创建一个程序，该程序可为Secret Santa礼物交换生成合作伙伴.但是，在此设置中，允许使用约束而不是随机生成对.

For fun, I'm creating a program that generates partners for a Secret Santa gift exchange. However, in this setup, instead of randomly generating pairs, constraints are allowed.

示例:人A和人B彼此讨厌，所以A和B都不应该分配给对方购买礼物.

Example: Person A and Person B hate each other, so neither A nor B should be assigned to buy a gift for the other.

第二个例子:丙人去年买了礼物给丁人.不应指派C人为D人购买礼物，但仍应允许D人为C人购买礼物.

Second Example: Person C bought a gift for Person D last year. Person C should not be assigned to buy a gift for Person D, but person D should still be allowed to buy C a gift.

通常，我想从集合到其自身生成一个双射函数，但是该函数需要对约束敏感.如果约束太多，无法解决问题，则例程应返回错误或类似内容.

In general, I want to generate a bijective function from a set to itself, but that function needs to be sensitive to constraints. If there are too many constraints such that the problem can't be solved, the routine should return an error or something.

在我看来，这看起来像是某种图形问题，但我真的不知道该朝哪个方向解决.如何以编程方式解决此问题?我可以使用/修改现有的算法吗?

This looks to me like some sort of graph problem, but I don't really know what direction to go in to solve it. How can I solve this problem programmatically? Are there existing algorithms I can use/modify?

推荐答案

基本上，您的问题是众所周知的分配问题:

Essentially your problem is well-known assignment problem:

考虑一个二部图，其中每一边都有所有人员作为节点(是的，每个人将出现两次:一次在左侧，一次在右侧).然后，如果允许A向B发送礼物，则可以从左边的人A向左边的人B添加一条边.然后，您可以应用

Consider a bipartite graph where each side has all persons as nodes (yes, each person will appear twice: once at the left side and once at the right one). Then you can add an edge from person A from the left side to the right side's person B if A is allowed to send a gift to B. Then you can apply, for example, Hungarian algorithm to find assignment which maximizes number of allowed gifts.

这篇关于匹配约束的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！