TOP

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

公開日： 2018/05/17 : 最終更新日：2018/05/17 機械学習 Aアルゴリズム, ダイクストラ法, 最良優先探索

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

つまり、

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

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

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

つまり、

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

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

Contents

ダイクストラ法

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

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

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

openリスト

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

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

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

などが挙げられます。

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

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

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

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

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

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

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

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

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

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

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

が挙げられます。

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

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 アルゴリズムは、上記の２つの手法でそれぞれ用いられていたコスト関数とヒューリスティック関数（コストの予測値）の両方を使用する探索法のことです。

スタートから節点までの（現時点の）最小コストと節点からゴールまでのコストの予測値ｈ’（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　コスト：９

A＊アルゴリズム

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

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