以下の動画の、内容を要約しました。
https://youtu.be/5NgNicANyqM?si=Qc3Dzaw6gf3x5qmd
宇宙探索アルゴリズムの解説：深さ優先探索（DFS）と幅優先探索（BFS）の比較、そして改良案
宇宙探索や迷路解決のアルゴリズムとしてよく用いられる 深さ優先探索（DFS） と 幅優先探索（BFS） は、それぞれ異なる特性とトレードオフを持っています。本記事ではこれら2つのアルゴリズムを比較し、さらに効率的な探索方法について検討します。
深さ優先探索（DFS）とは？
DFSは、初期状態から最も深い状態まで一つのパスを辿り、行き止まりに到達すると元に戻って別のパスを探索する方法です。このアルゴリズムは「スタック」をデータ構造として使用し、最後に追加されたノードを優先的に探索します。
特徴
- 長所: メモリ消費が少ない（探索時に記録するノードが少なくて済む）。
- 短所: 最適解が見つからない場合がある（回り道を選択する可能性がある）。
例
迷路内でゴールを目指す場合、DFSは一つの方向に突き進み、行き止まりに到達すると別の道を探索します。このため、効率的な経路を見つけるのではなく、遠回りをする可能性があります。
幅優先探索（BFS）とは？
BFSは、初期状態から近い順にすべてのノードを探索する方法です。「キュー」をデータ構造として使用し、最初に追加されたノードを優先的に探索します。
特徴
- 長所: 最短経路（最小コストの解）を見つけやすい。
- 短所: メモリ消費が大きい（探索範囲が広がるため、記録するノード数が増える）。
例
迷路内でゴールを目指す場合、BFSは初期位置から近いノードを順に探索し、効率的な経路を見つけることができます。ただし、探索範囲が広がると多くの無関係なノードも調べるため、メモリを多く使用します。
DFSとBFSのトレードオフ
DFSは少ないメモリで実行可能ですが、最短経路を保証しません。一方、BFSは最短経路を見つける可能性が高いですが、探索範囲が広がるとメモリを大量に消費します。この違いにより、用途や問題の特性に応じて適切なアルゴリズムを選択する必要があります。
改良案：ヒューリスティックを用いた探索
DFSやBFSの課題を解決するために、問題特有の知識を活用した「ヒューリスティック探索」が有効です。この方法では、探索するノードを選ぶ際に「ゴールへの推定距離」を利用します。
1. グリーディ最良優先探索（Greedy Best-First Search）
このアルゴリズムでは、ゴールに最も近いと思われるノードを優先して探索します。距離の推定には、以下のような方法を使います：
- マンハッタン距離: ゴールまでの垂直・水平距離を合計した値。
- ヒューリスティック関数: ( h(n) ) という数値で、ノード ( n ) がゴールにどれだけ近いかを評価。
特徴
- 長所: 探索範囲を絞り込み、効率的な経路を見つける。
- 短所: 最適解を保証しない場合がある（推定が間違っていると回り道を選択する）。
例
迷路内でゴールを目指す際、右方向に進む方がゴールに近いと推定できる場合、右のノードを優先して探索します。この方法により、不要な探索を減らし効率化が図れます。
プログラムの実装
基本構造
以下はPythonでの迷路解決プログラムの概要です：
-
ノードの定義:
- 状態、親ノード、アクションを記録。
- パスコストは後から計算。
-
データ構造:
- スタック（DFS）またはキュー（BFS）を使用。
- グリーディ探索ではヒューリスティック関数を追加。
-
探索アルゴリズム:
- 初期ノードをフロンティアに追加。
- ループ内でノードを取り出し、ゴールテストを実行。
- ゴールに到達しない場合、隣接ノードを追加。
結論
DFSとBFSは、それぞれ異なる状況に適した探索アルゴリズムです。さらに効率を追求する場合、ヒューリスティックを活用したグリーディ探索のような手法を検討すべきです。特に迷路のような問題では、問題特有の知識を反映したアルゴリズムが有用であり、探索効率を大幅に向上させる可能性があります。