質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.49%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

2回答

533閲覧

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

SmaSTATION

総合スコア29

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2024/02/20 23:45

編集2024/02/22 23:18

実現したいこと

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

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

現状の状況を整理です。

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

該当のソースコード

C++

1#include <iostream> 2#include <vector> 3#include <queue> 4#include <algorithm> 5using namespace std; 6 7 8struct HopcroftKarp { 9 int sizeL, sizeR; 10 vector<vector<int> > list; // left to right 11 12 // result 13 vector<bool> seen, matched; 14 vector<int> level, matching; 15 16 // base 17 HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector<int>()) { } 18 inline vector<int>& operator [] (int i) { return list[i]; } 19 inline void addedge(int from, int to) { list[from].push_back(to); } 20 inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) { 21 s << endl; 22 for (int i = 0; i < G.list.size(); ++i) { 23 s << i << " : "; 24 for (int j = 0; j < G.list[i].size(); ++j) { 25 s << G.list[i][j]; 26 if (j + 1 != G.list[i].size()) s << ", "; 27 } 28 s << endl; 29 } 30 return s; 31 } 32 33 // methods 34 void hobfs() { 35 queue<int> que; 36 for (int left = 0; left < sizeL; ++left) { 37 level[left] = -1; 38 if (!matched[left]) { 39 que.push(left); 40 level[left] = 0; 41 } 42 } 43 level[sizeL] = sizeL; 44 while (!que.empty()) { 45 int left = que.front(); 46 que.pop(); 47 for (int i = 0; i < list[left].size(); ++i) { 48 int right = list[left][i]; 49 int next = matching[right]; 50 if (level[next] == -1) { 51 level[next] = level[left] + 1; 52 que.push(next); 53 } 54 } 55 } 56 } 57 bool hodfs(int left) { 58 if (left == sizeL) return true; 59 if (seen[left]) return false; 60 seen[left] = true; 61 for (int i = 0; i < list[left].size(); ++i) { 62 int right = list[left][i]; 63 int next = matching[right]; 64 if (level[next] > level[left] && hodfs(next)) { 65 matching[right] = left; 66 return true; 67 } 68 } 69 return false; 70 } 71 int solve() { 72 seen.assign(sizeL, false); 73 matched.assign(sizeL, false); 74 level.assign(sizeL+1, -1); 75 matching.assign(sizeR, sizeL); 76 int res = 0; 77 while (true) { 78 hobfs(); 79 seen.assign(sizeL, false); 80 bool finished = true; 81 for (int left = 0; left < sizeL; ++left) { 82 if (!matched[left] && hodfs(left)) { 83 matched[left] = true; 84 ++res; 85 finished = false; 86 } 87 } 88 if (finished) break; 89 } 90 return res; 91 } 92}; 93 94const int dx[4] = {1, 0, -1, 0}; 95const int dy[4] = {0, 1, 0, -1}; 96 97int main() { 98 int R, C; cin >> R >> C; 99 vector<string> fi(R); 100 for (int i = 0; i < R; ++i) cin >> fi[i]; 101 102 HopcroftKarp hk(R*C, R*C); 103 int V = R*C; 104 for (int i = 0; i < R; ++i) { 105 for (int j = 0; j < C; ++j) { 106 int left = i * C + j; 107 cout << "left=" << left << endl; 108 cout << "i=" << i << endl; 109 cout << "j=" << j << endl; 110 if (fi[i][j] == '*') { 111 --V; 112 continue; 113 } 114 if ( (i + j) % 2 == 1 ) continue; 115 for (int dir = 0; dir < 4; ++dir) { 116 int ni = i + dx[dir], nj = j + dy[dir]; 117 cout << "ni=" << ni << endl; 118 cout << "nj=" << nj << endl; 119 if (ni < 0 || ni >= R || nj < 0 || nj >= C) continue; 120 cout << "fi[ni][nj]=" << fi[ni][nj] << endl; 121 if (fi[ni][nj] == '*') continue; 122 int right = ni * C + nj; 123 cout << "right=" << right << endl; 124 hk.addedge(left, right); 125 } 126 } 127 } 128 auto res = hk.solve(); 129 cout << V - res << endl; 130}

試したこと・調べたこと

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

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

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

補足

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ikedas

2024/02/21 00:46

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

2024/02/21 06:01 編集

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

2024/02/21 06:43

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

2024/02/21 09:41 編集

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

2024/02/22 23:54

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

回答2

0

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

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


#1

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

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

#2

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

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

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

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

#3

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

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


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

投稿2024/02/22 04:04

編集2024/02/23 10:35
ikedas

総合スコア4306

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

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

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

c++

1 // 初期条件 (頂点 0 を初期ノードとする) 2 dist[0] = 0; 3 que.push(0); // 0 を橙色頂点にする 4 5 // BFS 開始 (キューが空になるまで探索を行う) 6 while (!que.empty()) { 7 int v = que.front(); // キューから先頭頂点を取り出す 8 que.pop(); 9 10 // v から辿れる頂点をすべて調べる 11 for (int nv : G[v]) { 12 if (dist[nv] != -1) continue; // すでに発見済みの頂点は探索しない 13 14 // 新たな白色頂点 nv について距離情報を更新してキューに追加する 15 dist[nv] = dist[v] + 1; 16 que.push(nv); 17 } 18 }

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

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

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

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

つまり、幅優先探索が理解できていれば、上記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「左」の頂点から辺をたどって到達できる「右」の頂点(複数)
seenhodfs()で「左」の頂点が探索済みかの判定に使う
matched「左」の頂点がマッチングに含まれるか
level「左」の頂点にたどり着くまでに何セットの移動が必要か
matching「右」の頂点からマッチング内の辺をたどって到達できる「左」の頂点

投稿2024/02/21 14:01

編集2024/02/24 11:28
actorbug

総合スコア2224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

SmaSTATION

2024/02/25 00:21

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだベストアンサーが選ばれていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.49%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問