KATOエンジニヤリング開発日誌

「アウトプット無きエンジニアにインプットもチャンスも無い」の精神で書いています

「なっとくアルゴリズム」を読んだ - 幅優先探索 -

前回に続いて「なっとくアルゴリズム」を読んで理解したことのまとめです。

www.kato-eng.info

www.kato-eng.info

www.kato-eng.info

グラフ

グラフは一連のつながりをモデル化したもので、「AlexはRamaに借りがある」をグラフで表現すると次のようになる。

f:id:masayuki_kato:20171002104117j:plain

グラフはそれぞれノード(node)と辺(edge)で構成されている。ノードは他の複数のノードに接続できる。そうしたノードは隣接(neighbor)と呼ばれる。上記のグラフではRamaはAlexの隣接ノードとなる。

グラフは様々なものが相互に結びつく様子をモデル化することができる。

幅優先探索

幅優先探索は下記2種類の問題を解決するのに役立つ。

  • ノードAからノードBへの経路はあるか
  • ノードAからノードBへの最短経路は何か

ノードAからノードBへの経路はあるか

自分がマンゴー農園所有者で、マンゴーを販売してくれる販売者をFacebookから探す場合、まず友人にマンゴー販売者がいるかを調べるところから始まる。

f:id:masayuki_kato:20171002115605j:plain

この際の検索は単純で、まず検索する友人のリストを作成する。

  • 友人リスト
    • Alice
    • Bob
    • Claire

次にリストの友人を1人ずつチェックし、その友人がマンゴーを販売しているかどうかを調べる。

Aliceはマンゴーを販売しているか?
- Yes: 終了
- No: 次の友人へ

Bobはマンゴーを販売しているか?
- Yes: 終了
- No: 次の友人へ

Claireはマンゴーを販売しているか?
- Yes: 終了
- No: 次の友人へ

リストが空だった場合 -> マンゴーを販売している友人はいない。

友人の中にマンゴー販売者がいない場合には友人の友人を調べていく。下記のようなグラフの場合の幅優先探索は次のようになる。

f:id:masayuki_kato:20171002120356j:plain

  • 友人リスト
    • Alice
    • Bob
    • Claire
Aliceはマンゴーを販売しているか?
- Yes: 終了
- No: Aliceの友人をリストの末尾に加え、次の友人へ

友人リストは下記のようになる。

  • 友人リスト
    • Alice
    • Bob
    • Claire
    • Daniel
Bobはマンゴーを販売しているか?
- Yes: 終了
- No: Bobの友人をリストの末尾に加え、次の友人へ

この手順を繰り返してマンゴーの販売者が見つかるか、友人リストが空になるまで続ける。

この友人リストではAlice、Bob、Claireは1次つながりで、友人の友人は2次つながりといえる。2次つながりより1次つながりの方が望ましいので、1次つながりの友人の中にマンゴー販売者がいないことを確認するまでは2次つながりを調べるのは早計であるといえる。幅優先探索ではこれをすでに行っている。

但し、このグラフはAliceとBobの共通の友人であるDanielが2回リストに載ってしまい、無駄な作業が発生してしまう。実際には、一度チェックした友人は再びチェックしないようにする必要がある。

リストに追加された順に人を検索しなければいけない時に役立つデータ構造が後述するキュー(queue)である。

ノードAからノードBへの最短経路は何か

ツインピークスからゴールデンゲートブリッジに行きたいとき、最もステップ数の少ない経路を見つけるアルゴリズムはどのようなものかを記述していく。

f:id:masayuki_kato:20171002110744j:plain

最初のステップで到達できるのは、ノード1とノード2です。

f:id:masayuki_kato:20171002111324j:plain

最初のステップでは目的地であるゴールデンゲートブリッジに到達できていない。次のステップ2はどうなるか。

f:id:masayuki_kato:20171002111507j:plain

ノード3、ノード4、ノード5の3つに到達したが、ゴールのゴールデンゲートブリッジにはまだ到達できていない。次のステップ3はどうなるか。

f:id:masayuki_kato:20171002111845j:plain

ゴールデンゲートブリッジに到達できた。このグラフではツインピークスからゴールデンゲートブリッジまでは、ノード1 -> ノード4 -> ゴールデンゲートブリッジの最短3ステップで到達できることがわかる。この種の問題は最短経路問題(shortest-path problem)と呼ばれる。

キュー

キューの仕組みはバス停の列に並ぶことに似ている。バス停に並ぶときは後ろの方から並び、バスに乗るときは先頭から乗り始める。

キューの要素にランダムアクセスすることはできない。キューにはエンキュー(enqueue)とデキュー(dequeue)という2つの演算があるだけである。

f:id:masayuki_kato:20171002123209j:plain

まとめ

  • 幅優先探索はAからBへの経路が存在するかを調べることができる
  • 経路が存在する場合は幅優先探索は最短経路を見つけ出すことができる
  • 探索リストに追加された順に人を調べる必要があるため、探索リストはキューである必要がある
  • 一度調べた人を再び調べない仕組みが必要