我似乎无法为一对二的分配问题找到一个好的算法。好的算法以经典的分配问题而闻名，其中 N 个任务需要以一一对应的方式分配给 M 个代理。
在我的一对二分配问题的情况下，我有 N 个任务和 M 个代理。但是，每个任务只有分配给两个代理才能解决。与经典分配问题类似，目标是最小化成本，由成本矩阵给出. 这里分配任务代理花费一定金额.
有什么想法可以有效解决这个问题吗？
我已经考虑了 Pentico, D. 'Assignment Problems: A Golden Anniversary Survey' 的评论，但在那里找不到我的问题。
不确定这是否是一个好的解决方案，但无论如何都会发布：
假设我们可以形成一个二分图并且可以解决一对一的分配问题。我们将从以经典方式分配第一个任务开始：每个节点将被分配给目标中的一个节点。然后我们可以从图中删除分配的链接（边），因为这些已经存在于之前的解决方案中（例如，我们可以将分配成本设置为无穷大）。然后我们可以重新运行分配算法，即匈牙利语，并生成下一个分配，这些分配保证与第一个不同。
当然，这个算法可能会导致一个次优的解决方案，因为它看起来很贪婪。然而，第一个解决方案始终是经典分配问题的最佳解决方案，它可能是一个很好的简单开始，因为这种方法可以让您从现有的求解器中受益。复杂性明智的只是，这是非常可以接受的。
以类似的方式，可以使用拍卖算法，这可能会将运行时间减少到.