初級ガイド

技術ブログ

備忘録 - 8パズル

8パズルを幅優先探索+メモ化で実装した。

幅優先探索

Queueを使って実装した。

いくつか種類があり、用途に応じて使い分ければ良さそう。実行速度や消費メモリの差は要調査。

addで入れてpollで引き出す。終了判定にpeekを使う。

メモ化

グローバル変数にハッシュマップを用意して探索空間の状態を保存する。
次の空間を探索する前にハッシュマップに保存されていないか確認して、すでに保存されていたらその探索を破棄する。

HashMap<String, String> map = new HashMap<String, String>();
ArrayList<Integer> array = new ArrayList<>();

//memo check
String s = array.toString();
if(map.containsKey(s))
 continue;

//memo resist
map.put(s,array.indexOf(9));

参考・その他

スライディングパズルはA*で解くのが一般的らしい。
他の工夫として、ゴールから逆順に辿る処理を通常の探索と交互に挟んでいくことで高速化できるとのこと。

15パズル - Wikipedia

メモ化 - Wikipedia

A* - Wikipedia

www.geocities.jp