5 c# java algorithm graph-theory 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)
我研究了很多算法，包括匈牙利算法、Blossom 算法、最小成本流算法，但我不确定哪种算法最适合这种情况。此外，似乎有大量的材料可以解决二分图中的此类问题，但事实并非如此。
所以我问你：
在这种情况下，哪种算法最能返回 (a) 最大匹配数量和 (b) 总成本最低。
您是否知道任何适合您推荐算法的好材料（也许是一些易于理解的伪代码）？我不是数学符号方面最强的。
对于 (a)，最合适的算法（理论上有更快的算法，但它们更难以理解）是 Edmonds 的 Blossom 算法。不幸的是它相当复杂，但我会尽力解释其基础。
基本思想是进行匹配，并通过进行一些局部更改来不断改进它（增加匹配节点的数量）。关键概念是交替路径：从一个不匹配的节点到另一个不匹配的节点的路径，具有边在匹配内和匹配外之间交替的属性。
如果您有交替路径，则可以通过翻转交替路径中边的状态（无论它们是否处于匹配状态），将匹配的大小增加一。
如果存在交替路径，则匹配不是最大的（因为该路径为您提供了增加匹配大小的方法），相反，您可以证明如果不存在交替路径，则匹配是最大的。因此，要找到最大匹配，您需要做的就是找到替代路径。
在二分图中，这很容易做到（可以用DFS来完成）。在一般图表中，这更加复杂，这就是 Edmonds 的 Blossom 算法的用武之地。粗略地说：
构建一个新图，如果可以通过首先遍历匹配中的边，然后遍历不在匹配中的边从 u 到 v，则两个顶点之间有一条边。
在此图中，尝试找到从不匹配顶点到具有不匹配邻居（即原始图中的邻居）的匹配顶点的路径。
您找到的路径中的每条边都对应于原始图的两条边（即匹配中的一条边和匹配中的一条以外的边），因此该路径转换为新图中的交替行走，但这不一定是交替行走路径（路径和步行之间的区别是路径仅使用每个顶点一次，但步行可以多次使用每个顶点）。
如果步行是一条路径，则有一条替代路径并且完成。
如果不是，则行走多次使用某个顶点。您可以删除两次访问该顶点之间的步行部分，并获得一个新图（删除了部分顶点）。在这个新图表中，您必须再次进行整个搜索，如果您在新图表中找到替代路径，您可以将其“提升”到原始图表的替代路径。
对于 stackoverflow 的答案来说，深入了解这个（关键的）最后一步的细节有点太多了，但你可以在维基百科上找到更多细节，也许这个高级概述可以帮助你理解更多的数学文章。
从头开始实施这一点将非常具有挑战性。
对于加权版本（使用欧几里德距离），埃德蒙兹算法有一个更复杂的变体可以处理权重。Kolmogorov提供了 C++ 实现和随附的论文。这也可以用于未加权的情况，因此使用这个实现可能是一个好主意（即使它不在 java 中，也应该有某种方法与其交互）。
由于您的权重基于欧几里德距离，因此可能有针对这种情况的专门算法，但我上面提到的更通用的版本也可以工作，并且可以实现。