グラフ探索ことはじめ - 幅・深さ優先探索 -

# Motivation

人工知能っていうとでぃーぷらぁーにんぐみたいな話になってるのがむかつくのでアンチテーゼにでもなればと思い、思いつきではじめました。たぶん一人でやるのであまり深いところまでは書き/書けません。自分の復習/備忘録的なものでもあります。しかもグラフ理論は自学で学んだぐらいの人間が書いてます。(グラフ理論入門 原著第四版 R.HJ. ウィルソン) 基本は AIMA から引っ張ってきています。

# グラフ探索ってなに?

カーナビです。つまり、まず、今居る所「スタート」と、目的地「ゴール」があります。通ることの出来る「道路」があって、その途中に沢山「交差点」があります。あなたは一番短い時間、距離でゴールにたどり着きたいと思っています。グラフ探索問題とは、与えられた地図上で、スタートとゴールがあるときに、ゴールまでの最短の行き方を調べるための問題です。

![Screenshot from 2015-12-04 19:03:48.png](https://qiita-image-store.s3.amazonaws.com/0/6090/16c70d82-b86f-f050-32a4-5893b2d902e9.png)


アルゴリズムや数学の世界では、このような「交差点」のようなものが「道路」という線っぽいもので繋がったものをグラフと言います。「交差点」のことは「頂点」、「道路」のことは「辺」と言います。ええ、正方形は4つの辺と頂点があり、りっぱなグラフです。

カーナビやFacebookの友達検索など、身近なソフトウェアの中には、このグラフ探索問題を解くプログラムが沢山入っています。ただ、それらの扱うグラフはとても広いだけではなく、とても複雑な地形を持っているカーナビ問題だと考えてください。普通の道路地図よりも複雑な例として、例えば「新宿駅の地図」を考えてみましょう。新宿駅は、例え直線距離的に近くても、建物の構造や改札があるせいで遠回りをしないと辿りつけないような場所がたくさんあります。

![Screenshot from 2015-12-04 19:06:02.png](https://qiita-image-store.s3.amazonaws.com/0/6090/67841ce5-486c-1f1b-f05a-099b1b1c1416.png)


グラフ探索アルゴリズムは、新宿駅の $10^{70}$ 倍ぐらい広いような複雑なグラフで動くカーナビを実現するためにあるといって過言ではありません。こういう規模のグラフは非現実的な話ではなくて、身近にあるシンプルなパズル、例えば **ルービックキューブ** 程度でも存在します。そして特に、人工知能における推論問題に頻繁に出現します。このこと故に、グラフ探索、より広く **探索** は、**学習** と並ぶ人工知能の重要なテーマです。

ちなみに、新宿駅が $1km$ 四方ぐらいの敷地だとして、似た構造で $10^{70}$ 倍の頂点を持つグラフは だいたい $10^{35} km= 10^{22}$ 光年四方ぐらいに相当するでしょう。[観測可能な宇宙の直径は465億光年](https://ja.wikipedia.org/wiki/%E8%A6%B3%E6%B8%AC%E5%8F%AF%E8%83%BD%E3%81%AA%E5%AE%87%E5%AE%99) $\approx 4.65\times 10^{10}$ 光年らしいので、これよりもはるかに大きいサイズですね。

# グラフ探索問題の定義

まずグラフというのは、頂点の集合 $V$ と、辺の集合 $E$ からなります。頂点(Vertex/・ices)に対しては $v \in V$ 、あるいは探索ノード $n$ として表記します。辺とは2つの頂点の列 $(v_1,v_2) \in E $ です。組ではなく順列としたことからもわかるように、自分の記事では基本は有向グラフを対象にします。それぞれの辺 $e=(v_1,v_2)$ は重みあるいはコスト $c$ を持ちます。これについて特に言及しない場合、重みが1のユニットコスト問題となります。

グラフ探索の入力は、このグラフ $(V,E)$ と、初期ノード $v_0$ および ゴールノード $v_g$ です。ただ、たいていのアルゴリズムは初期ノード集合、ゴールノード集合にも適用できます。

グラフ探索の出力は、 $v_0$ から $v_g$ に至るための経路、即ち辺の列 $\langle(v_0,v_1),(v_1,v_2)\ldots (v_{k-1},v_g)\rangle$ です。この時、グラフ **最小コスト** 探索の場合は、その辺のコストの合計が、存在する経路のうち最小のものである必要があります。 ユニットコスト探索の場合、コストの和は経路の長さ $k$ と一致するので、**最短経路探索**とも言われます。 どちらでも最短経路探索と言う人もいます。あるいは、 **最適探索** (optimising/optimal search) とも呼ばれます。

# グラフ探索 or 木探索?

どのアルゴリズムの教科書でも、はじめに習うのは木探索です。なぜかというと、グラフにはサイクル(閉路)という問題がつきまとうからです。サイクルとは、あるノードからどこかの辺を通って自分に戻ってくることが出来るような経路のことを言います。

木探索のアルゴリズムをそのままグラフ探索に用いると、大まかに言えば、同じ所をぐるぐるまわってアルゴリズムが終了しない可能性があります。そのためグラフ探索は、一度通った場所を通らないようにするための **重複検知** の手法を含んでいます。が、この重複検知はある程度アルゴリズムを複雑にします。そこで、教育的な観点から(For a pedagogical reason...)、はじめに木探索をやります。

いやまあ本音は、もう夜遅いからですよ。

# 幅優先探索

一番簡単な幅優先探索を紹介します。幅優先探索は木探索で用いられます。

幅優先探索の、まあ唯一の要素は、 **キュー** です。

Algorithm: $BreadthFirstSearch(V,E,v_0,v_g)$:

1. Let $Q$: a FIFO queue.
2. Initialize: $push(v_0,Q)$
3. Until $empty(Q)$
    * Let $v \leftarrow pop(Q)$
    * When $v = v_g$ then return $reverse(unfold(parent, v_g))$
    * Else, for each $v' \in children(v)$ do
        * $push(v',Q)$
* return nil

![breadth-first.png](https://qiita-image-store.s3.amazonaws.com/0/6090/90aed1d1-a3d9-821b-da3b-1b64de0697d8.png)


こんなもんでしょうか。ただし:

* children は ノードから出て行く辺の先に繋がったノードの集合を返します。
* parent は そのノードに入ってくる辺の先に繋がったノードを返します。木探索なので、そういうノードは一本しかありません。

キューに後ろから追加して前から取り出していくので、木の浅い部分から順番に探索していきます。
コストは全く考えていないので、コストありのグラフでは非最適になります。一方、ユニットコストの木では最短経路、つまり最適解を返してくれます。

計算量の議論はなんでしょうね、たぶんユニットコストで最適解が$d$, 最大のbranching factor $b = \max_{v\in V} |children(v)|$ として、$O(b^d)$ぐらいの時間計算量でしょうか。

グラフに使うときは、ノードにマークを付けて、訪問済みの場合は無視します。 ~~同じく、ユニットコストの場合は 最適です。コストありの場合はそうではありません(合計コストの小さい、しかし長い経路が存在するため)。~~ 最適じゃないです。一年もほったらかしてごめんね。素直に次のdijkstra使ってください。

# 深さ優先探索

ついでなので深さ優先探索も書いちゃいます。
幅優先探索との唯一の違いはキューがLIFOキュー、言い方を変えればスタックであることだけです。
このことから、深さ優先探索は再帰で書くことも出来ます。

Algorithm: $DepthFirstSearch(V,E,v_0,v_g)$:

1. Let $Q$: a LIFO queue.
2. Initialize: $push(v_0,Q)$
3. Until $empty(Q)$
    * Let $v \leftarrow pop(Q)$
    * When $v = v_g$ then return $reverse(unfold(parent, v_g))$
    * Else, for each $v' \in children(v)$ do
        * $push(v',Q)$
* return nil

![depth-first.png](https://qiita-image-store.s3.amazonaws.com/0/6090/e69aac1b-b98a-4133-6824-f51113a0bd57.png)


探索したノードの子を次にぐさま探索するので、どんどん深さ方向にネストしていきます。
当然、最適性は担保できません。この点はもう少しあとで書くIDA*(など、IterativeDeepening系のアルゴリズム)に話を譲ることにします。
木の最大の深さが決まっている場合にはいいですが、でかいグラフには使えませんよね。

# 書いてみた感想

やってみるもんだ、30分ぐらいで書けましたね。内容が薄いとも言う。