13. 深さ優先探索と幅優先探索¶

グラフ探索の基本である深さ優先探索 (DFS) と幅優先探索 (BFS) を学んでいきましょう。いよいよ、2年生で学ぶアルゴリズムのクライマックスとなります。

13.1. 木構造とグラフ¶

まず、基本データ構造の木構造とグラフ構造の用語を抑えておきましょう。

13.1.1. 木構造(Tree)¶

木構造は、ノード(node, 節点、頂点)とノード間を結ぶエッジ(edge, 枝、辺)で表すデータ構造です。ルート(root,根)と呼ばれる頂点があるのが特徴です。

重要なバリエーション

二分木 (binary tree) : 各ノードが子ノードを最大2つしかもたない木
平衡木 (balance tree): すべての葉について、深さがほぼ等しい木

木構造は、コンピュータ技術では非常に多く利用されます。

応用例

階層構造のあるデータ構造(ディレクトリツリー、ドメイン名)
プログラミング言語(制御構造、構文木)
データベースアクセスの高速化(インデックス(B-Tree)、トライ木)

13.1.2. グラフ構造¶

グラフ (graph) は、木構造をより一般化したもので、ノード(頂点)群とノード間の連結関係を表すエッジ(枝)群で構成されるデータ型です。

重要なバリエーション

有向/無向 (directed or not) : エッジが方向をもつか持たないか?
巡回/非巡回 (cyclic or acyclic) : 巡回するかしないか?

グラフも、コンピュータ技術では広く利用されます。

応用例

ネットワーク状のデータ構造(Web など)
モデル(コミュニケーション、SNS、経路)

13.2. グラフ探索問題¶

グラフ探索問題とは、あるノード(木の場合は主にルート)からノードを巡回し、ゴールとなるノードを探す問題です。

ノードを巡回する順番によって、次の2つのアルゴリズムに分類されます。

13.2.1. 深さ優先探索 (depth-first search)¶

現在のノードを調査し、子ノードのひとつを選んで調査を進めていきます。見つからなかったら、未調査の子ノードのあるノードに戻って調査を行います。

バックトラック(backtracking)

深さ優先探索などで、前の状態に戻って探索を再開すること

13.2.2. 幅優先探索(breadth-first search)¶

深さが同じノードを浅い方から順に走査していきます。

必修

深さ優先探索と幅優先探索の概念的な違いだけは、必ず区別できるようにしよう

13.3. 探索の例: 油分け算¶

江戸時代の算術書『塵劫記』には、「油分け算」という興味深い問題が掲載されています。

現代風にアレンジすると、次のような例題にあんります。

例題（油分け算）

10L の容器いっぱいに油が入っている。7L の容器 A と 3L の容器 B を使って、この油を 5L ずつに分けたい。どのような分け方があるか?

油分け算は、実はグラフの探索問題として解くことができます。まずは、紙とえんぴつを用意して解いてみましょう。

f46d58e9a4fe4ea9992fd37c31aa3d8e

13.3.1. 考え方¶

容器 A, B にそれぞれ \(a\) L, \(b\) L 入っている状態を (a, b) のペアで表現することにします。最初の状態は、(0,0) とします。ここから、(5, 0)の状態になるまで、操作を繰り返してゆきます。

ステップ	状態	説明
1	(0,0)	初期状態
2	(7,0)	容器 A に油を移す
3	(4,3)	容器 A の油をこぼさないように容器 B に移す
4	(4,0)	容器 B の油を全て 10L の容器に移す

このような操作を図に書くと、次のようなグラフになります。

Let’s try

(5, 0) の状態になるまで油の移動を書き出してみよう！

13.3.2. アルゴリズム化¶

油分け算は、(a, b)のとき、以下のいずれかの操作によって、(a', b')の状態に、油を移すことができます。

可能な油分けの操作: (a, b) → (a′, b′)

容器 A を満杯にする: (a, b) -> (7, b)
容器 B を満杯にする: (a, b) -> (a, 3)
容器 A の油をこぼれないように B に移す: (a, b) -> (a-min(a,3-b), b+min(a,3-b))
容器 B の油をこぼれないように A に移す: (a, b) -> (a+min(7-a,b), b-min(7-a,b))
容器 A の油をもどす: (a, b) -> (0, b)
容器 B の油をもどす: (a, b) -> (a, 0)

したがって、上記のいずれかの操作を選んで、(0, 0) から (5, 0) への操作手順を示せればよいわけです。

ただし、可能な操作は、最大６候補あります。それらを順番に探索するために、どの候補を探索すべきか状態を管理する必要があります。このとき、状態変化を管理するデータ構造によって、探索アルゴリズムが変わります。

深さ優先探索(DFS)：前の状態をスタックに追加して探索する
幅優先探索(BFS)：次に調べる状態をキュー（待ち行列）に入れて探索する

13.3.3. 深さ優先探索によるプログラム例¶

深さ優先探索は、スタックを使って (a, b) の状態遷移を管理します。

新しい状態を調べる: スタックに (a, b) を push する
前の状態に戻る(バックトラック): スタックから pop する

深さ優先探索は、スタックの代わりに再帰関数とコールスタックを使って、スタック構造を使わなくても書くことができます。だから、深さ優先探索は、幅優先探索より簡単に実装できます。

コールスタックの原理

関数呼び出し(関数コール)は、引数の値をスタックにpushすることで実現しています。逆に、関数をリターンすることは、引数を pop することに相当します。

関数 dfs(a,b)¶

dfs(a,b)を(a,b)の状態を探索する深さ優先探索アルゴリズムの実装とします。すると、(a,b)->(a',b')の状態遷移を探索することは、dfs(a’,b’)を再帰的に呼び出すことになります。

[1]:

def dfs(a, b):
    if a == 5 and b == 0:
        return True # 発見 !!
    # 次の状態を探す
    # 容器 A を満杯にする `(a, b) -> (7, b)`
    if dfs(7, b):
        return True
    # 容器 B を満杯にする `(a, b) -> (a, 3)`
    # 容器 A の油をこぼれないように B に移す `(a, b) -> (a-min(a,3-b), b+min(a,3-b))`
    # 容器 B の油をこぼれないように A に移す `(a, b) -> (a+min(7-a,b), b-min(7-a,b))`
    # 容器 A の油をもどす `(a, b) -> (0, b)`
    # 容器 B の油をもどす `(a, b) -> (a, 0)`

    return False # (a, b) からは(5,0)に到達できず

気を付けなればならない点は、油分けの操作によっては何度も同じ状態に遷移することです。だから、木構造の探索ではなく、グラフ構造の探索問題となります。

同じ状態を繰り返し調べないようにするため、辞書 visitedを使って、一度、探索した状態を記録して、繰り返さないようにします。

[2]:

visited = {} #調べた状態を記録する

def dfs(a, b):
    if a == 5 and b == 0:
        return True # 発見 !!
    if (a,b) in visited: #一度訪れていたら
        return False
    visited[(a,b)] = True # 訪れた状態を記録する
    # 次の状態を探す
    # 容器 A を満杯にする `(a, b) -> (7, b)`
    if dfs(7, b):
        return True

    # 容器 B を満杯にする `(a, b) -> (a, 3)`
    # 容器 A の油をこぼれないように B に移す `(a, b) -> (a-min(a,3-b), b+min(a,3-b))`
    # 容器 B の油をこぼれないように A に移す `(a, b) -> (a+min(7-a,b), b-min(7-a,b))`
    # 容器 A の油をもどす `(a, b) -> (0, b)`
    # 容器 B の油をもどす `(a, b) -> (a, 0)`

    return False # (a, b) からは(5,0)に到達できず

Let’s Try

dfs(a,b)を完成させてみよう

13.3.4. 探索経路の表示¶

関数 dfs(a,b) は、(a, b) の状態から開始して、(5, 0) に到達したら True を返します。しかし、このままでは、どういう操作によって (5, 0) に至ったのかわかりません。

Let’s Try

探索経路を表示できるようにしてみよう

ヒント : 正解を発見したときから，関数を戻るごとに表示すれば、(逆順になるが)順番が示されます。

if dfs(X, Y):
    print(f'({a},{b}) => ({X},{Y})')
    return True

答えを見る前に自分で考えてみよう。

04bd342fbe7e49329629421710779e7e

[3]:

Visited = {}

def dfs(a, b): # (a, b)の状態を探します
  if a == 5 and b == 0:
    return True # ゴールをみつけたら

  if (a, b) in Visited: # 探索済なら探さない
    return False
  Visited[(a, b)] = '探索済'

  #1. A に油を入れる
  if dfs(7, b):
    print((a, b), '=>', (7, b))
    return True

  #2. B に油を入れる
  if dfs(a, 3):
    print((a, b), '=>', (a, 3))
    return True

  # 3. Aから Bにこぼさずうつす
  ab = a if (3 - b ) > a else 3- b
  if dfs(a-ab, b+ab):
    print((a, b), '=>', (a-ab, b+ab))
    return True

  # 4 BからAにうつす
  ba = b if (7 - a ) > b else 7- a
  if dfs(a+ba , b-ba):
    print((a, b), '=>', (a+ba, b-ba))
    return True

  #5. A を空にする
  if dfs(0, b):
    print((a, b), '=>', (0, b))
    return True

  #6. B を空にする
  if dfs(a, 0):
    print((a, b), '=>', (a, 0))
    return True

  return False # 見つからなかったら


dfs(0, 0) # (0,0)から探索します。

(2, 3) => (5, 0)
(2, 0) => (2, 3)
(0, 2) => (2, 0)
(7, 2) => (0, 2)
(6, 3) => (7, 2)
(6, 0) => (6, 3)
(3, 3) => (6, 0)
(3, 0) => (3, 3)
(0, 3) => (3, 0)
(7, 3) => (0, 3)
(7, 0) => (7, 3)
(0, 0) => (7, 0)

[3]:

True

13.3.5. 最短経路¶

深さ優先探索は、名前が示すとおり、ひとつ候補を選んでどんどん深く探索していきます。つまり，手順数は多くてもお構いなしです。したがって、もっと短い手順で探索できる可能性があります。

深さ優先探索の限界

最短手順は保証されない

最短経路を探すためには、次のような方法があります。

幅優先探索 (breadth first search): 同じ深さのノードから探索するため，最短手順が必ず見つかる。スタックの代わりにキューを使って容器の状態を管理する。
反復深化深さ優先探索 ( iterative deepening depth-first search): 深さ優先探索の深さに制限を付け，徐々に制限を緩和することで浅い解を先に見つける

プログラミングの練習としては、是非、状態遷移をキューで管理するように変更し、幅優先探索で最短経路を探してもらいたいところです。

深さ優先探索が簡単な理由は，スタックを使わずに、再帰関数で実装できる点です。幅優先探索は，スタックの代わりにキューを使うことになりますが、実装はかなり手間が増えます。一方，反復深化は dfs(a,b) 関数に、dfs(a,b,depth)のように深さ制限をつけるだけなので、少しの改良で実装できます。

13.4. 演習問題¶

今回は、前期アルゴリズムの最終回なのでレポート問題も出題します。

13.4.1. エイトクイーン¶

「深さ優先探索」や「幅優先探索」はパズルを解くときに利用されます。代表的なパズル問題を解いて練習しましょう。

**レポート問題**エイトクイーン

問題チェスのクイーンは，上下左右斜めの 8 方向，将棋の飛車と角行を合わせた動きをする。 8 個のクイーンをチェス盤 (8 × 8) 上においたとき，どのクイーンも他のクイーンから取られないように配置する方法をすべて表示せよ。

一例

□□□👸□□□□
□□□□□□👸□
□□👸□□□□□
□□□□□□□👸
□👸□□□□□□
□□□□👸□□□
👸□□□□□□□
□□□□□👸□□

考え方

（2次元配列などで）チェス面をデータ表現する
(上の列から順番に) クイーン (👸) を置く
置いたクイーン (👸) の移動できる場所を置けなくし、次の列に進む
次の列で置けなかったら、バックトラック (backtrack) して前の列に戻り、別の場所を試す

36267ec9b4a448b88cff840481e74da1

Let’s try

エイトクイーンは、プログラミング力を鍛える程よい練習問題として、情報系の学生が一度は挑戦する課題です。

Webには、エイトクイーンの解説が溢れていますが、まずは自分の力で考えてプログラミングしてみましょう。

チェス盤をデータ表現できる
クイーン(👸)をお互い取り合わないようにおける
再帰関数で探索プログラムが書ける
バックトラック処理が正しく書ける
全ての配置を表示できる

レポートは、自分で理解してプログラムできたところまで報告していただければいいです。逆に、正解に至るプログラムの場合は、コピペを判定するのが難しいです。最後までかけたら、プログラムを教員に見せてください。

13.4.2. 課題リスト¶

グラフや探索を活用する問題を集めてみました。

課題リストより

Python Programming 2021 ドキュメント