algorithm
A *パスファインディング
サーチ…
A *
A *（A star）は、あるノードから別のノードへのパスを見つけるために使用される検索アルゴリズムです。したがって、 幅優先検索 、またはダイクストラのアルゴリズム 、または深さ優先検索 、または最優先検索と比較することができます。 A *アルゴリズムは、グラフ前処理が選択肢ではない効率と精度の点で、グラフ検索で広く使用されています。
A *は、評価関数fが特定の方法で定義されているベスト・ファースト・サーチの特化である。
f（n）= g（n）+ h（n）は、最初のノードが思考ノードnに行くように調整された目標までの最小コストである。
g（n）は初期ノードからnまでの最小コストです。
H（n）は 、NからNに最も近い目標に最小コストであります
A *は情報に基づいた検索アルゴリズムであり、可能な限り最小の時間（ 許容可能なヒューリスティックを使用する場合）で最小のパス（最小コストのパス）を見つけることを常に保証します。それで、それは完全で最適です。次のアニメーションは、A * search-
A *アルゴリズムを用いた8-パズル問題の解法
問題の定義 ：
8パズルは、3 x 3グリッド（9つの正方形を含む）で構成される単純なゲームです。正方形の1つは空です。オブジェクトは、四角に移動して別の位置に移動し、数字を「目標状態」に表示します。
8パズルゲームの初期状態と到達すべき最終状態が与えられると、初期状態から最終状態に到達する最も費用効果の高い経路を見つける。
初期状態 ：
_ 1 3
4 2 5
7 8 6
最終状態 ：
1 2 3
4 5 6
7 8 _
ヒューリスティックな仮定 ：
この問題のステートメントのヒューリスティックとして、現在と最終状態の間のマンハッタンの距離を考えてみましょう。
h(n) = | x - p | + | y - q |
where x and y are cell co-ordinates in the current state
p and q are cell co-ordinates in the final state
総コスト関数 ：
したがって、総コスト関数f(n)は、
f(n) = g(n) + h(n), where g(n) is the cost required to reach the current state from given initial state
問題の解決策 ：
最初に、初期状態から最終状態に到達するために必要なヒューリスティックな値を見つけます。コスト関数、g（n）= 0、初期状態にある
h(n) = 8
上記のような値が得られ、 1現在の状態では、1つの水平距離離れよりも1最終状態です。同じことがのために行く2 、 5 、 6 。 _は水平方向に2距離、垂直方向に2距離です。したがって、 h(n)合計値は1 + 1 + 1 + 2 + 2 = 8です。総コスト関数f(n)は8 + 0 = 8に等しくなります。
さて、初期状態から到達可能な状態が見つかると、 _を右または下に移動できます。
したがって、これらの移動を移動した後に得られる状態は次のとおりです。
1 _ 3 4 1 3
4 2 5 _ 2 5
7 8 6 7 8 6
(1) (2)
ここでも、全コスト関数は、上述の方法を用いてこれらの状態について計算され、それぞれ6および7であることが分かる。我々は状態（1）である最小コストの状態を選んだ。次に可能な移動は、左、右または下になります。我々はその状態で以前のように左に移動しません。したがって、右または下に移動できます。
再び、（1）から得られた状態を見つける。
1 3 _ 1 2 3
4 2 5 4 _ 5
7 8 6 7 8 6
(3) (4)
（3）は6に等しいコスト関数につながり、（4）は4につながる。また、（2）はコスト関数が7になる前に得られることを考慮する。次に可能な移動は、左または右または下になります。我々は州を得る：
1 2 3 1 2 3 1 2 3
_ 4 5 4 5 _ 4 8 5
7 8 6 7 8 6 7 _ 6
(5) (6) (7)
（5）、（6）、（7）のコストはそれぞれ5,2,4となります。また、以前の状態（3）と（2）にそれぞれ6と7があります。我々は（6）である最小コスト状態を選んだ。次の可能な動きはUp、Downであり、明確にDownは私たちを最終状態に導き、ヒューリスティック関数の値が0になるようにします。
A *障害物のない迷路を通る経路探索
次の4 x 4グリッドがあるとしましょう：
これが迷路であると仮定しよう。しかし、壁や障害物はありません。出発点（緑色の四角形）と終点（赤い四角形）のみがあります。緑色から赤色になるために、我々は斜めに動くことができないと仮定しよう。そこで、緑色の四角形から始めて、どの四角形に移動できるかを見て、青色で強調表示してみましょう：
次に進むべき四角形を選択するには、2つのヒューリスティックを考慮する必要があります。
- "g"値 - これは、このノードが緑色の正方形からどれくらい離れているかです。
- "h"値 - これは、このノードが赤い四角からどのくらい離れているかです。
- "f"値 - これは "g"値と "h"値の合計です。これは、どのノードに移動するかを指示する最後の番号です。
これらの経験則を計算するために、これは私たちが使用する式です： distance = abs(from.x - to.x) + abs(from.y - to.y)
これは「マンハッタン距離」の式として知られています。
abs(3 - 2) + abs(2 - 2) = 1緑の四角形のすぐ左側の青い正方形の "g"の値を計算しましょう。
すばらしいです！ 1.値を計算してみましょう： abs(2 - 0) + abs(2 - 0) = 4
完璧。さて、 "f"値を取得しましょう： 1 + 4 = 5
したがって、このノードの最終的な値は「5」です。
他のすべての青い四角に対しても同じことをしましょう。左上の数字は「g」の値で、右上の数字は「h」の値ですが、各正方形の中央の大きな数字は「f」の値です。
すべての青色ノードのg、h、fの値を計算しました。今、私たちはどちらを選ぶのですか？
どちらが最低のf値を有するか。
しかし、この場合、同じf値を持つ2つのノードがあります。
単に、ランダムに選択するか、または優先順位を設定します。私は通常、次のような優先順位を持つことを好みます： "右>上>下>左"
f値が5のノードの1つが「下」方向に、もう一方が「左」になります。 DownはLeftよりも優先順位が高いので、私たちは「Down」となる四角形を選択します。
私たちはヒューリスティックを計算したノードをオレンジ色にしましたが、シアン色として選択したノードにマークしました。
さて、シアンノードの周りのノードについて同じヒューリスティックを計算しましょう。
ここでも、すべてのオプションが同じf値を持つため、シアンノードからノードを選択します。
シアンノードが持つ唯一のネイバーのヒューリスティックを計算しましょう。
申し訳ありませんが、同じパターンに従うので私たちは次のようにしています：
もう一度、ノードの隣人のヒューリスティックを計算しましょう：
そこに行こう：
最後に、我々は私たちの隣に勝利の広場があることがわかります。そこで私たちはそこに移動し、私たちは完了です。
