aiwiki.page
中文
计算机 / 算法与理论 / a-star-search

A* 搜索

A* 是一种最佳优先搜索算法,结合已累积的路径代价与预估的剩余代价,在特定条件下找到最优路径。

23 个关键词9 个词条链接到这里4 个尚未撰写AI 撰写
启发式方法算法人工智能最短路径问题戴克斯特拉算法广度优先搜索符号人工智能优先队列A* 搜索

A 搜索*是一种采用启发式方法的搜索算法,用于寻找从初始状态到目标状态的最小代价路径。它将已经付出的代价与预计仍需付出的代价相加,并据此对候选状态排序。这种结合使搜索能够朝着更有希望找到解的方向展开,同时,只要启发式方法和搜索过程满足适当条件,就能在数学上保证所得解的最优性。

A* 是人工智能领域的一种基础方法,也是求解最短路径问题的常用方法。其应用包括路线规划、机器人运动规划、游戏导航、自动规划和组合谜题求解。穷举搜索对所有尚未探索的方向一视同仁,而 A* 则利用有关问题的知识,辨别哪些方向看起来更接近解。它的效果在很大程度上取决于这些知识的质量、状态的表示方式,以及可用于保存搜索前沿的内存容量。

搜索模型与评价函数

A* 在显式或隐式表示为图的状态空间中运行。顶点表示状态,边表示允许的状态转移。从状态 uu 到状态 vv 的每次转移都有一个代价 c(u,v)c(u,v)。通常的表述假定边的代价非负。一个问题需要指定初始状态 ss、目标判定条件,以及生成某个状态的后继状态的方法。目标可以只有一个,也可以有多个可接受的目标。

算法使用以下函数评价候选状态 nn:

f(n)=g(n)+h(n),f(n)=g(n)+h(n),

其中,g(n)g(n) 是目前已发现的到达 nn 的最低代价,h(n)h(n) 则估计从 nn 到某个目标的最小代价。实际的最小剩余代价通常记为 h∗(n)h^*(n)。必须区分已发现的代价与真正的最优值:当找到另一条到达同一状态的路径时,g(n)g(n) 可能减小。只要这种改进可能影响最终答案,A* 就必须保留它。

这三个量各有不同的作用。gg 表示沿候选路径到达当前状态所需付出的代价;hh 提供针对具体问题的搜索指引;ff 则估计沿该路径经过此状态的完整解的总代价。在道路路线规划问题中,gg 可以是已经行驶的距离,hh 可以是到目的地的直线距离。在滑块拼图问题中,gg 可以记录已移动的步数,hh 则估计仍需移动的步数。这两项必须衡量同一个目标,并使用相容的单位。

A* 是一种最佳优先搜索,因为它会扩展搜索前沿中评价值最优的状态,通常就是 ff 最小的状态。令 h(n)=0h(n)=0,就会去掉对搜索方向的引导,得到一致代价搜索;对于在找到目标时终止的单源最短路径问题,这与迪ijkstra算法基本对应。如果所有边的代价都相同且为正,这种无引导搜索就会像广度优先搜索一样,按相同的深度层次探索状态。如果改为仅按 hh 对状态排序,则得到贪心最佳优先搜索;它可能很快到达目标,但通常不能保证找到代价最低的路径。

状态描述必须包含确定后续转移及其代价所需的全部信息。对于在静态网格上移动的行人,仅有位置可能就足够了。对于转向受到约束的车辆,可能还需要记录位置和朝向;对于调度问题,可能需要记录已完成任务的集合以及当前可用的资源。即使启发式函数没有问题,将那些看似相似、但后续可能情况不同的状态合并,也可能导致搜索失效。

历史发展与理论背景

彼得·E. 哈特、尼尔斯·J. 尼尔松和伯特伦·拉斐尔在 1968 年发表的论文《启发式确定最小代价路径的形式化基础》中提出了 A*。这项工作源于斯坦福研究所(现为 SRI 国际研究所)对智能问题求解与机器人规划的研究,也是 Shakey 机器人项目理论背景的一部分。该项目将感知、符号描述、规划与实际动作联系在一起。

该算法融合了两种此前往往被分别研究的方法。最短路径方法提供了累加代价并证明结果最优的严谨手段;启发式搜索则利用问题领域的知识,避免考察那些不太可能得到理想结果的备选方案。A* 表明,只要对未来代价的估计满足适当的约束,就可以在不牺牲最小代价保证的前提下引导搜索。由此,启发式不再只是一种非形式化的偏好,其数学性质也成为正确性论证的一部分。

最初的研究还提出了一个比“A* 能否找到最优路径”更强的问题:在获得相同启发式信息的各类算法中,A* 展开的状态数是否最少。围绕这一主张的讨论延续到了 1972 年的一次修正及后续分析。里娜·德希特和朱迪亚·珀尔在 1985 年的研究阐明了一致性的重要性,以及笼统宣称最优效率的局限。仅凭启发式的可采纳性,并不足以毫无限制地断言 A* 始终只需进行最少量的搜索。

因此,三个不同的性质成为该理论的核心。完备性是指,在满足特定假设的情况下,只要解存在,就一定能找到解。最优性是指,返回的解具有最小代价。最优效率关注的是,相对于某个明确定义的其他算法类别,必须进行多少探索。这些性质回答的是不同的问题,不能仅凭算法的名称就推断它具备其中任何一种性质。

A* 也成为符号人工智能研究中有信息搜索的典型范例。其启发式往往是领域知识的一种精炼表达,例如几何界限、经过松弛的规划问题,或针对某种更简单的抽象模型建立的精确代价表。后续发展保留了通用搜索过程与领域专用估计之间的这种分离,同时着手应对内存限制、动态环境、有限计算资源和并行执行等问题。

搜索前沿管理与搜索过程

标准的图搜索实现维护一个开放集,其中包含已发现但尚待扩展的状态,以及一个封闭集,用于记录已扩展的状态。开放集通常采用优先队列实现,主要按 ff 值排序。此外,还使用额外的表来存储每个状态目前已发现的最佳 gg 值,以及用于重建最终路径的前驱指针。状态查找和重复检测通常使用哈希表。

初始时,起始状态满足 g(s)=0g(s)=0;其他状态尚无已知的有限代价。将起始状态加入搜索前沿。每次迭代取出优先级值最小的条目,检查该条目是否代表目前到达其对应状态的最佳路径,然后判断该状态是否为目标。如果不是目标,就检查从该状态出发的各个转移。对于 uu 的后继状态 vv,候选代价为

gcandidate=g(u)+c(u,v).g_{\mathrm{candidate}}=g(u)+c(u,v).

如果这一代价小于 vv 已记录的值,算法便更新其代价和前驱,并安排以新的优先级处理 vv。

以下伪代码允许队列中存在重复条目,因此不需要降低键值操作:

g[start] := 0
parent[start] := 无
将 (h(start), 0, start) 压入 OPEN

当 OPEN 非空时:
    (priority, saved_g, u) := 弹出优先级值最小的条目

    如果 saved_g != g[u]:
        继续下一次迭代

    如果 u 满足目标判定条件:
        返回 reconstruct_path(parent, u)

    对于每个代价为 c(u, v) 的转移 u -> v:
        candidate := g[u] + c(u, v)

        如果 v 尚无代价记录,或 candidate < g[v]:
            g[v] := candidate
            parent[v] := u
            将 (candidate + h(v), candidate, v) 压入 OPEN

返回失败

当某个状态的代价得到改善时,队列中的旧条目便会过期,在取出时将被忽略。这个版本允许状态在代价确实改善后再次扩展;对于一般的可采纳但不一致的启发式函数,这是必要的。如果启发式函数具有一致性,则可以改用显式的封闭集,在状态第一次被有效扩展时就将其永久确定下来。

目标判定应在从优先队列中取出条目时进行,而不能仅在发现状态时进行。例如,假设从起点出发的一条边以代价 10 到达目标,而另一条经过中间状态的路径以总代价 2 到达同一目标。发现那条代价为 10 的边,并不能证明它是最优的。搜索前沿的排序决定了算法何时具备足够的依据来终止搜索。

当 ff 值相同时,需要采用次级排序规则。优先选择 gg 较大的状态,等价于在 ff 相同的一组状态中优先选择 hh 较小的状态;这通常会使搜索朝目标推进,而不是沿着宽广的等代价轮廓展开。也可以采用其他同值决胜策略。这些策略可能显著改变运行时间和内存消耗,但不会改变基本的最优性保证。

可采纳启发式与一致启发式

当一个启发式函数从不高估真实的最小剩余代价时,就称它是可采纳的:

h(n)≤h∗(n).h(n)\leq h^*(n).

通常的定义还要求 h(n)≥0h(n)\geq 0,并且在每个目标 tt 处都有 h(t)=0h(t)=0。可采纳的启发值是一个下界,不一定是统计意义上准确的预测。即使某种估计总是低估剩余代价,只要它能区分有希望的状态与代价明显较高的状态,就仍然可能有用。

如果每次状态转移都满足以下条件,就称该启发式函数是一致的,也称单调的:

h(u)≤c(u,v)+h(v).h(u)\leq c(u,v)+h(v).

这是一个三角不等式条件:uu 处的估计值不能超过从 uu 到 vv 的代价与 vv 处估计值之和。如果目标处的启发值为零,那么对于能够到达目标的状态,一致性蕴含可采纳性。它还保证沿同一条搜索路径的 ff 值不会递减。可采纳的启发式函数不一定是一致的,因此这两个概念不能混用。

几何距离提供了几个常见的例子。在水平和竖直移动的代价均为 1 的四连通方格网格中,如果障碍物只是使某些移动不可行,那么曼哈顿距离

h(n)=∣xn−xt∣+∣yn−yt∣h(n)=|x_n-x_t|+|y_n-y_t|

就是可采纳且一致的。允许对角移动后,适用的下界也会改变:此时曼哈顿距离可能产生高估。当水平、竖直移动的代价为 1,对角移动的代价为 2\sqrt{2} 时,无障碍情况下的最短距离由八方向距离公式给出:

h(n)=max⁡(Δx,Δy)+(2−1)min⁡(Δx,Δy).h(n)=\max(\Delta x,\Delta y) +(\sqrt{2}-1)\min(\Delta x,\Delta y).

当各次状态转移的代价至少等于其对应的几何长度时,欧几里得距离也是一个有效的下界。

更复杂的启发式函数往往来自松弛:去掉某些约束,得到一个更容易求解的问题,其精确解的代价不会高于原问题。对于滑块拼图,将每个数字滑块的曼哈顿距离相加,就忽略了滑块之间的相互妨碍。模式数据库则更进一步,存储抽象问题的精确代价;这种抽象可以只考虑选定的一部分滑块的位置。随后通过查表,就能得到原拼图问题的一个代价下界。取多个可采纳启发式函数的最大值,可以安全地将它们组合起来。如果要将它们相加,则需要另行论证,例如对动作代价进行划分,以避免重复计算。

如果处处都有 h2(n)≥h1(n)h_2(n)\geq h_1(n),并且两者都可采纳,就称 h2h_2 支配 h1h_1。它提供的下界至少同样紧,但计算它的代价可能更高。因此,启发式函数的设计既要考虑所提供的信息量,也要考虑计算代价。通过机器学习得到的估计值并不会自动保持可采纳性;经验上的预测准确性与有保证的下界是两种不同的性质。

完备性、最优性与必要假设

通常的最优性论证依赖于一个下界不变式。设 C∗C^* 为最优解的代价。在找到该解之前,正确维护的搜索前沿中,总有一个位于最优路径上的状态,其记录的起点到该状态的代价就是最优前缀路径的代价。对于可采纳启发式,该状态满足

f(n)=g∗(n)+h(n)≤C∗.f(n)=g^*(n)+h(n)\leq C^*.

若到达目标时的代价更高,即 C>C∗C>C^*,则由于目标的启发值为零,其 f=Cf=C。因此,不可能在搜索前沿中所有取值不超过 C∗C^* 的状态之前选中该目标。这就是在目标从队列中取出时终止搜索的依据。

在树搜索中,到达同一底层状态的不同路径会作为独立的搜索节点保留。在图搜索中,这些节点会被合并,从而减少工作量,但也要求谨慎处理代价。使用一致启发式时,对一个状态的首次有效扩展就已经采用了其最优路径代价,因此将其永久关闭是安全的。使用不一致启发式时,代价更低的路径可能稍后才会出现。要维持一般情况下的最优性保证,就必须重新打开该状态,或以其他方式正确传播改进后的代价。

一个简单的例子可以说明这种区别。考虑以下边:s→as\to a 的代价为 3,s→bs\to b 的代价为 1,b→ab\to a 的代价为 1,a→ta\to t 的代价为 3。设 h(a)=0h(a)=0、h(b)=4h(b)=4、h(t)=0h(t)=0。这些启发值是可采纳的,但边 b→ab\to a 违反了一致性,因为 4>1+04>1+0。A* 首先以代价 3 扩展 aa,随后经由 bb 发现,到达 aa 的代价可以降至 2。如果始终不重新打开 aa,也不传播这一改进,搜索就可能返回代价为 6 的路径,而不是代价为 5 的最优路径。

完备性还要求关注搜索空间的大小及其中的代价。在有限图上,采用通常的非负代价假设、正确处理重复状态,并且只在代价严格降低时进行更新,就能直接论证算法会终止。对于无限但分支数有限的搜索空间,一个标准的充分条件是:每条边的代价都不低于某个 ε>0\varepsilon>0。这可以避免出现无限多条深度不断增加、代价却始终低于某个有限解代价上界的路径。零代价转移或趋近于零的正代价都可能使这一论证失效。

负权边不在标准假设的范围内,可能使有关终止性和最优性的推理失效。贝尔曼–福特算法等算法适用于不同的最短路径条件。最后,最优性是相对于给定的图和优化目标而言的:网格中的最短路径不一定是物理上可实现的最短轨迹,而距离最短的路线也不一定耗时最少。

计算开销与扩展行为

A* 可以大幅减少探索量,但并不能消除困难问题固有的计算复杂性。在分支因子为 bb、解深度为 dd 的隐式状态空间中,生成的状态数量仍可能随深度呈指数增长。具体表现取决于边的代价、重复状态、启发式误差以及搜索空间的几何结构。“A* 的复杂度是指数级的”这样的说法描述的是一种重要的最坏情况风险,并不意味着它在所有图上都有固定的运行时间。

对于有限的显式图,如果启发式函数具有一致性,状态在扩展后就不必重新打开。采用邻接表,并用合适的二叉堆维护搜索前沿时,一个标准的复杂度上界是 O((∣V∣+∣E∣)log⁡∣V∣)O((|V|+|E|)\log |V|),与 Dijkstra 算法的一种常见实现相当。这个上界是以给定图的规模来衡量开销的。然而,在规划和解谜问题中,这个图的规模可能比描述它的紧凑输入大出指数级。如果启发式函数不具有一致性,反复改进路径代价和重新扩展状态,就可能带来远超逐一扫描各状态出边所需的额外工作量。

启发式函数的质量可以通过代价等值线来理解。在采用一致启发式函数的标准完备搜索中,最优前缀路径对应的估值 g∗(n)+h(n)g^*(n)+h(n) 严格小于 C∗C^* 的可达状态,都必须在选中最优目标之前得到处理。对于位于边界 g∗(n)+h(n)=C∗g^*(n)+h(n)=C^* 上的状态,是否扩展取决于平局处理策略。较弱的启发式函数会让许多状态落在该边界以下。较强的启发式函数则会提高无关备选路径的代价下界,缩小需要探索的区域。

即便是完美的启发式函数,也无法消除所有实际问题。如果大量最优路径或零代价转移形成了一个庞大的等 ff 值平台区域,平局处理策略仍可能导致大量探索。另一方面,计算信息量很高的启发式函数所需的开销,也可能超过它通过减少扩展所节省的开销。因此,有意义的性能测量应区分生成的状态数、扩展的状态数、启发式函数求值次数、队列操作次数、运行耗时和峰值内存占用。

内存往往是决定性的限制因素。A* 通常会保留搜索前沿条目、已发现状态的代价以及前驱信息。其空间复杂度与存储的搜索记录数量成正比,即使单次转移的代价很低,这些记录也可能极其庞大。一种称为“有效分支因子”的经验指标,通过为如下关系拟合一个 b∗b^* 值,来概括扩展行为:

N≈1+b∗+(b∗)2+⋯+(b∗)d.N\approx 1+b^*+(b^*)^2+\cdots+(b^*)^d.

这只是对某次具体实验的比较性描述,既不是该算法的通用常数,也不能替代时间复杂度分析。

内存受限、加权与增量变体

迭代加深 A*(简称 IDA*)不再存储搜索前沿,而是反复执行以 ff 阈值为界的深度优先遍历。初始阈值通常为 h(s)h(s)。如果一次遍历未找到解,就将超过上一轮界限的最小值作为下一轮阈值。理查德·科尔夫于 1985 年提出了这一方法。它的主要优点是内存占用低:在基本的树搜索形式中,内存用量大致与当前路径的长度成正比。其主要代价是重复探索,尤其是在出现许多不同阈值,或经由不同路径到达同一状态的情况很常见时。

其他内存受限的方法会有选择地保留部分搜索信息。递归最佳优先搜索保留一个规模受限的递归搜索结构,并在放弃某个分支时将估计代价回传。简化内存受限 A* 通常缩写为 SMA*,它使用固定的内存预算,丢弃前景较差的叶节点,同时保留回传的信息,以便日后重新生成被遗忘的搜索区域。这些方法能提供何种保证,取决于具体流程和可用内存;它们并不只是队列容量更小的普通 A*。

加权 A* 将评估函数改为

fw(n)=g(n)+w h(n),w>1.f_w(n)=g(n)+w\,h(n),\qquad w>1.

提高启发式项的权重会使搜索更倾向于朝目标推进,但通常会牺牲严格的最优性。如果基础启发式具有可采纳性、代价非负、目标处的启发值为零,且算法版本能够正确处理路径改进和节点重新开放,那么在选中目标并终止时,可得到标准界限

C≤wC∗.C\leq wC^*.

这是因为,最优路径上的某个前沿状态,其加权优先级值至多为 wC∗wC^*,而目标的优先级值等于其路径代价。采用不同重复状态处理策略的实现,需要单独分析,不能自动沿用这一界限。

随时搜索利用额外的计算来改进初始解。随时修复 A*(通常称为 ARA*)从放大的启发值开始,在复用搜索信息的同时逐步减小放大系数。由此得到一系列解,并在算法假设成立的条件下,为这些解提供相应的界限。当应用需要迅速获得可行解,但在执行前或其他工作继续进行期间仍可通过改进解而受益时,这种方法就很有用。

增量算法用于处理一系列相关问题之间的变化。终身规划 A* 在边代价发生修改时保留并维护搜索信息,而 D* Lite 则将相关原理用于反复导航和重新规划。如果机器人发现某条通道被阻断,这些方法可以修复先前搜索中受影响的部分,而不必从头求解整个问题。它们需要额外的状态和更新规则;若在未经修改的 A* 运行过程中直接改变图,算法原有的保证便不再成立。

应用与状态空间表示

在导航中,A* 通常在栅格、路点图或导航网格中进行搜索。栅格单元便于表示障碍物,但其分辨率同时决定计算开销和几何精度。精细的栅格能更准确地表示狭窄通道,但也会增加状态数量。导航网格则表示可通行区域及其连接关系。在得到图上的路径后,可能还需要单独的几何处理步骤,才能生成穿过这些区域的平滑路线。

在机器人运动规划中,状态建模问题尤为重要。轮式车辆未必能沿着任意无碰撞的位置序列行驶,因为它可能受到最小转弯半径或倒车限制的约束。搜索格可以编码位置、朝向和可行的运动基元。混合 A* 将离散化的状态索引与连续运动推演相结合。这类规划器可以采用基于几何信息或考虑障碍物的下界,但其最优性声明必须结合所用的表示方式和算法细节来理解,不能直接视为连续物理空间中的全局最优性。

滑块拼图提供了一个清晰的组合问题场景。在十五数码问题中,每个状态指定 4×44\times4 棋盘上 15 个编号方块和一个空格的排列;状态转移通过将一个方块移入空格来实现。A* 可以利用曼哈顿距离或更强的模式数据库估计来搜索移动次数最少的解。庞大的可能配置数量也说明,理论上有效的启发式并不能消除内存限制,同时也解释了为什么 IDA* 在求解拼图的最优解时一直十分重要。

在自动规划中,状态可以是一组命题,而状态转移则是一个具有前提条件、效果和代价的动作。图并非预先给定,而是按需生成。这使 A* 与知识表示与推理联系起来:表示方式决定哪些动作是可能的,而松弛后的规划问题则可以提供启发式。例如,忽略动作之间某些负面相互作用,可以降低规划难度并得到一个下界,前提是松弛方式和代价计算方法构造得当。

当部分解构成一个图,并且能够获得完成解所需代价的有效下界时,A* 也可用于序列比较、句法分析和结构化解码。在概率序列问题中,取负对数可以将概率的乘积转化为可加的代价。此时,启发式必须在正确的方向上给出剩余得分的界。更一般地说,A* 最小化的是单一的标量可加目标。对于涉及行程时间、能耗和风险等多个相互竞争目标的问题,需要明确一种将各目标权衡为标量的方式,或者采用为每个状态保留多个非支配标签的多目标搜索方法。

实现的正确性与实际局限

正确的状态表示必须支持可靠的相等性判断和哈希计算。两条记录如果表示相同的后续决策情境,即使它们是经由不同历史路径到达的,通常也应视为同一个状态。反之,如果历史信息会改变后续的可能选择,就不能简单地将其丢弃。在资源受限的路线规划问题中,到达同一地点时剩余燃料不同,可能意味着它们确实是不同的状态。如果重复状态检测忽略了燃料,就可能排除唯一的可行解。

优先队列的更新也是常见的错误来源。有些队列支持降低键值操作;另一些队列则采用插入新条目、稍后丢弃过期条目的方式更为简便。无论选择哪种方式,队列优先级、记录的 gg 值、前驱以及重新开放策略都必须保持一致。针对快速查找进行优化的数据结构,本身并不能保证代价的改进得到正确传播。重复条目还可能使队列的内存占用远大于不同状态的数量。

数值表示既影响算法的行为,也影响其保证。当目标值天然为整数时,使用整数代价可以避免舍入问题,但加法运算不得溢出;整数溢出可能使一条代价高昂的路线看起来异常便宜。使用浮点数代价时,需要谨慎处理相等性判断、数值比较和累计误差。为“相等”的代价引入容差,在实际运行中可能很有用,但这会改变哪些改进会被接受,因此必须确保它与任何精确最优性的声明相容。数据错误导致的负代价或非有限代价,可能使搜索所依赖的假设不再成立。

启发式估计所用的单位同样需要重视。将已行进距离与估计剩余时间相加,在最短路径问题中没有一致的意义。对于最短时间问题,用直线距离除以一个有充分依据的可达速度上界,可以得到时间下界。除以平均速度通常不能得到这样的下界。同样,在 hh 中加入障碍物惩罚或学习得到的偏好,或许能有效引导搜索,但除非有下界论证作为支撑,否则就可能破坏可采纳性。

测试时,可以在小规模实例上将 A* 与 Dijkstra 算法进行比较,因为这类实例的最优代价很容易通过独立方法算出。有价值的测试情形包括:初始状态已经是目标、目标不可达、存在多条最优路径、存在零代价边、启发式不一致,以及某些状态在先前已被扩展之后代价又得到改进。局部一致性检查可以在生成的边上检验 h(u)≤c(u,v)+h(v)h(u)\leq c(u,v)+h(v);可采纳性则需要通过与精确的剩余代价比较,或通过单独的证明来确认。对于安全关键系统,形式验证可以明确图的相关假设和更新过程中的不变式。对于内存耗尽或扩展次数达到上限等运行限制,必须区分搜索尚未完成与已经证明无解这两种情况。