6、搜索算法与求解策略

大家好，欢迎来到IT知识分享网。

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 决策。