6.1 搜索问题基础

6.1.1 问题形式化

• 状态空间：所有可能状态的集合 S
• 初始状态：s ∈ S
• 目标状态：G S
• 动作集合：A(s) 在状态 s 可执行的动作
• 转移模型：Result(s, a) → s'
• 路径耗散：c(s,a,s') ≥ 0

6.1.2 关键指标

6.2 无信息搜索策略

6.2.1 广度优先搜索(BFS)

def BFS(start):
    queue = [start]
    visited = set()
    while queue:
        node = queue.pop(0)
        if node in G: 
            return node
        for child in expand(node):
            if child not in visited:
                visited.add(child)
                queue.append(child)

• 特点：
• 完备性：是（有限状态空间）
• 最优性：是（动作耗散相同）
• 时间复杂度：O(b^d)
• 空间复杂度：O(b^d)

6.2.2 深度优先搜索(DFS)

def DFS(node):
    if node in G: 
        return node
    for child in expand(node):
        result = DFS(child)
        if result: 
            return result

• 特点：
• 完备性：否（可能陷入无限分支）
• 最优性：否
• 时间复杂度：O(b^m)
• 空间复杂度：O(bm)

6.2.3 迭代加深搜索(IDS)

def IDS(start):
    depth = 0
    while True:
        result = DLS(start, depth)
        if result: 
            return result
        depth += 1

• 折中方案：融合了 BFS 的完备性与 DFS 的空间效率

6.3 启发式搜索策略

6.3.1 A*算法

• 评估函数：f(n) = g(n) + h(n)
• g(n)：从初始节点至 n 的实际耗散
• h(n)：n 到目标节点的启发式估计

def AStar(start):
    open_set = PriorityQueue([(start, h(start))])
    g_score = {start: 0}
    while open_set:
        current = open_set.pop()
        if current in G: 
            return reconstruct_path(cameFrom, current)
        for neighbor in expand(current):
            tentative_g = g_score[current] + c(current, neighbor)
            if tentative_g < g_score.get(neighbor, float('inf')):
                cameFrom[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score = tentative_g + h(neighbor)
                open_set.add(neighbor, f_score)

6.3.2 启发函数设计原则

• 可采纳性：h(n) ≤ h*(n) （h*为真实耗散）
• 一致性：h(n) ≤ c(n, a, n’) + h(n’)
• 典型启发函数：
• 曼哈顿距离（于网格路径中）
• 欧几里得距离（在连续空间里）
• 放松问题的最优解（如八数码问题）

6.4 局部搜索算法

6.4.1 爬山法

def HillClimbing(current):
    while True:
        neighbors = expand(current)
        next = max(neighbors, key=lambda n: f(n))
        if f(next) <= f(current): 
            return current
        current = next

• 变体：
• 随机重启爬山
• 首选爬山（选取第一个改进邻接点）

6.4.2 模拟退火

def SimulatedAnnealing(current, T0):
    T = T0
    while T > T_min:
        next = random.choice(expand(current))
        ΔE = f(next) - f(current)
        if ΔE > 0 or random.random() < exp(ΔE/T):
            current = next
        T = α * T

6.5 约束满足问题(CSP)

6.5.1 标准形式

• 变量：X = {X, …, X}
• 值域：D = {D, …, D}
• 约束：C = {C, …, C}

6.5.2 回溯搜索

def Backtracking(assignment, csp):
    if is_complete(assignment): 
        return assignment
    var = select_unassigned_var(csp)
    for value in order_domain_values(var, assignment):
        if is_consistent(var, value, assignment):
            assignment[var] = value
            result = Backtracking(assignment, csp)
            if result: 
                return result
            del assignment[var]
    return None

6.6 博弈树搜索

6.6.1 Minimax 算法

def Minimax(node, depth, maximizingPlayer):
    if depth == 0 or is_terminal(node):
        return evaluate(node)
    if maximizingPlayer:
        value = -float('inf')
        for child in expand(node):
            value = max(value, Minimax(child, depth - 1, False))
        return value
    else:
        value = float('inf')
        for child in expand(node):
            value = min(value, Minimax(child, depth - 1, True))
        return value

6.6.2 Alpha-Beta 剪枝

def AlphaBeta(node, depth, α, β, maximizingPlayer):
    if depth == 0 or is_terminal(node):
        return evaluate(node)
    if maximizingPlayer:
        value = -float('inf')
        for child in expand(node):
            value = max(value, AlphaBeta(child, depth - 1, α, β, False))
            α = max(α, value)
            if α >= β: 
                break  # β 剪枝
        return value
    else:
        value = float('inf')
        for child in expand(node):
            value = min(value, AlphaBeta(child, depth - 1, α, β, True))
            β = min(β, value)
            if β <= α: 
                break  # α 剪枝
        return value

6.7 实际应用案例

6.7.1 路径规划

• 算法选择：
• 精确路线：A*（带地理距离启发式）
• 实时导航：D* Lite（动态环境）

6.7.2 机器人任务调度

• 方法组合：
• 高层任务分配：约束满足
• 底层运动规划：RRT*（采样优化）

6.7.3 游戏 AI 开发

• 技术栈：
• 战略层：Monte Carlo 树搜索
• 战术层：行为树 + 效用函数

小结

搜索算法构筑了 AI 问题求解的基础架构，应当依据问题的特质来选定策略：

• 对于完全信息确定性问题，宜采用系统化搜索。
• 面对大规模的状态空间，则需借助启发式引导。
• 若涉及多 Agent 对抗，应进行博弈树分析。
• 针对复杂约束，可运用 CSP 建模。

关键词：状态空间、A*算法、可采纳启发式、约束传播、Minimax 决策。