４＊４のパズルをAIに解いてもらうけど、時間かかるようなら一旦良さそう感じに動かして、改めて考えてもらうようにしてみた。
背景
前回作った４＊４の正式名称良く分からないパズルの自動解答機能ですが、ひどい状態の場合、1日待っても帰ってこない。
それじゃあ実用性に欠けるので、最短経路じゃなくても良いから現実的な時間でゴールしよう、という趣旨で機能追加してみた。
ついでに、毎回ひどい、かつ同じ状態に直ぐにセットできるようにボタンも追加してみた。
デモ
v405_async_BDBFS_moveCloserを追加
ソース
前回記事
| 関数名 | 概要 |
|---|---|
helpBtn.addEventListener |
HELPボタン押下時の起点 |
autoSolve() |
探索＋解の再生を行うメイン処理 |
solvePuzzleBidirectional() |
双方向BFS探索ロジック |
buildSolutionPath() |
探索結果からステップを構築 |
moveCloserState() |
探索失敗時にゴールへ近づく |
setInterval(),movedTile |
解を順次再生する繰り返し処理 |
注意、諦めた点
- スタート側、ゴール側の処理は共通化できそうだけど一旦動いているのでよし
- メモリを数百MB使う。再帰実行してたらブラウザが停止したりクラッシュしたりしたのでsetTimeoutに変更
アルゴリズムの概要
探索とは、ある状態（start）から目的状態（goal）までの状態遷移のパス（手順） を見つける処理です。
このアプリでは：
- 状態：スライドパズルのタイル配置（1〜15 と null）
- 遷移：上下左右への合法なタイル移動
双方向幅優先探索（Bidirectional BFS）とは？
通常の幅優先探索（BFS）
- スタートから幅広に探索し、最短経路を見つける
- 計算量：
O(b^d)（b = 分岐数, d = 深さ）
双方向幅優先探索
- スタートとゴールの両側から同時に探索
- 中央で「出会う」ことを目指す
- 計算量：
O(b^{d/2} + b^{d/2})→ 事実上O(b^{d/2})
実装フロー（探索ループ）
-
startFrontier（キュー）に開始状態を入れる -
goalFrontierにゴール状態を入れる -
startVisited,goalVisitedに訪問状態を記録 - whileループで両方から1手ずつ進める（幅優先）
- stateToString() により文字列化し、Map で重複チェック
- trialNodes を数えて上限になれば moveCloserState() へ
- 交差したら
buildSolutionPath()で経路を合成 - 結果は
solvingSolution[]に保存され、UIで順に再生される
while (startFrontier.length > 0 && goalFrontier.length > 0) {
// スタート側から1手進める（getNeighbors）
// → 新しい状態を startVisited に追加
// → その状態が goalVisited に存在すれば交差！
// 同様にゴール側からも1手進める（getReverseNeighbors）
// → 交差チェック
}