【この記事について】
8パズルを題材にして各アルゴリズムを説明する。
予備知識を必要としないように書いた。
【用語解説】キュー（queue）
先に入れたものが最初に出てくる箱。後に入れたものは後から出てくる。食堂で並んでいるときのように最初に来た人から処理される。
幅優先探索
①動かすことができる方向をすべて試す。
②試してみて目的の状態があった場合は終了。なかった場合は動かしてみてできた状態をすべてキューに入れる(このときキューに入れる順番は問わない)
③キューから一つ状態を取り出す。この状態で①からの作業を繰り返す。
以上を行うことで最初の状態から作ることができる状態を満遍なく試してみることができるが、当然効率はよくない。
(幅優先探索の例。8パズルと必ずしも一致しない。数字は試してみる順番で、1が最初の状態。Wikipediaより)
実装において
アルゴリズムを高速化するために、既に過去に一度試している状態に遭遇した場合は、その状態をキューに入れない処理を加える。
【用語解説】スタック（stack）
後から入れたものが先に出てくる箱。先に入れたものが後に出てくる。食器棚に積まれた皿を取り出すときと同じ。
深さ優先探索
①動かすことができる方向をすべて試す。
②試してみて目的の状態があった場合は終了。なかった場合は動かしてみてできた状態をすべてスタックに入れる(このときスタックに入れる順番は問わない)
③スタックから一つ状態を取り出す。この状態で①からの作業を繰り返す。
深さ優先探索ではひとつの動かせる方向を見つけたら、ひたすら突き進む。
(深さ優先探索の例。8パズルと必ずしも一致しない。数字は試してみる順番で、1が最初の状態。Wikipediaより)
実装において
8パズルでは空いたマスさえあれば駒を動かせることができる。そのため、特に深さ優先探索では途中で目的の状態に到達できればよいが、できなかった場合には無限に探索を続けることになる。そのため、8パズルの最大手数は31手ということを利用して、探す深さに31手という制限をかけた深さ制限探索を用いる。
【用語解説】マンハッタン距離
二つの座標の差（の絶対値）の総和。直線距離(ユークリッド距離)ではないやつ。
(二つの座標間のマンハッタン距離は一つに定まる。どのルートを通っても同じ距離となる。Wkipediaより)
A*アルゴリズム
目的の状態までのかかる手数を予想することで効率を改善したアルゴリズム。
①動かすことができる方向をすべて試す。
②試してみて目的の状態があった場合は終了。なかった場合は動かしてみてできた状態全てにおいて「最初の状態(①の状態ではなく一番最初に与えられた状態)から今の状態までにかかった手数＋h(x)」を計算し、箱に入れる。
③箱の中から計算結果が一番小さい状態を選び取り①に戻る。
h(x)をヒューリスティック関数という。これが目的の状態までかかる手数の予想を担う部分。８パズルにおけるh(x)は
・各駒の今の状態と目的の状態における配置とのマンハッタン距離の和
・各駒の今の状態と目的の状態における配置とのマンハッタン距離の二乗の和
・各駒の今の状態と目的の状態における配置とのマンハッタン距離の和＋マンハッタン距離の標準偏差
が考えられる。
また、h(x)を真の最短手数よりも短いものにしたときにA*アルゴリズムは最短距離を返す
【余談ではあるが】
Supremeのお香はこれらしい
Amazon | SATYA サイババナグチャンパ スティックタイプ 6箱セット | SATYA（サティヤ） | お香
【参考文献】
Java。A*アルゴリズムのプログラム例。ハッシュ関数に最小完全ハッシュ関数を使っている。各マスの動ける方向をハードコーディングしている。
リスト1●「8パズル」を幅優先探索で解くプログラム | 日経 xTECH（クロステック）
https://www.jstage.jst.go.jp/article/konpyutariyoukyouiku/21/0/21_78/_pdf
A*アルゴリズムの改良について。h'(x)に「マンハッタン距離」を使うと特定の状況では「目的の状態との異なるマスの数」に評価関数として劣ることを指摘。目的の状態とのマンハッタン距離が全てのコマで似た値となる場合、全てのコマを同じ程度の回数だけ動かせば目的の状態となることに着目し、
h'(x)=マンハッタン距離＋マンハッタン距離の標準偏差
を提案。
