1. 序章

多くの場合、一方のセットのできるだけ多くの要素がもう一方のセットの要素に関連付けられるように、2つの異なるデータセットを一致させる必要があります。

たとえば、利用可能なスロットに予定をスケジュールすることを想像してください。 教授が相談に利用できる時間枠が決まっていて、それを利用したい学生がたくさんいる場合は、これらを組み合わせる最も効率的な方法を見つける必要があります。

2. 最大二部マッチング

2部グラフは、グラフ理論の特殊なケースです。これは、すべての頂点が2つの異なるセットのいずれかにあり、しばしばとと呼ばれ、すべてのエッジがとの間で接続されるためです。 照合している2つのデータセットを2つのセットとと見なすことができます。 その場合、2つの間のエッジが許可された接続になります。

たとえば、教授のタイムスロットと学生の場合、の頂点は個々の学生であり、の頂点は使用可能なスロットであり、エッジは各学生が使用できるタイムスロットを示します。

グラフ理論でのマッチングは、独立したエッジセットとも呼ばれ、2つのエッジが同じ頂点を共有しないエッジの組み合わせです。 これは多くの場合、この要件を満たすために可能なすべてのエッジのサブセットになります。 「最大マッチング」とは、可能な限り多くのエッジを持つマッチングです。 「完全一致」とは、グラフ内のすべての頂点を使用するものであり、したがって、達成できる最大の一致です。

したがって、2部グラフの最大一致は、2つの異なるセット間の可能なリンクの最大数であるため、すべてのリンクは異なる頂点のセット間にあります。 これは事実上、2つの関連するセット間のペアリングの最大数であるため、これは非常に便利な概念です。 たとえば、学生と予約枠の間のように。

3. ホップクロフト-カープアルゴリズム

Hopcroft-Karpアルゴリズムは、特定の2部グラフの最大マッチングを生成するアルゴリズムです。 これは、1973年にジョンホップクロフトとリチャードカープによって開発されました。

アルゴリズムはフェーズで機能し、各フェーズは増加する長さの拡張パスを探します。拡張パスは、一致しない頂点で開始および終了する任意のパスであり、パス内のエッジが一致しないものと一致するものの間で交互になります。 これらのパスには常に奇数のエッジがありますが、サイズは1以上である可能性があります。

見つかった各パスを使用して、これまでのマッチングを増やします。これを行うには、以前に一致したすべてのエッジをマッチングから削除しながら、以前に一致しなかったすべてのエッジをマッチングに追加します。 これは、見つかったパスごとにマッチングのサイズを1ずつ増やす効果があります。

たとえば、次のことから始めた場合：

ここでは、頂点との間に単一のパスがあります。 から移動する新しいパスを見つけて、これをマッチングに追加できます。 そうすることで、次のようになります。

ここでは、それがマッチングから削除され、追加されていることがわかります。 最終結果は、マッチングに2つのパスがあることです。

4. アルゴリズム

アルゴリズムはフェーズで機能し、各フェーズでグラフ全体で多数の検索を実行します。の頂点の観点からもすべてを実行するため、必要なステップ数を簡素化できます。

入力として必要なのはグラフ自体だけです。 具体的には、のどの頂点がのどの頂点に接続するかの詳細。 アルゴリズム全体を通して、マッチングも追跡します。 具体的には、現在、の頂点がの頂点とペアになっていますが、両側からこれにアクセスできる必要があります。

フェーズごとに、さらに、発見した現在のパスを追跡します。 これは、の各頂点のパスに沿った距離として記録されます。 の頂点への接続方法の観点からのみ考慮されるため、の頂点の距離を記録する必要はありません。

4.1. 全体的なアルゴリズム

全体的なアルゴリズムは、いくつかの一般的な設定から始まり、フェーズでグループ化されたいくつかの検索を実行します。 各フェーズで、グラフ全体の幅優先探索を実行して、グラフに存在する拡張パスを検出します。 次に、現在一致していない各頂点から開始して、適切な拡張パスを構築し、一致を更新するために、深さ優先探索をいくつか実行します。

グラフの一部ではないが、アルゴリズムで使用される特別な頂点もあります。 これはNILと呼ばれ、これを使用しては、グラフ内の頂点が現在何ともペアになっていないことを示します。

各フェーズの開始時に、グラフ全体で幅優先探索を実行して、拡張パスが存在するかどうかとその長さを検出します。. パスが見つからなかったことを示す特別なNIL頂点までの距離を計算しなかった場合は、すぐに停止します。 これは、可能な限り最良のマッチングにすでに到達していることを意味します。

拡張パスが見つかった場合は、マッチングを拡張します。これは、現在ペアになっていないすべての頂点を反復処理し、そこからグラフ全体で深さ優先探索を実行することによって行われます。 この一環として、マッチングを更新し、必要に応じてエッジをスワップインおよびスワップアウトします。

4.2. 幅優先探索

各フェーズの最初の部分は、幅優先探索です。 すべての頂点を繰り返して展開し、可能なすべての拡張パスを検出します：

最初に、現在マッチングの一部ではないすべての頂点を検出し、それらを作業キューに追加します。 次に、このキューを繰り返し処理し、各頂点を順番に確認します。

これらのそれぞれについて、グラフから接続されているすべての頂点を反復処理します。 現在、これとペアになっている頂点が見つかります。これは、特別なNIL頂点である可能性があります。 この距離をまだ計算していない場合は、計算して作業キューに追加します。

次に、調べる頂点がなくなるまでこれを繰り返します。 この時点で、現在の状態からグラフを介して可能なすべての拡張パスがわかったので、次のステップの準備が整いました。

4.3. 深さ優先探索

現在の拡張パスのセットを生成したら、それらの拡張を開始します。 これを行うには、現在マッチングの一部ではない各頂点から、グラフ全体で深さ優先探索を実行します。。これを行うときに、マッチングを更新します によると:

5. 実例

これは複雑なので、それに従うための最良の方法は実際に協力することです。 ここでは、デモンストレーションを短くするために非常に単純なグラフを使用していますが、任意のサイズのグラフに拡張されます：

このグラフには、両側に2つの頂点があり、それらの間に3つのエッジがあります。 たとえば、午前と午後の予約が可能な教授と、それらを利用したい2人の学生を表すことができます。

5.1. フェーズ1

最初の幅優先探索を実行すると、グラフを通る単一の拡張パスが検出されます。これは頂点との間です。 可能なパスはすでに使用されている頂点のみを使用しているため、頂点またはを使用しているパスは見つかりません。

この後、との両方から開始して深さ優先探索を実行します。 から始まる検索はマッチングにエッジを追加し、から始まる検索は何も追加しません。

5.2. フェーズ2

2番目の幅優先探索は、代わりに上のグラフから開始されます。 この場合、パスはすでに一致しているため、からのパスを調査する必要はありません。代わりに、から開始します。 これで、。から移動する拡張パスが検出されます。

この後、深さ優先探索を再度実行します。 前と同じように、これはすでにマッチングに含まれているため、これを行うだけです。これにより、マッチングに追加され、同時にマッチングから削除されます。

5.3. フェーズ3

3番目の幅優先探索では、両方がすでに含まれているため、開始する頂点がありません。これは、処理を停止し、これまでに検出した一致を返すことを意味します。 上記を見ると、これが最適なマッチングであることがすでにわかります。

6. 概要

この記事では、2つのデータセットを一致させて、それらの間の最も効果的な一致を検出する方法を学びました。小規模で機能することを示しましたが、同等に効果的に機能します。はるかに大きなグラフでも同様です。