探索アルゴリズムの可視化
探索は対象を見つけるだけでなく、どこから見て、何を省くかを決めます。コードと同期した図で、ソート済み配列の範囲の半減、グラフの層ごとの拡張、ヒューリスティックによる探索先の選択を見ます。
線形探索は整列を要求せず、前から調べ、最悪では全要素を読みます。他の方法は構造を使います。二分探索は順序で半分を除外し、二ポインターは整列済み配列の数の組を両端から絞ります。本例のスライディングウィンドウは連続部分配列、非負値、正の目標を前提に両端を前へ進めます。累積和は配列が変わらないことに賭けます。最初に 1 回の走査で累計を作れば、以後どの区間和も引き算 1 回です。BFS と DFS はキューかスタックで次の頂点を選び、A* は残り費用の推定を加えます。最短路の保証には、それぞれの条件が必要です。
探索レッスンの見方
- 何を除くか：二分探索は約半分の候補を捨て、グラフ走査は訪問済み印で重複処理を避けます。
- どの順に訪れるか：BFS はキューで近い順、DFS はスタックや再帰で深く進んで戻ります。隣接リストでは双方 O(V + E) でも、軌跡が異なります。
- 前提は何か：二分探索には整列が必要です。BFS と DFS は一般のグラフを歩けますが、無重みの最少辺経路を保証するのは BFS の層順です。
- 推定を信頼できるか：A* は実費用
gと推定hを足します。hが一貫的（目標で 0、一歩ごとの減少がその歩の費用以下）なら、閉じたマスを開き直さない本例の実装でも最短路を保ちます。過大評価なら、最初に取り出した目標が最適とは限りません。
アルゴリズムの比較
| 方法 | 対象 | 時間 | 追加領域 | 前提・道具 | 順序 |
|---|---|---|---|---|---|
| 線形探索 | 任意の配列 | O(n) | O(1) | 整列不要 | 前から後ろ |
| 二分探索 | 整列済み配列 | O(log n) | O(1) | 整列 | 範囲を半分にする |
| 二ポインター | 整列済み配列 | O(n) | O(1) | 整列 | 両端から寄せる |
| スライディングウィンドウ | 連続部分配列 | O(n) | O(1) | 本例は非負値と正の目標 | 右を広げ、左を縮める |
| 累積和 | 区間和 | 構築 O(n)、クエリ O(1) | O(n) | ほとんど変わらない配列 | 2 本の区切り、引き算 1 回 |
| 幅優先探索 | グラフ／木 | O(V + E) | O(V) | キュー | 近い順 |
| 深さ優先探索 | グラフ／木 | O(V + E) | O(V) | スタック | 深い方を優先 |
| 木走査 | 二分木 | O(n) | O(h) | 再帰／スタック | 前順・中順・後順 |
| 連結成分 | 無向グラフ | O(V + E) | O(V) | 訪問集合 | 各島を走査して埋める |
| A* | 重み付き格子／グラフ | 本例 O((V + E) log V) | O(V + E) | 最短路条件を満たす推定 | 最小 g + h |
すべてが同じ問いを競うわけではありません。二分探索は整列列中の値を、グラフ探索は頂点の接続を調べます。BFS と DFS は訪問順の直接比較です。A* は Dijkstra に似た優先キューへ推定を加え、目標方向へ探索を集中します。
推奨する学習順序
線形探索で一つずつ読み、見つかれば止まります。最悪では全配列が必要です。構造を知れば何を省けるか、という問いにつなげます。
二分探索は比較で候補を半減し、百万の整列済み要素を最大約二十回で調べます。線形の最悪は百万回です。次の二ポインターも順序を使い、両端から移ります。未整列の失敗例は有効な組を飛ばし、前提の必要性を示します。
スライディングウィンドウは両指標を同じ方向へ進めます。各要素の追加と除去は最大一回ずつで O(n) です。負値の例では単調性が崩れ、縮め方がより短い有効窓を見逃します。
累積和は窓を探すのをやめ、答えを先に計算します。O(n) の 1 回の走査で累計を書き、区間和は prefix[r + 1] − prefix[l]、長さに関係なく 2 つ読むだけです。破綻点は一点更新で、それ以降の累計がすべて古くなります。
次に BFSでグラフへ進み、層順から無重み最短路を得ます。DFSではキューをスタックへ変え、深く進む順を比較します。木走査は二分木の DFS で、子の呼び出しの前、間、後のどこで記録するかにより前順・中順・後順になります。
連結成分は外側の走査を加え、未着色の頂点ごとに探索を開始します。開始回数が島の数で、孤立頂点も一成分です。最後の A*は FIFO／LIFO を g + h 順へ変え、過大評価の失敗例で保証の境界を確認します。
探索の可視化一覧
入力やグラフを変え、訪問と除外の順をコードと照合してください。