a*アルゴリズム

最小の総コストを求める探索アルゴリズム。

8パズル

3x3のグリッド（9つのマス）の形。
各タイルには1から8までの数字が書かれている。
誰かに初期状態と目標状態を入力してもらって、初期状態からタイルを動かして目標状態と同じく作ることが目的だ。
こんな感じ。

8パズルをa*アルゴリズムで解く前に話したいこと。

解く前に決めておくべきだと思うのは以下二つの定義だ。
①評価関数
②演算子

①評価関数の定義

コストを評価する関数。以下のように定義する。
f^(n)=g(n)+h^(n)

g(n):出発ノード（ここでは8パズル）から現在ノードまで到達するために消費した実際の経路コスト。
h(n):現在ノードから目標ノードまで到達するために消費する推定経路コスト。
h^(n):h(n)は正確に分からないため推測した推定値を示すヒューリスティック関数。

②演算子の定義

状態遷移を実現するための具体的なルール。

8パズルの例

誰かに以下のようなリクエストをもらった。
初期状態（これを）

目標状態（これと同じくしてください）

説明

①評価関数の定義

f^(n)=g(n)+h^(n)

g(n):空白の移動回数。
h(n):目標状態のパズルと比較した時、指定した位置に存在しないタイルの数。

②演算子の定義

U: 空白を上に移動させる。
D: 空白を下に移動させる。
R: 空白を右に移動させる。
L: 空白を左に移動させる。
（ここでなんで空白を移動させるのかわからない方へ。
　→　タイルを移動させることと空白を移動させることは観点の違いで、
「空白を上に移動させる」はつまりパズルを下に移動させることと同じであるため。）

解き方

理解のために用意したら良いことがある。
OPENリストとCLOSEリストだ。
OPENリスト：これから展開するノードを格納するリストのこと。
CLOSEリスト：すでに展開したノードを格納するリスト。

①最初に、出発ノードをopenリストに挿入する。この際、出発ノードの評価関数も計算して一緒に添付する。
②このリストの中で評価関数が最も良い（主に最小）ノードNを選び、それをcloseリストに追加する。
③−①ノードNが目標ノードであれば、探索は成功なのだ。
③−②ノードNが目標ノードでない場合は、ノードNを展開して、展開したノードの評価関数も計算してopenリストに挿入する。この際、展開したノードがopenリストまたはcloseリストに重複している場合は、重複処理を行う。（既存のノードと展開ノードの中で、コストが低い方のノードを削除または更新するなど）

この手順を繰り返し、探索に成功しないままopenリストから取り出すノードがなくなれば、探索は失敗となる。

正解

四角番号は展開順序。
丸のU、D、R、Lは使った演算子。
f^(n)は評価関数=コスト。
青い線が最小のコストの解き方になる。

（　・。。・　）🖐

間違っている内容がありましたら、教えて頂ければ喜びます。