[algorithm]グラフ理論と幅優先探索&深さ優先探索の入門の入門(夏休み企画4)

学校の授業でもアルバイトでもWeb系の開発ばかりしていたので、
数学・物理、そしてアルゴリズムなどとは(少なくとも僕が意識する範囲では)
無縁だったのですが、去年末に、サポーターズさんに
招待していただいた就活イベントで、お話させていただいた企業の方から

『WEBプログラマーはアルゴリズムに弱い』

というお話をお聴きしました。確かに必要に駆られる場合は、僕の場合、ありませんでした。

それでも、できないよりは、簡単なものから初めてみようと思い、TopCoderやAOJに登録して
みました。しかし、すぐにアルゴリズムをちゃんと勉強して、知識として持っていなくては
八方塞がりになることが、頻繁にあったので、空き時間に少しづつ本を読んだりしていました。

今回は、その中で、頻繁に出てくるテクニックとして、深さ優先探索と幅優先検索について
グラフ理論の基礎から復習を兼ねて、まとめてみたいと思います。
(※可能であればc++とpythonで実践もしたいと思います。)

概要はwikipediaやグーグル検索すれば、大体わかると思います。
僕も最近知ったもので、グーグル検索ですぐに手に入る程度の知識しかありません。

グラフ理論とは

数学の1分野で、ノード(頂点、node)とエッジ(枝、edge)の集合で構成されるグラフの性質について
研究する学問である。

コンピュータのデータ構造やアルゴリズムに広く応用されている。
(※ リスト構造、wwwのハイパーリンク、デッドロックの検出、ファイルシステム、ガベージコレクションなど)

下図はグラフ理論における、グラフの例です。矢印があるほうが有向グラフ
ないものが無向グラフです。

今回、僕が書きたいのが、このようなグラフから任意の条件にマッチするグラフを検索する
幅優先検索深さ優先探索です。

専門用語等、不明なワードがあれば、 wikipediaを参照してみてください。

経路探索などにも用いられることが多いので、
ゲームを作ったりする方は馴染みがあるかもしれません。

●幅優先探索とは

英語でBreadth first search。グラフ理論において、グラフや木構造(ツリー構造)の探索に用いられる。
アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。
それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。

アルゴリズムの観点からだと、ノードの展開により得られる子はキューに追加される。
典型的な実装の場合、未訪のノードは”open”と名づけられた(キューや連結リストのような)
コンテナに格納され、既訪のノードは”closed”と名づけられたコンテナに格納されることになる。

アルゴリズムの実装手順

  1. 根ノードを空のキューに加える。
  2. ノードをキューの先頭から取り出し、以下の処理を行う。
    • ノードが探索対象であれば、探索をやめ結果を返す。
    • そうでない場合、ノードの子で未探索のものを全てキューに追加する。
  3. もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ”not found”と結果を返す。
  4. 2に戻る。

※実際にプログラミング言語による実装は、後ほど・・・。

●深さ優先探索とは

英語でdepth first search(DFSと略されることも多い)。別名バックトラック法。
こちらもグラフやツリー構造の探索に用いられるアルゴリズム。

アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、
バックトラックするまで可能な限り探索を行う。

深さ優先探索の概要

形式的には、深さ優先探索は、探索対象となる木の最初のノードから、
目的のノードが見つかるか子のないノードに行き着くまで、深く伸びていく探索である。
その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。
非再帰的な実装では、新しく見つかったノードはスタックに追加される。

深さ優先探索の実装には、スタックを用いたものと、再帰を用いたものが代表的です。
検索するノードの順番が一筆書きできる、という特徴があります。

スタックで実装手順

  1. スタックを用意する
  2. スタックに最初の要素を入れる(push)
  3. スタックから要素を取り出す(pop)
  4. 要素に対して処理をする
  5. 要素の子供をスタックに入れる(push)
  6. スタックがカラになるまで3~5を繰り返す

引用元

※実際にプログラミング言語による実装は、後ほど・・・。

●深さ優先探索と幅優先探索のどちらを利用するべきか

深さ優先探索を用いるべきケース

  • 前通りのパターンを列挙し、結果をまとめる必要がある場合
  • 文字列などを探索するときに、辞書順であることが求められる場合

幅優先探索を用いるべきケース

  • 始点から最も近いおのを求めたいケース
  • 探索範囲は広いが、ある程度近くに求めたい解が存在することがわかっているケース
  • 探索範囲が広く、深さ優先探索ではスタックが大量に使われてしまうケース

上記内容はこちらの書籍を引用しました。実装例なども含まれています。redcoderの方が書いた
TopCoderの入門書です。

最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド

プログラミングによる実装

c++とpython、どちらで実装するか悩みましたが、まずは高レベルのmoduleが
充実していそうなpythonから挑戦してみました。

3*3マスのフィールドを、

  1. 深さ優先探索で同じ道を通らずにゴールまで進むパターンは何通りあるかを調べる
  2. 幅優先探索で最短経路は何歩であるか調べる(1歩1マスとして)

という問題を幅優先探索と深さ優先探索を用いて求めてみます。

3*3マスのフィールドは文字列型の配列で

と表現するとします。障害物のない状態なら、3*3という整数があれば表現できますが、
汎用的にするために、ここではこうしておきます。

startする地点は(0,0)の左上、ゴールは(4,4)つまり右下
とします。

動けるのは上下、左右で、斜めはなし。

pythonによるBFSとDFSの実装

幅優先探索のほうは、本で見たサンプルまんま・・・って感じですが・・・。
もうちょっと柔軟に、様々な問題をグラフ化して、どちらの検索方法でも
さらっと実装したかったです・・・。

問題解決を重ねるしかないですね・・・。

ちなみにc++でもQueueも再帰共に、上記の例であればpythonと同様に利用できるので
同じような流れで実装可能です。

推奨されるかは別として、グローバル変数を利用すれば、更にシンプルに
書くこともできます。

これは数こなすしかないな・・・というのが、とりあえず実装して一番感じたことです。

そしてもうひとつ感じたことは、問題をグラフ化する、ということが、まず問題解決の
第一関門、実装はその次、ということです。

この記事の目的としては、このコードに関して
検索している順番には着目してほしいですが、決して良いコードではありません。

●余談ですが

検索と探索の違い

検索とは、資料や文献の中から目的の情報を探し出すこと。
検索と探索の違いは、検索は目的の情報を探し出す基準が決まっているのに対して、
探索は有効な基準(解析的な解法)がない、あるいは用いないときに、
実際に試行錯誤することによって解を探す方法を取る事。

だそうです。引用元

numpy,scipy,matplotlibを導入しました。

グラフ理論をプログラミングの観点から勉強したくて、この記事を書いてる途中
pythonの上記moduleを導入してみました。

以前参加したプログラミングで数学を楽しむ会(2)の内容
を少しづつ思い出してきました。参加した当時は、ちんぷんかんぷんでしたが、重要性と汎用性を
少しだけ理解することができたかもしれません。

上記モジュールを利用したサンプルなど、機会があればブログ書きたいと思います。

参考・引用リンク

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です