探索アルゴリズム

同じ答えにたどり着くのに、探し方を変えると手数がどれだけ変わるかを見ます。並んだデータから数を探す2つの方法と、迷路を進む2つの方法を扱います。

• 線形探索: 左端から順に1つずつ調べていきます。
• 二分探索: まん中の値と比べて、探す範囲を半分ずつ捨てていきます。あらかじめ整列済みであることが条件です。
• 2つを上下に並べて同時に再生するので、比較回数の差がそのまま見えます。データ数を増やしたときの最大比較回数も表で比べられます。
• 幅優先探索（BFS）: 近いマスから順に、輪を広げるように調べます。次に見る候補はキューに入ります。見つかる経路は必ず最短です。
• 深さ優先探索（DFS）: 行けるところまで進み、行き止まりで引き返します。次に見る候補はスタックに入ります。見つかる経路は最短とは限りません。
• 迷路のマスをクリックすると壁を壊したり作ったりできるので、自分で道を変えて試せます。