ひとりで勝手にはじめた蟻本読書会 幅優先探索と深さ優先探索 意外と奥が深い全探索 蟻本読書会の続きです。今回は深さ優先探索の補足です。
幅優先探索も深さ優先探索も最短経路アルゴリズムとしても活用できます。
（中略）
「グラフの頂点の順序に意味がある場合」とはどのような場合でしょうか？ 例えば辞書順最小な経路から順番に探索したい場合では深さ優先探索が効果的です。
また深さ優先探索は再帰呼び出しで短く処理を書くことができます。再帰呼び出しを繰り返すと同じ引数で何度も呼び出しが発生して処理にかかる時間が急激に増えてしまう場合があります。このような場合はメモ化再帰といって処理結果を別のところにメモしておき、また同じ引数が渡されたときは計算はしないでメモしておいた値を返すことで処理にかかる時間を減らすことができます。
最短経路を調べるだけなら幅優先探索でも深さ優先探索でもできるのですが、複雑な条件や構造を持つものを全探索したい場合は再帰呼び出しを用いた深さ優先探索をすることで効率よく解を求めることができる場合があります。
単純パスの最長経路
単純パスとは同じ頂点を複数回通らないパスのことです。
問題の趣旨は、
移動した先の区画の薄氷をかならず割るという条件で、東西南北のいずれかの方向に隣接しまだ割られていない薄氷のある区画に移動する。スタート地点を自由に選んでよい場合、移動回数の最大値はどうなるかを問う問題です。
最短経路問題ならぬ最長経路問題といってよさそうな問題ですが、ダイクストラ法をもちいた最短経路問題とちがってうまく処理を減らすことができないので全経路を探索する必要があります。
再帰呼び出しで深さ優先探索をしています。引数は移動先の座標と次の移動に成功した場合の移動回数（出発点から動かなくても1回成功したものとする）です。移動することで count が増えていくのでこの最大値を記録していき、最後にこれを出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
using System; using System.Collections.Generic; using System.Linq; class Program { static int ReadInt() => int.Parse(Console.ReadLine()); static int[] ReadIntArray() => Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); static void Main() { int W = ReadInt(); int H = ReadInt(); int[,] grid = new int[H, W]; for (int r = 0; r < H; r++) { int[] vs = ReadIntArray(); for (int c = 0; c < W; c++) grid[r, c] = vs[c]; } int ans = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r, c] == 1) Dfs(r, c, 1); } } Console.WriteLine(ans); void Dfs(int r, int c, int count) { if (grid[r, c] == 0) // 訪問済みまたは最初から訪問不可 return; if (ans < count) // 移動できたなら移動回数の最大値を保存 ans = count; grid[r, c] = 0; int[] dy = { 0, 0, 1, -1}; int[] dx = { 1, -1, 0, 0 }; for (int i = 0; i < 4; i++) { int nr = r + dy[i]; int nc = c + dx[i]; if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; Dfs(nr, nc, count + 1); } grid[r, c] = 1; // 現在調査中の経路以外から訪問できるように訪問可能にする } } } |
単純パスの個数
問題の趣旨は、
N 頂点 M 辺の単純無向グラフが与えられる。1 を始点とする単純パスの個数を出力せよ。ただし1,000,000を超える場合は1,000,000を出力して処理を終了せよというものです。
これも再帰呼び出しで深さ優先探索をしています。引数は移動先の頂点の番号です。移動に成功した回数を数えることで単純パスの個数を取得することができます。前問とちがって移動成功回数を数えるだけなので引数が少なくなっています。ans をインクリメントしていき、1,000,000を超えたら処理を終了しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
using System; using System.Collections.Generic; using System.Linq; class Program { static int[] ReadIntArray() => Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); static (int, int) ReadInt2() { int[] vs = ReadIntArray(); return (vs[0], vs[1]); } static void Main() { (int N, int M) = ReadInt2(); List<int>[] edges = new List<int>[N]; for (int i = 0; i < N; i++) edges[i] = new List<int>(); for (int i = 0; i < M; i++) { (int a, int b) = ReadInt2(); a--; b--; edges[a].Add(b); edges[b].Add(a); } bool[] seen = new bool[N]; int ans = 0; Dfs(0); if (ans < 100 * 10000) Console.WriteLine(ans); else Console.WriteLine(100 * 10000); void Dfs(int cur) { if (seen[cur]) return; ans++; if (ans > 100 * 10000) return; seen[cur] = true; foreach (int next in edges[cur]) Dfs(next); seen[cur] = false; } } } |
根付き木の部分木に対する操作
深さ優先探索は木構造を扱った問題に使えることが多いです。
問題の趣旨は、
N 個の頂点を持つ根付き木が与えられる。各頂点には初期状態の値が 0 のカウンターが設置されていて、頂点 p[i] を根とする部分木に含まれるすべての頂点のカウンターの値に x[i] を足す処理を繰り返す。すべての操作のあとの各頂点のカウンターの値を求めよというものです。
部分木に含まれるすべての頂点のカウンターに値を追加する処理をどうするかですが、深さ優先探索で追加される値を保持しながらすべての頂点を移動しカウンターの値を更新していけば解を得ることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
using System; using System.Collections.Generic; using System.Linq; class Program { static int ReadInt() => int.Parse(Console.ReadLine()); static int[] ReadIntArray() => Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); static (int, int) ReadInt2() { int[] vs = ReadIntArray(); return (vs[0], vs[1]); } static void Main() { (int N, int Q) = ReadInt2(); List<int>[] edges = new List<int>[N]; for (int i = 0; i < N; i++) edges[i] = new List<int>(); for (int i = 0; i < N - 1; i++) { (int a, int b) = ReadInt2(); a--; b--; edges[a].Add(b); edges[b].Add(a); } int[] A = new int[N]; int[] B = new int[N]; for (int i = 0; i < Q; i++) { (int p, int x) = ReadInt2(); p--; A[p] += x; } bool[] seen = new bool[N]; Dfs(0, 0); Console.WriteLine(string.Join(" ", B)); void Dfs(int cur, int sum) { if (seen[cur]) return; sum += A[cur]; // cur を根とする部分木に含まれるすべての頂点に追加する値 B[cur] = sum; // sum が各頂点のカウンターの値となる seen[cur] = true; foreach (int next in edges[cur]) Dfs(next, sum); seen[cur] = false; } } } |
組み合わせ全探索
問題の趣旨は、
N 個の袋があり、それぞれの袋から 1 つずつボールを取り出す。ボールに書かれた数の総積が X になるような取り出し方は何通りあるか求めよというものです。
N 個の集合からそれぞれ1個ずつ整数を取り出す組み合わせを全探索して総積が X になる個数を数えるだけです。組み合わせ全探索も再帰呼び出しをすればできます。
注意点として、総積を計算するときにそのまま掛け算してしまうとオーバーフローするかもしれないことが挙げられます。そこで積を求めるときに double 型にキャストして乗算し X との大小関係を調べ明らかに大きな値になっている場合はオーバーフローしていると判断しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
using System; using System.Collections.Generic; using System.Linq; class Program { static long[] ReadLongArray() => Console.ReadLine().Split().Select(_ => long.Parse(_)).ToArray(); static (long, long) ReadLong2() { long[] vs = ReadLongArray(); return (vs[0], vs[1]); } static void Main() { (long N, long X) = ReadLong2(); long[][] A = new long[N][]; for (int i = 0; i < N; i++) A[i] = ReadLongArray().Skip(1).ToArray(); int ans = 0; Dfs(0, 1); Console.WriteLine(ans); void Dfs(int cur, long sum) { if (cur < N) { foreach (long a in A[cur]) { // Dfs(cur + 1, sum * a); オーバーフローするかもしれないので // 自作関数で対応する long c = Multiply(sum, a); if(c != -1 && c <= X) Dfs(cur + 1, c); } } else { if (X == sum) ans++; } } long Multiply(long a, long b) { double d = (double)a * b; if (d > X + 100) return -1; // double 型で計算して X よりも100大きければ乗算結果は明らかに不適 return a * b; } } } |
