【探索】ダイクストラ法・最良優先探索・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*アルゴリズム」と呼びます。

関連記事

【PyTorch】GPUのメモリ不足でエラーになったときの対処方法。

PyTorch で深層学習していて、 GPUのメモリ不足でエラーが出てしまったので、対処方法のメモで

記事を読む

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

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

記事を読む

【PyTorch】畳込みニューラルネットワークを構築する方法【CNN】

今回は、PyTorch を使って畳込みニューラルネットワーク(CNN)を構築する方法について紹介しま

記事を読む

【Weka】CSVファイルを読み込んで決定木を実行。

フリーの機械学習ソフト Weka を使って、CSVファイルを読み込んで決定木(Decision Tr

記事を読む

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

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

記事を読む

【TensorFlow】GPUを認識しない時の対処方法【Python】

TensorFlow で GPU を認識させようとしたときにハマってしまったので、その対処方法のメモ

記事を読む

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

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

記事を読む

【PyTorch】ニューラルネットワークを構築する方法【NN】

今回は、PyTorch を使って、ニューラルネットワーク(NN)を構築したときのメモです。 フ

記事を読む

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

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

記事を読む

【Weka】ARFF 形式から CSV 形式に簡単に変換する方法。

フリーのデータマイニングツールである WEKA では、ARFF 形式と CSV 形式のデータを読み込

記事を読む

Message

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

【Cubase】特定のトラックを無効にする方法。

今回は、Cubaseで特定のトラックのみを無効にする方法について紹介し

【転移学習】学習済みVGG16 による転移学習を行う方法【PyTorch】

今回は、PyTorch を使って、学習済みのモデル VGG16 を用い

【PyTorch】畳込みニューラルネットワークを構築する方法【CNN】

今回は、PyTorch を使って畳込みニューラルネットワーク(CNN)

【PyTorch】ニューラルネットワークを構築する方法【NN】

今回は、PyTorch を使って、ニューラルネットワーク(NN)を構築

【OpenCV】検出した顔画像部分を切り出す方法【Python】

OpenCV を使って、Python で画像の中から顔部分を切り出した

→もっと見る

PAGE TOP ↑