Appearance
搜索、CSP 与博弈
基本原理
AIMA 将许多 AI 问题抽象为状态空间搜索：给定初始状态、动作、转移模型、目标测试和路径代价，算法在可能状态中寻找到达目标的行动序列。这个思想仍然影响现代 Agent planning、工具调用路径选择、机器人导航和自动排程。
约束满足问题（CSP）把问题表达为变量、取值域和约束；博弈搜索则处理多智能体对抗环境，典型代表是 Minimax 和 Alpha-Beta 剪枝。
解决的问题
搜索、CSP 与博弈解决的是“候选方案巨大，不能靠枚举人工挑选”的问题。搜索负责找到通往目标的路径，CSP 负责在约束下找到可行赋值，博弈搜索负责在对手也会行动的情况下选择稳健策略。
应用场景
典型场景包括机器人路径导航、自动排课、实验流程排程、工艺参数组合筛选、物流路径规划、棋类 AI、对抗模拟，以及现代 Agent 在多工具、多步骤任务中的行动路径选择。
搜索算法
| 算法 | 基本原理 | 解决的问题 | 适用场景 |
|---|---|---|---|
| BFS | 按层展开，先找到步数最少解 | 无权图最短步数 | 迷宫、状态空间小的问题 |
| DFS | 沿一条路径深入，再回溯 | 快速探索深路径 | 解空间大但可回溯的问题 |
| UCS | 按累计路径代价最小展开 | 非均匀代价最短路径 | 物流、路径规划 |
| A* | 用 f(n)=g(n)+h(n) 结合已知代价和启发式 | 高效最优搜索 | 导航、机器人、排程 |
产品视角
搜索和规划不是只服务机器人路径，它也解释了为什么 Agent 需要多步执行。产品上遇到“先查资料、再判断、再调用系统、最后生成结果”的需求，本质就是状态、动作、目标和约束组成的搜索/规划问题。
| 产品场景 | 状态 | 动作 | 目标 | 风险 |
|---|---|---|---|---|
| 路径规划 | 当前地点、障碍、成本 | 移动到下个点 | 最短或最低成本到达 | 地图变化、成本估计错误 |
| 工作流自动化 | 当前工单、权限、审批状态 | 分派、补充资料、流转 | 按规则完成流程 | 越权、不可逆动作 |
| Agent 多步执行 | 上下文、工具结果、任务进度 | 检索、调用工具、总结、追问 | 完成用户目标 | 工具失败、循环调用、幻觉 |
| 实验流程 | 样品、图像、传感器、步骤 | 采集、分析、绘图、报告 | 得到可复核结论 | 中间结果未校验 |
AI PM 评审这类方案时要问：状态空间是否清楚、每个动作是否可观察、失败是否可回滚、是否需要人工确认、计划是否可以中途重算。
最小代码示例
A* 搜索
python
from heapq import heappop, heappush
def astar(graph, start, goal, h):
frontier = [(h(start), 0, start, [start])]
visited = set()
while frontier:
_, cost, node, path = heappop(frontier)
if node == goal:
return path, cost
if node in visited:
continue
visited.add(node)
for nxt, step_cost in graph[node]:
heappush(frontier, (cost + step_cost + h(nxt), cost + step_cost, nxt, path + [nxt]))
return None, float("inf")
graph = {
"A": [("B", 1), ("C", 4)],
"B": [("D", 2)],
"C": [("D", 1)],
"D": []
}
path, cost = astar(graph, "A", "D", h=lambda n: {"A": 2, "B": 1, "C": 1, "D": 0}[n])
print(path, cost)约束满足 CSP
CSP 解决的是“变量很多、约束很多、组合爆炸”的问题。地图着色、排课、生产排程、资源分配、N 皇后都可以看作 CSP。
Backtracking CSP
python
def backtrack(assign, variables, domains, constraints):
if len(assign) == len(variables):
return assign
var = next(v for v in variables if v not in assign)
for value in domains[var]:
candidate = {**assign, var: value}
if all(rule(candidate) for rule in constraints):
result = backtrack(candidate, variables, domains, constraints)
if result:
return result
return None
variables = ["WA", "NT", "SA"]
domains = {v: ["red", "green", "blue"] for v in variables}
constraints = [
lambda a: "WA" not in a or "NT" not in a or a["WA"] != a["NT"],
lambda a: "WA" not in a or "SA" not in a or a["WA"] != a["SA"],
lambda a: "NT" not in a or "SA" not in a or a["NT"] != a["SA"],
]
print(backtrack({}, variables, domains, constraints))博弈搜索
Minimax 假设对手也会理性选择最优行动，适合井字棋、棋类、对抗策略。Alpha-Beta pruning 在不改变最终决策的情况下剪掉不可能影响结果的分支。
Minimax
python
def minimax(state, depth, maximizing):
if depth == 0 or state["terminal"]:
return state["score"]
scores = [minimax(child, depth - 1, not maximizing) for child in state["children"]]
return max(scores) if maximizing else min(scores)Python 入口
| 库/仓库 | 用途 |
|---|---|
aima-python | AIMA 搜索、CSP、博弈等算法参考实现 |
networkx | 图搜索、路径、图结构可视化 |
python-constraint | CSP 原型 |
heapq | 实现 UCS/A* 的优先队列 |