ーーーー講義録始めーーーー
AIにおける探索の概要
次に、探索について説明します。AIにおける探索とは、問題が与えられた初期状態（スタート地点）から、問題が解かれた状態（ゴール地点）に移行する経路や手順を見つけることを指します。
探索は大きく盲目的探索とヒューリスティック探索に分けられます。最初に盲目的探索について説明しますので、印刷教材の図1-1をご覧ください。この図では、迷路内の分岐点や行き止まりを記号で表しています。
- 濃いサークルの"S"：出発点
- 濃いサークルの"G"：目標点
- 白いサークル：分岐点
- 薄いサークル：行き止まり
この迷路では、左上の"S"（出発点）にいるロボットが、右下の"G"（目標点）に移動する経路を探索することが課題です。
迷路図を木構造に変換する
人間は迷路を見ればゴールへの経路をすぐに見つけることができますが、AIにとってはこの図をそのまま扱うのは難しいため、通常は木構造に変換します。出発点"S"をルートノード（根）とし、各分岐点や経路をノードとして木構造を展開します。この変換により、AIが探索を効率的に処理できるようになります。印刷教材の図1-2をご覧いただくと、この迷路図が木構造として表現されていることがわかります。
盲目的探索の基本
盲目的探索とは、ゴールへの到達のしやすさを考慮せず、決まった原則に従って機械的に探索を進める方法です。代表的な手法として次の2つがあります：
- 深さ優先探索（Depth-First Search, DFS）
- 木構造の深さを優先して探索。縦方向に進める限り進み、行き止まりに達したら逆戻りして横方向に移動します。
- 幅優先探索（Breadth-First Search, BFS）
- 木構造の横方向を優先して探索。全てのノードを深さごとに順に探索します。
印刷教材の図1-3には、深さ優先探索の結果が示されています。この図では、各エッジに番号が振られており、その番号に従って縦方向を優先的に探索する様子が視覚的に理解できます。
深さ優先探索の具体例
探索の流れは以下のようになります：
- 出発点"S"から分岐点"A"、"B"、"D"と縦方向に進む。
- "D"で行き止まりに到達したため逆戻りし、"B"から再び探索を開始。
- "E"を経由して"G"（ゴール）に到達し、探索が完了する。
このように盲目的探索は、すべての可能性を網羅的に探索するため、解が見つかる保証があります。しかし、探索範囲が広がると時間や計算量が膨大になるという課題があります。
ヒューリスティック探索とその進化
このような課題を克服するために開発されたのが、ゴールへの到達容易性を評価するヒューリスティック探索です。この手法では、ゴールに到達するコストを推定するための評価関数を利用します。代表的な手法には次のものがあります：
- 最良優先探索（Best-First Search）
- A*アルゴリズム（A-Star Algorithm）
特にA*アルゴリズムは、以下のコストを考慮して最適な経路を見つける方法です：
- g(n)：スタートから現在のノードまでの移動コスト。
- h(n)：現在のノードからゴールまでの推定コスト（ヒューリスティック関数）。
- f(n) = g(n) + h(n)：総コスト。
A*アルゴリズムは、ロボットの行動計画や地図探索など、AIの多くの分野で活用されています。具体的な例については、印刷教材をご覧ください。
