ホップクロフト・カープ法 (Hopcroft–Karp Algorithm)の概要とアルゴリズム及び実装例

ホップクロフト・カープ法 (Hopcroft–Karp Algorithm)の概要

ホップクロフト・カープ法（Hopcroft–Karp Algorithm）は、二部グラフにおける最大マッチング（Maximum Matching）を効率的に求めるアルゴリズムとなる。

ここでの「マッチング」とは、グラフ中の辺の集合であり、隣接する辺が互いに重ならないように選ばれたものを指す。そして「最大マッチング」は、可能なマッチングの中で、もっとも多くの辺を選んだ集合となる。

この問題に対して、アルゴリズムは増加路（augmenting path）と呼ばれる経路を用いたアプローチを採る。特に本手法では、「交互路（alternating path）」を探索することで、既存のマッチングを拡張していく。

処理の要点は以下の通り

1. 幅優先探索（BFS）によって、グラフ上にレイヤー（層）構造を形成する。これにより、各ノードの距離が明示され、短い増加路を優先的に見つけることが可能になる。

2. 次に、深さ優先探索（DFS）を用いて、このレイヤー構造に基づいて複数の増加路を同時に探索する。

3. 増加路が発見されるたびに、マッチングを更新する。

4. 増加路がこれ以上存在しない状態になるまで、これらの探索と更新を繰り返す。

このアルゴリズムの大きな特徴は、1回の処理で複数の増加路を同時に処理することで高速化を図っている点にある。

計算量

本アルゴリズムは、以下の時間計算量を持つ。

• 時間計算量：O(√V × E)（ここで、V は頂点数、E は辺の数）

これは、単純に1本ずつ増加路を探索していく従来の方法（O(VE)）に比べて、大幅に高速であることを意味している。したがって、大規模な二部グラフに対しても、実用的な計算速度で最大マッチングを求めることが可能となる。

関連するアルゴリズム

ホップクロフト・カープ法（Hopcroft–Karp Algorithm）に関連するアルゴリズムとして、以下のような マッチング問題 や グラフ理論 に関連する手法が存在している。

関連アルゴリズム

1. フォード・ファルカーソン法（Ford–Fulkerson Algorithm）

• 最大フロー問題 を解くアルゴリズム。

• 二部グラフの最大マッチング問題を最大フロー問題に帰着して解くことも可能。

• 時間計算量：O(max_flow * E)

• 欠点：実装が単純だが、非効率な場合もある（無限ループの危険など）

2. ハンガリアン法（Hungarian Algorithm）

• **重み付き二部グラフの最小重み完全マッチング（割当問題）**を解くアルゴリズム。

• 時間計算量：O(n^3)

• 主にコスト最小化（例：仕事割り当て）に使用される。

3. ブロッサム法（Edmonds’ Blossom Algorithm）

• 一般グラフにおける最大マッチングを解くアルゴリズム（非二部グラフ対応）。

• 奇数長のサイクル（ブロッサム）を縮約して処理する。

• 時間計算量：O(V^3)

• 二部グラフでない場合はこちらが必要。

4. Kuhn’s Algorithm（クーンのアルゴリズム）

• 二部グラフのマッチングをDFSで求める古典的な方法。

• 時間計算量：O(VE)

• ホップクロフト・カープ法はこのクーン法を高速化したもの。

5. Dinic’s Algorithm（ディニックのアルゴリズム）

• フローアルゴリズムだが、Hopcroft–Karpと類似した「層状グラフ＋増加路」の考え方を持つ。

• 単位容量のネットワークに対して、最大マッチングを求めるのにも使える。

• 時間計算量：O(E√V)（単位容量）

6. Push-Relabel Algorithm（プッシュ・リレーベル法）

• 最大フロー問題における別アプローチ。

• マッチングそのものよりも、フロー→マッチング変換の観点で関連。

応用実装例

以下に、ホップクロフト・カープ法（Hopcroft–Karp Algorithm） の具体的な応用実装例として、「求職者と職のマッチング」問題を Python で実装した例を示す。

問題設定：求職者と職の最適マッチング

• 二部グラフの左側：求職者 U = {u1, u2, u3, ...}

• 右側：職（仕事）V = {v1, v2, v3, ...}

• 辺 (ui, vj) が存在すると、ui は vj の職に適任とされる。

• 目的：マッチング数を最大化（可能な限り多くの求職者に仕事を割り当てる）

from collections import deque

class HopcroftKarp:
    def __init__(self, U, V, edges):
        self.U = U  # 求職者集合
        self.V = V  # 仕事集合
        self.G = {u: [] for u in U}
        for u, v in edges:
            self.G[u].append(v)

        self.pair_U = {u: None for u in U}
        self.pair_V = {v: None for v in V}
        self.dist = {}

    def bfs(self):
        queue = deque()
        for u in self.U:
            if self.pair_U[u] is None:
                self.dist[u] = 0
                queue.append(u)
            else:
                self.dist[u] = float('inf')
        found = False
        while queue:
            u = queue.popleft()
            for v in self.G[u]:
                if self.pair_V[v] is None:
                    found = True
                elif self.dist[self.pair_V[v]] == float('inf'):
                    self.dist[self.pair_V[v]] = self.dist[u] + 1
                    queue.append(self.pair_V[v])
        return found

    def dfs(self, u):
        for v in self.G[u]:
            pu = self.pair_V[v]
            if pu is None or (self.dist[pu] == self.dist[u] + 1 and self.dfs(pu)):
                self.pair_U[u] = v
                self.pair_V[v] = u
                return True
        self.dist[u] = float('inf')
        return False

    def max_matching(self):
        matching = 0
        while self.bfs():
            for u in self.U:
                if self.pair_U[u] is None and self.dfs(u):
                    matching += 1
        return matching

使用例

# 求職者と仕事の定義
U = ['Alice', 'Bob', 'Charlie']
V = ['Job1', 'Job2', 'Job3']
edges = [
    ('Alice', 'Job1'),
    ('Alice', 'Job2'),
    ('Bob', 'Job2'),
    ('Charlie', 'Job3')
]

hk = HopcroftKarp(U, V, edges)
max_match = hk.max_matching()

print(f"最大マッチング数: {max_match}")
print("マッチング結果:")
for u in U:
    if hk.pair_U[u]:
        print(f"  {u} → {hk.pair_U[u]}")

出力例

最大マッチング数: 3
マッチング結果:
  Alice → Job1
  Bob → Job2
  Charlie → Job3

適用事例

ホップクロフト・カープ法（Hopcroft–Karp Algorithm）は、二部グラフにおける最大マッチング問題を高速に解くアルゴリズムとして、さまざまな実社会のマッチング問題に応用されている。以下に、その具体的な適用分野と活用事例について述べる。

適用事例と分野別活用

1. 求職者と求人の最適マッチング

企業のポジションと求職者のスキル・希望条件の適合を二部グラフでモデル化し、最適な職業配置を実現する。

• • 活用例：Indeed、リクルート、LinkedIn などの就職支援プラットフォーム

  • 特徴：リアルタイムな自動マッチングやスカウト機能の基盤として機能

2. 学生と学校・研究室の割り当て

学生の志望・成績・適性と、学科・研究室の要件との関係をグラフ化し、最適な進路決定や配属に活用。

• • 活用例：日本のAO入試、米国NRMP（医学部マッチング）

  • 特徴：公平性のある選抜や定員超過・未達の回避に寄与

3. タスク割り当て（ジョブスケジューリング）

作業者・ロボットと処理すべきタスクの適合関係に基づいて、効率的なリソース配分を実現。

• • 活用例：工場の自動化ライン、物流センターの作業最適化（Amazon など）

  • 特徴：スループット向上、人的コスト削減、ロス削減

4. マルチプレイヤー・イベントのマッチング

オンラインゲームやイベントでの参加者同士の公平な組み合わせ・対戦相手選定に応用。

• • 活用例：eスポーツ大会のトーナメント編成、マッチングアプリの候補選出

  • 特徴：希望条件・プレイスタイルに基づいた最適な相手探し

5. 自然言語処理（NLP）と知識ベースの結合

文章中のキーフレーズと知識ベースのエンティティを対応付けるための意味的マッチングにも利用される。

• • 活用例：エンティティリンク、質問応答システム、レコメンデーションエンジン

  • 特徴：言語と知識の橋渡しにより検索・対話の精度向上

6. 医療マッチング（患者と医療リソース）

患者の症状や希望と、医師や病院の専門領域・空き状況を組み合わせ、迅速かつ的確な医療提供を支援。

• • 活用例：LINEヘルスケア、地域医療連携システム

  • 特徴：地域・時間帯・診療科に応じた最適配置

7. クラウド・コンピューティングでのリソース最適化

処理ジョブと仮想マシン（VM）やコンテナの能力・時間帯の関係性から、自動スケジューリングと負荷分散を実現。

• • 活用例：Kubernetes、AWS/GCPのオーケストレーション

  • 特徴：リアルタイム処理、リソース効率の最大化、SLAの維持

分野別まとめ（対応構造）

応用と設計への発展

ホップクロフト・カープ法の導入は、上記のような一対一対応関係が重要な問題において、極めて有効なアプローチです。アルゴリズム自体がシンプルかつスケーラブルであるため、

• UIフローへの統合（例：求人検索における即時候補提示）

• バックエンドマッチングエンジンの最適化

• 推薦アルゴリズムや自然言語処理との組み合わせ

といった応用設計も容易で、どの分野において詳しく掘り下げるか、ご希望があればその設計支援も可能となっている。

参考図書

ホップクロフト・カープ法（Hopcroft–Karp Algorithm）に関する参考文献について述べる。

1. 基礎理論・アルゴリズムの原典

● Hopcroft, J. E., & Karp, R. M. (1973)

Title: An n^5/2 Algorithm for Maximum Matchings in Bipartite Graphs
Published in: SIAM Journal on Computing, Vol. 2, No. 4
概要:
ホップクロフト・カープ法の元論文。二部グラフにおける最大マッチングを O(√V * E) で解く方法を初めて提示。

2. アルゴリズム全般の教科書

● 『Introduction to Algorithms』(CLRS)

著者: Cormen, Leiserson, Rivest, Stein
出版社: MIT Press
概要:
定番のアルゴリズム教科書。マッチングアルゴリズムの理論と流れの章でホップクロフト・カープ法も簡潔に解説。
対象者: 学部〜大学院レベル

● 『Algorithm Design』

著者: Jon Kleinberg & Éva Tardos
出版社: Pearson
概要:
マッチングとネットワークフローの章で実際的な応用を含めて詳述。理論よりも直感に訴えるスタイル。
対象者: 応用や設計観点で学びたい人向け

3. 実装・競技プログラミング向け

● 『競技プログラミングの鉄則』

著者: 渡部有隆
出版社: マイナビ出版
概要:
最大マッチングを求めるDFSベースの解法から始まり、ホップクロフト・カープ法へ段階的に導入。Python・C++実装例あり。

● CP-Algorithms（Competitive Programming Algorithms）

概要:
ホップクロフト・カープを含むマッチングアルゴリズムのコード・可視化・理論がまとまった実践向けサイト。
言語: C++中心（一部Pythonあり）

4. 応用と研究への橋渡し

● 『Graph Theory and Its Applications』

著者: Jonathan L. Gross, Jay Yellen
概要:
グラフ理論の一般的応用をカバー。マッチング問題の応用事例や数学的背景も整理されている。
対象者: 応用数学・情報科学分野の研究者

5. その他オンラインリソース（無料）

補足：他の学術的参考文献

• Edmonds, J. (1965). Paths, Trees, and Flowers（→ ブロッサム法の原典）

• Tarjan, R. E. (1975). Efficiency of a Good But Not Linear Set Union Algorithm