--文献、ウェブページリンク--
-論文-
この論文は、最良優先探索アルゴリズムについて、並列処理などの改良を述べた論文である。
例題として、15パズル問題や、その他のスライディングパズル問題が用いられており、
深さと状態数についても述べられている。
この論文は、15パズルや24パズルを例題として、マンハッタン距離を用いた解き方ではなく
パターンデータベースを用いることによって高速化をはかったものである。
パターンデータベースについての説明がされている。
この論文は、上記の論文で書かれたパターンデータベースを基本とし、
新たに動的分割パターンデータベースと呼ばれる方法について提示し、
問題を小さな問題に分割するといった方法をる。
この方法についての長所や短所について議論されている。
-ウェブページ-
このページは、15パズル問題について、深さとそのときの状態数についてのまとめや、
最長手数の盤面について、また、15パズル問題を解くための探索方法の種類について
説明されている。
また、15パズル問題を解くためのプログラムの例が置かれている。
このページは、15パズル問題について、探索方法が主にまとめられている。
とくに、A*探索におけるヒューリスティック関数の種類と、それぞれの特徴
がまとめられている。
また、パターンデータベースの概要についてもまとめられている。
このページは、15パズル問題について、A*探索のヒューリスティック関数について考察されている。
マンハッタン距離などについてや、特に、新たなヒューリスティック関数として、
ID (InvertDistance)や、WD (WalkingDistance)といったヒューリスティック関数を定義しており、
そのヒューリスティック関数についての解説及び、ソースコードなどがまとめられている。