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

関連記事

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

Message

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

【Python】pip3 で「cannot import name ‘main’」エラーが出たときの対処法。

Python でライブラリをインストールする際に、pipを使います。

【mecab-python3】parseToNode で surface が正しく取得できないときの対処法。

python3 で mecab-python3 を使うと、parseT

【Python】形態素解析器 Mecab を Linux(Ubuntu)で使ってみた。

Linux の Ubuntu OS に、形態素解析器 Mecab をイ

【Python】NLTK(自然言語処理ライブラリ)を使ってみた。

Python の自然言語処理ライブラリである NLTK を Linux

【Python】OpenCV を使って顔画像を検出してみた。

OpenCV のインストール Numpy のインストール [c

→もっと見る

PAGE TOP ↑