2. 搜索算法基础

搜索算法的本质是在一个定义良好的问题表示空间中进行系统性的探索，以找到从初始状态到目标状态的路径。在路径规划领域，无论是机器人导航、游戏AI寻路，还是网络路由计算，其底层都依赖于对“图”这一抽象数据结构的建模与遍历。本章将深入剖析搜索算法的四大基石：图与树的数学表示、节点/边/代价的语义、状态空间的概念，以及搜索树与图搜索在算法执行层面的本质区别。理解这些基础，是后续学习Dijkstra、A*、RRT等具体算法的前提。

2.1 图与树的数学表示：从现实地图到抽象数据结构

核心原理：路径规划的第一步是将物理世界或逻辑世界中的“可通行区域”抽象为图（Graph）。图由顶点集合 V（Vertex）和边集合 E（Edge）构成，记作 G = (V, E)。在机器人路径规划中，顶点可以表示离散的栅格、路标点或拓扑节点；边表示顶点之间的直接连通关系。边可以是有向的（如单行道）或无向的（如双向道路），可以带权值（如距离、通行时间、能耗）或不带权值。树（Tree）是图的一种特殊形式，它满足两个条件：连通且无环。树具有唯一的根节点，任意两个节点之间有且仅有一条路径，且边数恰好等于顶点数减一（|E| = |V| - 1）。

判断方法或操作流程：在实际工程中，选择图还是树作为底层模型，取决于问题约束。若环境存在多条路径可达同一节点（即存在环），必须使用图模型；若问题天然具有层级分解特性（如决策树、行为树），则使用树模型。构建图的流程通常为：环境采样 → 节点生成 → 邻接关系判定 → 边代价赋值 → 图存储。存储方式主要有邻接矩阵（适合稠密图）和邻接表（适合稀疏图）。对于大规模路网，邻接表是更优选择，其空间复杂度为 O(V+E)。

2.2 节点、边与代价：搜索优化的核心度量

核心原理：节点（Node）是搜索过程中的基本单元，它代表一个具体的状态或位置。边（Edge）代表状态之间的转移关系，而代价（Cost）是赋予边的非负数值，用于衡量从当前节点转移到后继节点的“消耗”。代价可以是欧氏距离、曼哈顿距离、时间、能量消耗或综合风险值。在加权图中，路径的总代价是路径上所有边代价之和。搜索算法的目标通常是最小化从初始节点到目标节点的总代价。

判断方法或操作流程：代价函数的设计直接决定搜索行为。若所有边代价相同（如无权图），BFS（广度优先搜索）可保证最短路径（最少边数）；若边代价不同，则需要使用Dijkstra或A*算法。代价设计应遵循非负性和可加性原则。在工程中，代价往往需要归一化处理，例如将时间代价与能耗代价加权合并为综合代价：Cost = α·Time + β·Energy + γ·Risk，其中 α、β、γ 为权重系数。

// 邻接表表示带权图（C++风格伪代码）
struct Edge {
    int to;          // 目标节点编号
    double weight;   // 边代价
};
vector<vector<Edge>> graph; // graph[i] 存储节点 i 的所有出边

2.3 状态空间：搜索问题的形式化定义

核心原理：状态空间（State Space）是对问题所有可能状态的数学描述，通常表示为四元组：(S, A, T, G)。其中 S 是状态集合，A 是动作集合，T 是状态转移函数（T: S × A → S），G 是目标状态集合。在路径规划中，状态空间就是所有可行位置的集合，动作就是移动指令（如前进、左转、右转），转移函数描述执行动作后的新位置，目标状态是终点区域。状态空间的规模决定了搜索的复杂度，因此状态压缩和抽象是提高搜索效率的关键。

判断方法或操作流程：构建状态空间时，需要明确三个问题：① 状态粒度——栅格大小或路标密度；② 动作集合——允许的移动方向（4邻域、8邻域或连续转向）；③ 约束条件——障碍物、动力学限制、交通规则。状态空间的维度不仅包含位置，还可能包含速度、朝向、时间等。例如，在动态环境中，状态需要扩展为 (x, y, t) 三维，以处理移动障碍物。

2.4 搜索树与图搜索：算法执行的核心区别

核心原理：搜索树（Search Tree）是搜索算法在运行过程中动态生成的树形结构，其节点对应“状态访问路径”，而非状态本身。也就是说，同一个状态可能通过不同路径被多次访问，从而在搜索树中产生多个节点。图搜索（Graph Search）则维护一个 closed 集合（或 visited 集合），记录已经扩展过的状态，避免对同一状态的重复扩展。这一区别是理解搜索算法正确性与效率的关键。

判断方法或操作流程：判断一个算法属于树搜索还是图搜索，只需检查其是否检测重复状态。BFS、DFS 的朴素实现属于树搜索；Dijkstra、A* 的标准实现属于图搜索（使用 closed 表）。图搜索以额外的内存开销（存储 closed 表）换取时间效率，并保证在有限状态空间中不会陷入无限循环。对于树搜索，在含环图中可能永远无法终止；而图搜索则能保证终止。

常见误区与总结复盘：初学者常混淆“状态”与“节点”的概念。在搜索树中，节点包含指向父节点的指针和路径代价 g(n)，而状态仅描述问题世界的配置。另一个常见误区是认为图搜索总是优于树搜索——在状态空间极大且目标较近时，树搜索可能因内存占用更小而更快找到解（但可能不是最优解）。此外，A* 算法必须使用图搜索（即检测重复状态）才能保证最优性，否则在启发式函数不一致时可能返回次优解。