一般图中最小成本+最大匹配的算法
Algorithm for minimal cost + maximum matching in a general graph
我有一个由节点和边组成的数据集。
节点代表人，边代表人与人之间的关系，每个人都有一个使用欧氏距离计算的成本。
现在我希望通过它们各自的边将这些节点匹配在一起，其中只有一个约束：
- 任何节点只能与一个其他节点匹配。
现在我们知道我正在处理一般图，理论上每个节点都可以与数据集中的任何节点匹配，只要它们之间有一条边。
我想做的是找到具有最大匹配和最小总成本的解决方案。
Node A
Node B
Node C
Node D
- Edge 1:
Start: End Cost
Node A Node B 0.5
- Edge 2:
Start: End Cost
Node B Node C 1
- Edge 3:
Start: End Cost
Node C Node D 0.5
- Edge 2:
Start: End Cost
Node D Node A 1
这个问题的解决方案如下：
分配边 1 和边 3，因为这是匹配的最大数量（在这种情况下，显然只有 2 个解决方案，但可能有大量分支边到其他节点）
边 1 和边 3 被分配，因为它是具有最大匹配数量和最小总成本的解决方案 (1)
我研究了很多算法，包括 Hungarian、Blossom、Minimal-cost flow，但我不确定哪种算法最适合这种情况。此外，似乎有很多 material 可以解决二分图中的此类问题，但在这件事上并非如此。
所以我问你：
在这种情况下，哪种算法最好 return (a) 匹配的最大数量和 (b) 总成本最低。
你知道什么好的material（也许是一些容易理解的伪代码），作为你推荐的算法吗？我数学符号不是最强的
对于(a)，最合适的算法（理论上有更快的算法，但它们更难理解）是Edmonds 的Blossom 算法。不幸的是它相当复杂，但我会尽力解释基础。
基本思想是进行匹配，并通过进行一些局部更改来不断改进它（增加匹配节点的数量）。关键概念是 交替路径 ：从一个不匹配的节点到另一个不匹配的节点的路径，属性 边缘在匹配中和匹配之外交替.
如果你有一个交替路径，那么你可以通过翻转交替路径中边的状态（无论它们是否在匹配中）来增加匹配的大小。
如果存在交替路径，则匹配不是最大的（因为路径为您提供了增加匹配大小的方法），相反，您可以证明如果没有交替路径，则匹配是最大的。因此，要找到最大匹配，您需要做的就是找到一条交替路径。
在二分图中，这很容易做到（可以用 DFS 做到）。在一般图形中，这更复杂，这是埃德蒙兹的 Blossom 算法出现的原因。粗略地说：
构建一个新图，如果你可以通过首先遍历匹配中的边，然后遍历匹配中的边，从 u 到 v，两个顶点之间有一条边' t.
在这个图中，尝试找到一条从不匹配的顶点到具有不匹配的邻居（即原始图中的邻居）的匹配顶点的路径。
你找到的路径中的每条边对应于原始图的两条边（即匹配中的一条边和匹配中的一条边），因此路径转换为新图中的交替行走，但是这个不一定是交替路径（path 和 walk 的区别在于 path 只使用每个顶点一次，而 walk 可以多次使用每个顶点）。
如果步行是一条路径，则您有一条交替路径并完成。
如果不是，那么行走会多次使用某个顶点。您可以删除两次访问该顶点之间的步行部分，并获得一个新图（删除了部分顶点）。在这个新图中，你必须再次进行整个搜索，如果你在新图中找到一条交替路径，你可以 "lift" 它到原始图的交替路径。
进入这个（关键的）最后一步的细节对于 Whosebug 的答案来说有点太多了，但你可以在 Wikipedia 上找到更多细节，也许这个高级概述有助于你理解数学文章越多。
从头开始实施将非常具有挑战性。
对于加权版本（使用欧几里得距离），埃德蒙兹算法有一个更复杂的变体可以处理权重。 Kolmogorov 提供了 C++ 实现和随附的论文。这也可用于未加权的情况，因此使用此实现可能是个好主意（即使它不在 java 中，也应该有某种方式与之交互）。
由于您的权重是基于欧几里德距离的，因此可能有针对这种情况的专门算法，但我上面提到的更通用的版本也可以使用，并且可以实现。
我有一个由节点和边组成的数据集。 节点代表人，边代表人与人之间的关系，每个人都有一个使用欧氏距离计算的成本。
现在我希望通过它们各自的边将这些节点匹配在一起，其中只有一个约束：
- 任何节点只能与一个其他节点匹配。
现在我们知道我正在处理一般图，理论上每个节点都可以与数据集中的任何节点匹配，只要它们之间有一条边。
我想做的是找到具有最大匹配和最小总成本的解决方案。
Node A
Node B
Node C
Node D
- Edge 1:
Start: End Cost
Node A Node B 0.5
- Edge 2:
Start: End Cost
Node B Node C 1
- Edge 3:
Start: End Cost
Node C Node D 0.5
- Edge 2:
Start: End Cost
Node D Node A 1
这个问题的解决方案如下：
分配边 1 和边 3，因为这是匹配的最大数量（在这种情况下，显然只有 2 个解决方案，但可能有大量分支边到其他节点）
边 1 和边 3 被分配，因为它是具有最大匹配数量和最小总成本的解决方案 (1)
我研究了很多算法，包括 Hungarian、Blossom、Minimal-cost flow，但我不确定哪种算法最适合这种情况。此外，似乎有很多 material 可以解决二分图中的此类问题，但在这件事上并非如此。
所以我问你：
在这种情况下，哪种算法最好 return (a) 匹配的最大数量和 (b) 总成本最低。
你知道什么好的material（也许是一些容易理解的伪代码），作为你推荐的算法吗？我数学符号不是最强的
对于(a)，最合适的算法（理论上有更快的算法，但它们更难理解）是Edmonds 的Blossom 算法。不幸的是它相当复杂，但我会尽力解释基础。
基本思想是进行匹配，并通过进行一些局部更改来不断改进它（增加匹配节点的数量）。关键概念是 交替路径 ：从一个不匹配的节点到另一个不匹配的节点的路径，属性 边缘在匹配中和匹配之外交替.
如果你有一个交替路径，那么你可以通过翻转交替路径中边的状态（无论它们是否在匹配中）来增加匹配的大小。
如果存在交替路径，则匹配不是最大的（因为路径为您提供了增加匹配大小的方法），相反，您可以证明如果没有交替路径，则匹配是最大的。因此，要找到最大匹配，您需要做的就是找到一条交替路径。
在二分图中，这很容易做到（可以用 DFS 做到）。在一般图形中，这更复杂，这是埃德蒙兹的 Blossom 算法出现的原因。粗略地说：
构建一个新图，如果你可以通过首先遍历匹配中的边，然后遍历匹配中的边，从 u 到 v，两个顶点之间有一条边' t.
在这个图中，尝试找到一条从不匹配的顶点到具有不匹配的邻居（即原始图中的邻居）的匹配顶点的路径。
你找到的路径中的每条边对应于原始图的两条边（即匹配中的一条边和匹配中的一条边），因此路径转换为新图中的交替行走，但是这个不一定是交替路径（path 和 walk 的区别在于 path 只使用每个顶点一次，而 walk 可以多次使用每个顶点）。
如果步行是一条路径，则您有一条交替路径并完成。
如果不是，那么行走会多次使用某个顶点。您可以删除两次访问该顶点之间的步行部分，并获得一个新图（删除了部分顶点）。在这个新图中，你必须再次进行整个搜索，如果你在新图中找到一条交替路径，你可以 "lift" 它到原始图的交替路径。
进入这个（关键的）最后一步的细节对于 Whosebug 的答案来说有点太多了，但你可以在 Wikipedia 上找到更多细节，也许这个高级概述有助于你理解数学文章越多。
从头开始实施将非常具有挑战性。
对于加权版本（使用欧几里得距离），埃德蒙兹算法有一个更复杂的变体可以处理权重。 Kolmogorov 提供了 C++ 实现和随附的论文。这也可用于未加权的情况，因此使用此实现可能是个好主意（即使它不在 java 中，也应该有某种方式与之交互）。
由于您的权重是基于欧几里德距离的，因此可能有针对这种情况的专门算法，但我上面提到的更通用的版本也可以使用，并且可以实现。