Hopcroft-karpの幅優先探索がわからない

Question

実現したいこと

この問題のプログラムの34行目から始まる深さ優先探索のやっていることの見当がつかず、ヘルプをいただきたいです。
参照サイト
広告を打つ位置を探索で求める問題です。

発生している問題・分からないこと

現状の状況を整理です。

• 全ての頂点を探索して、「left」「right」を割り振り、両方ある頂点ではその「left」「right」で重さ1の辺を張ることまでは理解済み
• その後、この辺分だけ幅優先をし最大マッチング数を求めて頂点数から引くことで答えが求まるのも納得済み
• この幅優先の部分の探索方法がわからないです

該当のソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


struct HopcroftKarp {
    int sizeL, sizeR;
    vector<vector<int> > list; // left to right
    
    // result
    vector<bool> seen, matched;
    vector<int> level, matching;
    
    // base
    HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector<int>()) { }
    inline vector<int>& operator [] (int i) { return list[i]; }
    inline void addedge(int from, int to) { list[from].push_back(to); }
    inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) {
        s << endl;
        for (int i = 0; i < G.list.size(); ++i) {
            s << i << " : ";
            for (int j = 0; j < G.list[i].size(); ++j) {
                s << G.list[i][j];
                if (j + 1 != G.list[i].size()) s << ", ";
            }
            s << endl;
        }
        return s;
    }
    
    // methods
    void hobfs() {
        queue<int> que;
        for (int left = 0; left < sizeL; ++left) {
            level[left] = -1;
            if (!matched[left]) {
                que.push(left);
                level[left] = 0;
            }
        }
        level[sizeL] = sizeL;
        while (!que.empty()) {
            int left = que.front();
            que.pop();
            for (int i = 0; i < list[left].size(); ++i) {
                int right = list[left][i];
                int next = matching[right];
                if (level[next] == -1) {
                    level[next] = level[left] + 1;
                    que.push(next);
                }
            }
        }
    }
    bool hodfs(int left) {
        if (left == sizeL) return true;
        if (seen[left]) return false;
        seen[left] = true;
        for (int i = 0; i < list[left].size(); ++i) {
            int right = list[left][i];
            int next = matching[right];
            if (level[next] > level[left] && hodfs(next)) {
                matching[right] = left;
                return true;
            }
        }
        return false;
    }
    int solve() {
        seen.assign(sizeL, false);
        matched.assign(sizeL, false);
        level.assign(sizeL+1, -1);
        matching.assign(sizeR, sizeL);
        int res = 0;
        while (true) {
            hobfs();
            seen.assign(sizeL, false);
            bool finished = true;
            for (int left = 0; left < sizeL; ++left) {
                if (!matched[left] && hodfs(left)) {
                    matched[left] = true;
                    ++res;
                    finished = false;
                }
            }
            if (finished) break;
        }
        return res;
    }
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
    int R, C; cin >> R >> C;
    vector<string> fi(R);
    for (int i = 0; i < R; ++i) cin >> fi[i];

    HopcroftKarp hk(R*C, R*C);
    int V = R*C;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            int left = i * C + j;
            cout << "left=" << left << endl;
            cout << "i=" << i << endl;
            cout << "j=" << j << endl;
            if (fi[i][j] == '*') {
                --V;
                continue;
            }
            if ( (i + j) % 2 == 1 ) continue;
            for (int dir = 0; dir < 4; ++dir) {
                int ni = i + dx[dir], nj = j + dy[dir];
                cout << "ni=" << ni << endl;
                cout << "nj=" << nj << endl;
                if (ni < 0 || ni >= R || nj < 0 || nj >= C) continue;
                cout << "fi[ni][nj]=" << fi[ni][nj] << endl;
                if (fi[ni][nj] == '*') continue;
                int right = ni * C + nj;
                cout << "right=" << right << endl;
                hk.addedge(left, right);
            }
        }
    }
    auto res = hk.solve();
    cout << V - res << endl;
}

試したこと・調べたこと

• teratailやGoogle等で検索した
• ソースコードを自分なりに変更した
• 知人に聞いた
• その他

上記の詳細・結果

検索➔Hopcraftkarpの説明は出てくるも探索については説明なし

改変➔SIZELやSIZERを出力するもよくわからず。

補足

• おそらく、leftからrightへの「s-tパス」みたいなのを44行目以降あたりからやっているのかなとは思いつつ、「う～ん」という感じです。
• 𠮟咤激励含めてコメント・ご回答いただけると幸いです。

Comments

[ikedas]

他人の書いたソースコード (あなたが後から手を加えた場合も含む) を引用する場合、最低限、そのコードの出所を明記してください。出所とは、ウェブサイトならURL、書籍なら著者名、標題、出版社、該当のページ番号、といったことです。
出所の明記などがない場合、著作権侵害等の権利侵害となることがあります。今後質問する際も気をつけてください。

[ikedas]

> 検索➔Hopcraftkarpの説明は出てくるも探索については説明なし
そうなんですか? 「Hopcroft-Karpの深さ優先探索」でウェブ検索すると、この探索アルゴリズムの解説はいろいろみつかるようですけど。

[SmaSTATION]

ご回答ありがとうございます。
次回から明記の件、しっかりとしていきます。ありがとうございます。

[ikedas]

質問文は編集できます。今回から明記してほしいです。

それと、
・「Hopcroft-Karp」の綴りがまちがっています。質問を見落とされるかもしれませんし、質問者さんの真剣さも疑われかねません。
・34行めからのメソッドは「BFS」という名前なのですが、深さ優先探索なのでしょうか。元々コードを書いた方もそうしていたのか、質問者さんが書き換えたりした結果こうなっているのか、どちらでしょうか。

[ikedas]

アルゴリズム名称の誤記を修正されたようですが、Karpは人名ですから最初が大文字です。

Answer 1

まず、ご提示のコードは (main関数を除き) 下記のものと同一のようです。

• https://drken1215.hatenablog.com/entry/2021/08/05/175900

出所を明記せずにコードだけ投げられましても、これが正しい動作をするコードなのかさえわかりません。もしも動作しないものだったらそれを読まされるほうはたまったものではありません。

---

#1

調べてみると、おなじ作者の同じコードに「verified」としてコンテストを通過したとみられる記述があります。したがって、このコードは信用してよいでしょう。

で、質問者さんがわからないとしているhobfs()というメソッドは、名前からして幅優先探索を実行するものでしょう。深さ優先探索を実行するものとして読んだら「分からない」のは当たり前です。

#2

もしかして上のようなことを聞きたいのではなく、なぜここで探索をするのかを聞きたいのでしょうか。

それは、Hopcroft-Karp アルゴリズムについての理解があればわかります。

上のリンク先のウィキペディアの解説を全部読みましょう。ここには、アルゴリズムの説明として、マッチングの各フェーズで幅優先探索1回と深さ優先探索複数回を実行することがのべられています。つまり、探索を実行している理由はそういうアルゴリズムだからです。

解説中の擬似コードをC++で書き直せば、ご提示のコードに近いものになりそうです。

#3

もしかして、「深さ優先探索」や「幅優先探索」がどういうものなのかが「わからない」ということなのでしょうか。もしもそうなら、自分で学んでくださいとしか言いようがないです。

ウィキペディアでいいので、それぞれの探索についての記事を全部読んでください。擬似コードなどものっていますから、今見ているソースコードと比較してみて、それぞれの探索がどのように使われているか確認してください。

---

アルゴリズムの実装についての質問をされるのなら、せめてそのアルゴリズムを理解してからにしてはどうでしょうか。

Answer 2

まず確認したいのは、幅優先探索を本当に理解しているか、ということです。
幅優先探索が理解できていれば「この問題のプログラムの34行目から始まる深さ優先探索のやっていることの見当がつかず」という事態にはなりません。
なぜなら、ご提示のコードは、一般的な幅優先探索のコードとほぼ一対一に対応するからです。

こちらの記事「BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜」から、「BFSの実装テンプレ」の実処理部分を引用させていただいて、比較してみましょう。

    // 初期条件 (頂点 0 を初期ノードとする)
    dist[0] = 0;
    que.push(0); // 0 を橙色頂点にする

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            dist[nv] = dist[v] + 1;
            que.push(nv);
        }
    }

以下のように一対一に対応することが分かります。

引用コード行	ご提示のコード行	説明(カッコ内はご提示のコード)
1-3	36-42	初期ノードのdist(level)を0にしてキューに登録
6	44	キューが空になるまで探索を行う
7-8	45-46	キューから先頭頂点を取り出す
11	47-49	v(left) から辿れる頂点をすべて調べる
12	50	すでに発見済みの頂点は探索しない
14-16	51-52	新たな白色頂点 nv(next) について距離情報を更新してキューに追加する

差分は以下項目のみとなります。

• 初期ノードが複数ある
• 辿れる頂点の計算方法が異なる(引用コードはGから、ご提示のコードはlistとmatchingから)

つまり、幅優先探索が理解できていれば、上記2点を直接質問するはずなのです。

もし幅優先探索が理解できていないのであれば、まずは上で引用したページの説明を読んで理解してから先に進むことをお勧めします。

---

基本的な考え方は、こちらで説明されているので、まずはこちらを読んで理解してください。

二部グラフの最大マッチングと増加道

Hopcroft-Karp algorithm は、こちらの方法の変種です。ものすごくざっくり説明すると、最短の増加道を、頂点が被らないように複数同時に選んで反転することで、反転回数を減らそうというものです。

まず、最短の増加道(頂点が被るのを許す)をすべて求めるためにhobfs()で幅優先探索し、その中から頂点が被らないものを選んで反転するためにhodfs()で深さ優先探索を行う、という流れになります。

hobfs()

現在のマッチングに使われていない「左」の頂点から開始する。(35-42行)
マッチング外の辺→マッチング内の辺の順番でたどって「左」の頂点に戻る移動(※)を1セットとしたとき、ある「左」の頂点にたどり着くまでに最短で何セットの移動が必要か(levelのこと)を幅優先探索で求める。(44-55行)

(※) 実際には、「マッチング外の辺→マッチング内の辺」ではなく「すべての辺→マッチング内の辺」の移動をしている。しかし、「マッチング内の辺→マッチング内の辺」とたどると元の頂点(処理済み)に戻るため、実質「マッチング外の辺→マッチング内の辺」しか処理されない。

ただし、マッチング外の辺をたどって「右」の頂点に行った後、マッチング内の辺が無くて「左」の頂点に戻れない場合は、特殊な頂点(sizeL)に到達するものとみなす。(75行)
特殊な頂点(sizeL)への最短移動距離については、最大の値sizeLをあらかじめ入れておく。こちらはhodfs()で使用する。(43行)

最終的に特殊な頂点(sizeL)に到達するルートが、最初に説明した「増加道」になっているというのが、このコードのポイントである。

hodfs()

「左」の頂点の1つ(引数で指定)から始めて、マッチング外の辺→マッチング内の辺の順番でたどる移動(levelが増える方向なら移動可(※))を繰り返して深さ優先探索する。(64行)

(※)「levelが増える方向なら移動可」という判定にしているため、特殊な頂点(sizeL)への移動は常に成功する。

最後に特殊な頂点(sizeL)に到達できるか判定する。(58行)
ただし、すでに探索済みの頂点は除く。(59-60行)
到達できたら、移動経路上の辺のマッチング内/外をすべて反転してtrueを返す。(65-66行)

solve()

hobfs()でlevelを求める。(78行)
現在のマッチングに使われていない「左」の頂点すべてについて、hodfs()を呼び、trueが返ってきたらマッチングを1つ増やす。(82-86行)
マッチングが1つも増えなかったら終了。(88行)

メンバ変数の説明

メンバ変数名	説明
sizeL	「左」の頂点の番号の最大値+1
sizeR	「右」の頂点の番号の最大値+1
list	「左」の頂点から辺をたどって到達できる「右」の頂点(複数)
seen	hodfs()で「左」の頂点が探索済みかの判定に使う
matched	「左」の頂点がマッチングに含まれるか
level	「左」の頂点にたどり着くまでに何セットの移動が必要か
matching	「右」の頂点からマッチング内の辺をたどって到達できる「左」の頂点

Comments

[SmaSTATION]

度々、追記の方ありがとうございます。大変、勉強になっております。