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

関連記事

【機械学習】 scikit-learn で精度・再現率・F値を算出する方法【Python】

今回は、2クラス分類で Python の scikit-learn を使った評価指標である、精度(P

記事を読む

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

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

記事を読む

【機械学習・手法比較】決定木とナイーブベイズを比較してみた。

同じデータを使って、教師有り機械学習手法の 決定木(Decision Tree)とナイーブベイズ(N

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

Message

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

初心者でも分かるビットコインの仕組みについてまとめてみた。

ビットコインは,時価総額が1位で最も有名な仮想通貨です. 仮

【LaTeX】 見出し付き箇条書きを右にずらす方法【数式の変数説明】

今回は、LaTeX で見出し付き箇条書きの全体の位置を右にずらす方法に

【LaTeX】 余白部分を設定しレイアウトを確認する方法。

今回は、LaTeX の余白部分のレイアウトの変更方法とレイアウトの確認

【LaTeX】 レポートや論文の表紙のテンプレート。

LaTex を使ってレポートや論文を書くときに、表紙をつけると思います

【DTM】 Cubase AI でギターやベースを録音する方法。

今回は、DTM のための DAWソフト Cubase AI でギター(

→もっと見る

PAGE TOP ↑