【探索】ダイクストラ法・最良優先探索・Aアルゴリズムの比較。

公開日: : 最終更新日:2018/05/17 機械学習 , ,

縦型探索や横型探索では、機械的に順序を付け、最小ステップでゴールを目指します。

つまり、

  1. 機械的順序 ⇒ 優先順位をつけない。
  2. 最小ステップ ⇒ どんな枝も同等として扱う。

という前提がありました。

しかし、現実問題だと、候補には有望さがあり、1ステップにもコスト(費用や時間)があります。

つまり、

  1. 有望な候補から調べていきたい ⇒ ヒューリスティック関数を活用した探索。
  2. 重い枝を避け総コスト最小の経路を見つけたい ⇒ コスト関数を考慮した探索。

を行う探索について紹介します。

ダイクストラ法

ダイクストラ法は、枝のコスト関数のみを使う探索法のことで、コスト最小のノードから展開していきます。また、ゴールが見つかり、かつコストが最小になれば終了します。

ちなみに、「ダイクストラ」は数学者の名前です。

実際に以下の探索木をダイクストラ法で解いてみます。

openリスト

[S(0)]->[A(2), B(3)]->[C(A5), B(3)]->[C(B4), D(B7)]->[G(BC6), E(BC7), D(B7)]

ダイクストラ法の特徴としては、

  1. 必ず最適順路(最小コストの経路)を見出すことができ、ループになったりしない。
  2. 枝のコストがすべて同じウェイト(値)のとき、横型(幅優先)探索と一致する(時間がかかりメモリ量も大きい)。
  3. ノードの有望さを使わない(コストが低ければ明らかに無駄な方向も探索する)。

などが挙げられます。

そこで、ヒューリスティック関数が登場します。

ヒューリスティック関数とは、ゴールへの予測コストh’(n)のことで、予測なので解く人が決めるし、正確でない可能性もあります。

ヒューリスティック関数の山登り法

ヒューリスティック関数の山登り法は、一つの節点に着目して、現地点からの候補だけをみて予測コスト最小を選びます。

ただし、以下のような探索木の場合、無限ループに陥ってしまいます。

()内の数値が予測コストなので、山登り法だと、単純に()内の数値が小さい方に進んでいきます。

すると、S ⇒ B ⇒ C ⇒ E ⇒ A と無限ループになってしまいます。

ヒューリスティック関数の最良優先探索

ヒューリスティック関数を用いた最良優先探索は、過去を含む全節点で最良の節点(予測コスト最小)を展開していきます。

ヒューリスティック関数を用いた最良優先探索の特徴は、

  • ヒューリスティック関数h’(n)のみを使用する。
  • 最適順序は保証されない(h’(n)は本来いいかげんなものであるし、コスト関数を見ていないから)。

が挙げられます。

山登り法では無限ループになってしまった探索木を最良優先探索で試してみます。

openリストは、

[S(7)]->[B(5), A(7)]->[C(B4), D(B5), A(7)]->[E(BC1), F(BC2), D(B5), A(7)]->[F(BC2), D(B5), A(7)]->[G(BCF0), D(B5), A(7)]

のようになり、経路は S->B->C->F->G となり、コストは10となります。

A アルゴリズム

A アルゴリズムは、上記の2つの手法でそれぞれ用いられていたコスト関数ヒューリスティック関数(コストの予測値)の両方を使用する探索法のことです。

スタートから節点までの(現時点の)最小コストと節点からゴールまでのコストの予測値h’(n)のを使います。

open リスト

[S(7)]->[B(7), A(10)]->[C(B7), D(B9), A(10)]->[E(BC5), F(BC10), D(B9), A(10)]->[F(BC10), D(B9), A(10)]->[F(BD9), A(10)]->[G(BDF9), A(10)]

経路:S->B->D->F->G コスト:9

A*アルゴリズム

A*アルゴリズムは、Aアルゴリズムの間に「*」アスタリスクが入っています。アスタリスク「*」は最適という意味で用いられます。

Aアルゴリズムは最適解とは限りません。それは、ヒューリスティック関数h’(n)がいいかげんなものだからです。そこで、ヒューリスティック関数h’(n)が、真のコストh(n)と比較して常に、h’(n)<= h(n)を満たすとき(楽観的なとき)、常に最適解が保証されます。そして、このときのAアルゴリズムを「A*アルゴリズム」と呼びます。

関連記事

【Weka】欠損データを自動的に補完するフィルタを使ってみた。

機械学習で用いるデータについてです。データは完璧なことに越したことはないが、通常は、ある属性の値が入

記事を読む

【Weka】フリーの機械学習ソフトをインストールする方法。

Weka は、GUIで使えるフリーの機械学習ソフトです。 https://ja.wikiped

記事を読む

【Weka】アソシエーション・ルール(association rule)【機械学習】

フリーの機械学習ツール Weka でアソシエーション・ルール(association rule)を使

記事を読む

【機械学習】パーセプトロン(Perceptron)について。

パーセプトロンは、教師あり学習の中でも、入出力モデルベース(eager learning:働き者の学

記事を読む

【機械学習】モンテカルロ法(Monte Carlo method)について。

モンテカルロ法(Monte Carlo method)とは、シュミレーションや数値計算を乱数を用いて

記事を読む

【機械学習】 scikit-learn で不正解データを抽出する方法【Python】

Python の scikit-learn ライブラリを使って機械学習でテストデータを識別(2クラス

記事を読む

機械学習の手法のまとめ。

機械学習は、「与えられた入出力事例をモデル化する行為」のことで、ディープラーニングなどで注目を集めて

記事を読む

【探索】縦型・横型・反復深化法の探索手法の比較。

探索とは、チェスや将棋や囲碁などのゲームをコンピュータがプレイするときに、どの手を指すかを決定するの

記事を読む

【画像認識】 Google画像検索結果を取得する方法 【google image download】

今回は、深層学習(DeepLearning)で画像認識をするための画像データの収集を、Google画

記事を読む

【機械学習】決定木(decision tree)について。

教師あり学習の一つである決定木(desicion tree)について勉強したことを書いていきます。

記事を読む

Message

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

【matplotlib】 Python でヒストグラムの横軸と棒(ビン)の数を調整する方法。

Python の matplotlib を使ってヒストグラムを描画し、

【デジカメ】 NEX-6 で撮った写真を Wi-Fi で PC に転送する方法【SONY】

今回は、SONY の NEX-6 のデジカメで撮った写真を 無線の W

【SONY NEX-6】オールドレンズをミラーレスカメラに付ける方法【マウントアダプター】

家でずっと眠っていたオールドレンズ(フィルムカメラに装着されて

【WordPress】 カテゴリごとに広告を簡単に切り替える方法【AdRotate】

今回は、WordPress のプラグインを使って、簡単にカテゴリごとに

【ビットコイン】 アドレス生成方法について調べてみた。

仮想通貨の1つであるビットコインを送金するときは、送付側と受け手側のそ

→もっと見る

PAGE TOP ↑