元数据卡

• 前置知识：Vol 2 图与树、Vol 10 线性代数
• 预计时间：45 分钟
• 核心难度：进阶
• 阅读模式：高度专注
• 完成标志：能用 Python 实现 BFS、DFS、A* 和极小化极大搜索

你的进度

想起阿花在信里说“它要是能自己学就好了”——于是你推开模型工坊的门，从最简单的智能行为开始：在一个给定的空间里找到路径。

你的任务

一个智能体面对一个未知环境，首先需要的能力是什么？是搜索。在已知的状态空间中找到目标，是所有推理和学习的起点。本章实现四种搜索算法，观察它们如何在不同场景下权衡代价与最优性。

本章分层

• 必读：BFS、DFS、A*
• 选读：博弈树搜索与 alpha-beta 剪枝
• 进阶：将搜索视为通用问题求解框架

破局 · 溯源

想象你站在迷宫入口。面前有无数岔路，目标在某一扇门后面。你怎么找到它？

最朴素的想法：一条路走到底，撞墙就退回上一个岔路——这是深度优先搜索。但它不保证找到最短路径。那换个方式，把所有岔路按离入口的距离依次探索——这是广度优先搜索，保证最短路径，但需要记住很多没用的路。

如果迷宫的每条路都有"路况"标记（哪条更短、哪条有障碍），你可以用 A*：选一个启发式函数（比如直线距离）引导你优先走"看起来最有可能"的方向。这就是从盲目搜索到启发式搜索的跃迁。

BFS 与 DFS

我们从最简单的状态开始：一个树形结构，每个节点有若干子节点。

# ch01_search.py
from collections import deque

def bfs(tree, root, target):
    """广度优先：逐层搜索"""
    queue = deque([root])
    visited = set()

    while queue:
        node = queue.popleft()
        if node == target:
            return True
        visited.add(node)
        for child in tree.get(node, []):
            if child not in visited:
                queue.append(child)
    return False

def dfs(tree, root, target):
    """深度优先：一条路走到黑"""
    stack = [root]
    visited = set()

    while stack:
        node = stack.pop()
        if node == target:
            return True
        visited.add(node)
        for child in tree.get(node, []):
            if child not in visited:
                stack.append(child)
    return False

运行看看：

tree = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['G'],
    'F': [],
    'G': []
}

print(bfs(tree, 'A', 'G'))  # True
print(dfs(tree, 'A', 'G'))  # True

两者都能找到目标，但路线不同。BFS 从 A → B→C→D→E→F→G，DFS 从 A→C→F→...→B→E→G。在一个更宽的树上，BFS 需要 O(b^d) 的空间（b=分支因子，d=深度），而 DFS 只需要 O(d)。

A 搜索*

现在引入代价。每条边有通行成本，你希望找到总成本最小的路径。Dijkstra 能解决（BFS 的加权版本），但在搜索空间巨大时太慢。A* 加了一个启发式函数 h(n) 来估计从 n 到目标的距离，优先探索 f(n) = g(n) + h(n) 最小的节点，其中 g(n) 是从起点到 n 的实际代价。

import heapq

def a_star(graph, start, goal, heuristic):
    """A* 搜索：g(n) + h(n) 引导搜索方向"""
    open_set = [(0, start)]
    g_score = {start: 0}
    came_from = {}

    while open_set:
        _, current = heapq.heappop(open_set)
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1]

        for neighbor, cost in graph.get(current, []):
            tentative_g = g_score[current] + cost
            if tentative_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score, neighbor))

    return None  # 无路径

如果 h(n)=0，A* 退化为 Dijkstra。如果 h(n) 是实际最短距离的下界（可采纳），A* 保证找到最优解。曼哈顿距离是网格地图上常用的可采纳启发式。

寻找最优路径的过程是对搜索空间进行剪枝的过程——A 用启发式告诉你哪些方向值得下去。*

博弈树搜索

搜索不只用于路径。下棋时，你也在搜索：在当前的局面（状态）下，走哪一步能最大化你的胜率。极小化极大算法（Minimax）递归地评估每个走法：你选对自己最有利的，对手选对你最不利的。

def minimax(state, depth, maximizing):
    if depth == 0 or is_terminal(state):
        return evaluate(state)

    if maximizing:
        value = -float('inf')
        for move in get_moves(state):
            value = max(value, minimax(move, depth - 1, False))
        return value
    else:
        value = float('inf')
        for move in get_moves(state):
            value = min(value, minimax(move, depth - 1, True))
        return value

这棵树是极大层和极小层交替的。Alpha-beta 剪枝在遍历过程中记录两个值：alpha（当前已知的最大下界）和 beta（当前已知的最小上界），一旦 beta <= alpha，就剪掉剩下的分支。

def alpha_beta(state, depth, alpha, beta, maximizing):
    if depth == 0 or is_terminal(state):
        return evaluate(state)

    if maximizing:
        value = -float('inf')
        for move in get_moves(state):
            value = max(value, alpha_beta(move, depth - 1, alpha, beta, False))
            alpha = max(alpha, value)
            if beta <= alpha:
                break  # beta 剪枝
        return value
    else:
        value = float('inf')
        for move in get_moves(state):
            value = min(value, alpha_beta(move, depth - 1, alpha, beta, True))
            beta = min(beta, value)
            if beta <= alpha:
                break  # alpha 剪枝
        return value

理想情况下，alpha-beta 剪枝将搜索空间从 O(b^d) 降到 O(b^{d/2})——翻了一倍的搜索深度，代价是零。

常见陷阱

• BFS 和 DFS 在无限状态空间时出问题：BFS 可能耗尽内存，DFS 可能永不回头（要用深度限制或迭代加深）。
• A* 的启发式不可采纳时能显著加速，但牺牲最优性。
• 极小化极大对深层搜索极度敏感——没有 alpha-beta 剪枝，深 10 层的国际象棋树有约 35^10 ≈ 2.7e15 个节点。
• 搜索算法依赖状态表示——同样的迷宮，抽象的"房间-走廊"图和像素级网格图，搜索成本差几个数量级。

通关挑战

• 热身（10 分钟）：在 5x5 网格上，用 A* 找一条绕过障碍物的路径，先后用曼哈顿距离和欧几里得距离做启发式，观察节点访问量差异。
• 挑战（30 分钟）：实现一个井字棋 AI，用 alpha-beta 剪枝。让它和自己对弈，你能击败它吗？
• 观察：在 A* 中打印每个扩展节点的 f、g、h 值，理解三个值如何协同工作。

旅人笔记

搜索是智能的基础操作。从路径规划到博弈对弈，本质上都是在状态空间中做选择，区别只在代价函数和搜索策略。

-> 下一站预告

解决了"怎么找"的问题，下一步是"怎么表示知识，让机器能推理"。