情報・コンピューティング · アルゴリズム探究 / 原理と探究
最短経路を探す 実験解説
格子の訪問順と最終経路で探索法を比べます。
どのような原理？
幅優先は歩数、ダイクストラは総費用を最小化します。
重要な関係
d(v) = min[d(u) + w(u,v)]
観察してみよう
- 格子の訪問順と最終経路で探索法を比べます。
- 3つの基準条件を実行して記録します。
- 1つの変数を変えて基準記録と比べます。
結果を読み解く
全セルの費用が同じなら両手法の最短距離は？
等しいです · 幅優先は歩数、ダイクストラは総費用を最小化します。
モデルの仮定と限界
上下左右に移動し費用は正です。壁と始終点は再現可能な設定で変えます。