経路探索実験室
壁を描いて、道の探し方を変える。探索したマスと見つけた経路を一歩ずつ観察しよう。
入力や実験結果は送信・保存しません。ページへの通常のアクセス記録は残ります。
1. 地図を作る
マスをクリック／なぞって編集。キーボードでは矢印で移動し、EnterかSpaceで編集できます。移動は上下左右、1歩のコストはすべて1です。
S スタートG ゴール壁探索済み経路
2. 探し方を比べる
地図を編集して、探索を始めてください。
0探索済みマス
—見つけた経路の歩数
0これから調べる候補
表示のため、少数のマスずつ実際に探索を進めます。アニメーションの所要時間はアルゴリズムの処理速度を測ったものではありません。一時停止後は「1マス進める」で続けられます。
BFSとA*は最短経路を探す
BFSは近いマスから順に広げます。A*は「ここまでの歩数＋ゴールまでの縦横の距離」を手がかりに進みます。この地図の条件では、どちらも道があれば最短の歩数になります。
DFSは深く進んで戻る
一つの方向を深く調べ、進めなくなったら戻ります。早くゴールに着くこともありますが、最短経路とは限りません。同じ地図のまま方式を切り替え、探索数と歩数を比べてみましょう。