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

関連記事

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

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

記事を読む

【深層学習】 TensorFlow と Keras をインストールする【Python】

今回は、Google Colaboratory 上で、深層学習(DeepLearning)フレームワ

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

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

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

記事を読む

Message

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

【MT4】日付と時間を指定してPCを自動起動させる方法【DELL】

今回は、日付と時間を指定してPCを自動的に起動させる方法について紹介し

【MT4】PCが再起動しても自動的に起動させる方法【FX自動売買】

今回は、FX 自動売買用のツールの MT4 で、実行しているPCが再起

【MT4】複数口座を同時に起動させる方法【FX・CFD】

今回は、MT4(メタトレーダー4)で複数口座を同時にログインし、起動さ

【MQL4】スプレッドを取得する方法【MT4】

今回は、MQL4 で対象通貨ペアのスプレッドを取得する方法について紹介

【楽天CFD】取引口座を開設してみた【MT4】

今回は、楽天CFDの取引口座(本番口座)の開設方法について紹介します。

→もっと見る

PAGE TOP ↑