A
AIエージェントの仕組み
ch1-s2 · Search & Optimization

探索と最適化

約 12 分

この回のゴール

1. なぜ「探索」が AI なのか

次のような問題を考えてみてください:

これらはすべて 「状態」を移動しながらゴールを探す 問題として定式化できます。これが 状態空間探索 です。

記号主義 AI の時代、AI 研究の大半はこの「探索をどう効率化するか」に費やされました。Deep Blue (チェスでカスパロフに勝った IBM の AI) は本質的には探索アルゴリズムです。

2. 状態空間の数学的定式化

問題を次の 5 つで表します:

記号 意味 迷路の例
$S$ 状態の集合 迷路の各マス
$s_0 \in S$ 初期状態 スタート位置
$G \subseteq S$ ゴール状態の集合 ゴールマス
$A(s)$ 状態 $s$ で取れる行動 上下左右の移動
$c(s, a)$ 行動のコスト 移動1回 = 1

目標: $s_0$ から $G$ の要素までの コスト最小の行動列 を見つける。

$$ \pi^* = \arg\min_\pi \sum_{t} c(s_t, a_t) \quad \text{s.t.} \quad s_T \in G $$

3. 3 つの代表的なアルゴリズム

(a) BFS — 幅優先探索

from collections import deque
def bfs(start, goal, neighbors):
    q = deque([(start, [start])])
    visited = {start}
    while q:
        s, path = q.popleft()
        if s == goal:
            return path
        for ns in neighbors(s):
            if ns not in visited:
                visited.add(ns)
                q.append((ns, path + [ns]))

(b) DFS — 深さ優先探索

(c) A* — ヒューリスティック探索

$$ f(s) = g(s) + h(s), \quad h^*(s) = \text{真のコスト} $$

許容性(admissibility): $h(s) \le h^(s)$ であれば A* は 最短経路を保証* する。

4. 探索でできること・できないこと

✅ できること

❌ できないこと(次の章以降の動機)

👉 だから 機械学習 が必要になります。次のサブステップで扱います。

まとめ

この回の限界(次への動機)

問題 何が起きるか
状態が明確に定義できない そもそも探索木が作れない
状態数が爆発的 全探索は不可能 (囲碁の局面数は $10^{170}$)
入力が曖昧 (画像、自然言語) 「似ている」を定義できない

👉 次回は「機械学習の基礎」。データから関数を学ぶ アプローチによって、ルールや状態を人が書かなくても問題が解けるようになります。

よくある質問

Q. LLM にも探索は関係ある? A. めちゃくちゃ関係あります。LLM が文を生成するときの ビームサーチ や temperature サンプリング は、確率付きの探索です。第 3 章の LLM で触れます。

Q. A* より速い探索はないの? A. 問題の性質に応じて、双方向探索、IDA*、MCTS (囲碁 AI で使われる) など多数あります。MCTS は AlphaGo でも核となる技術です。

Q. なぜ AI エージェントで探索を学ぶ必要がある? A. エージェントの「複数ステップ計画」は 状態空間探索の拡張 だからです。第 6 章で再登場します。

参考文献

📝 理解度クイズ (3 問) 💡 ログインすると進捗が保存されます

💬 このサブステップの Q&A

まだ質問はありません。最初の質問を投稿してみましょう。

質問の投稿にはログインが必要です。