重み付けされていない二部グラフで最大一致サイズを見つけるために、拡張パスまたはクーンのアルゴリズムを読んでいました。
アルゴリズムは、一致しない頂点で開始および終了する交互パス (一致しないエッジと一致するエッジを交互に含む) を見つけようとします。代替パスが見つかった場合、パスが拡張され、一致するカウントが 1 増加します。
アルゴリズムは理解できますが、一般的な実装方法を理解するのに問題があります。これがリファレンス実装です - https://sites.google.com/site/indy256/algo/kuhn_matching2。
各段階で、左側の一致しない頂点から始まる代替パスを見つけようとする必要があります。ただし、指定された実装では、次のコードに示すように、反復ごとに、すべての一致しない頂点を可能な開始位置として試す代わりに、1 つの一致しない頂点のみから検索を開始します。
for (int u = 0; u < n1; u++) {
if (findPath(graph, u, matching, new boolean[n1]))
++matches;
}
このようにして、反復中に一致しない左側の頂点が再試行されることはありません。なぜこれが最適なのか理解できませんか？