A* 寻路算法源码实战：swift-algorithm-club 中的启发式最佳优先搜索实现详解

A* 寻路算法源码实战swift-algorithm-club 中的启发式最佳优先搜索实现详解【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-clubA*读作 ay star是一种借助启发式函数heuristic function驱动的最佳优先搜索算法它通过优先扩展最有希望的节点来大幅减少搜索规模、缩短寻路时间。本文以 swift-algorithm-club 仓库 A-Star/README.md 为主体结合 A-Star/AStar.swift、A-Star/Tests/AStarTests.swift 与 Hashed Heap/HashedHeap.swift 的源码从算法原理、图解示例到 Swift 实现与测试完整拆解 A* 的运作机制。读完本文你将理解g h估值公式、可采纳启发式admissible heuristic与最优性的关系并掌握如何在自定义图结构上直接使用仓库中的AStar泛型类求解最短路径。A* 是什么启发式最佳优先搜索A* 是一种启发式最佳优先搜索heuristic best-first search算法。普通的最佳优先搜索只依据当前代价选择扩展节点而 A* 额外引入一个启发式函数用来估计两个顶点之间的剩余距离从而看得更远。启发式函数的典型例子如果你要在城市中寻找两点之间的路径可以用直线距离来估计真实的街道距离。虽然直线距离不一定可通行但它永远是实际行驶距离的下限这恰恰是 A* 需要的关键性质。A* 的核心工作方式是总是优先扩展启发式函数认为最有希望的节点。仍以城市寻路为例它会优先选择大致朝向目标方向的街道只有当这些街道是死胡同时才会回溯尝试其他街道。这种先朝目标冲撞墙再回头的策略使 A* 在大多数场景下都能显著加速搜索。最优性条件可采纳启发式A* 之所以广受欢迎是因为它在满足特定条件时保证找到最短路径最优可采纳admissible启发式启发式函数永远不高估到达目标的实际代价。在极端情况下如果启发式函数恒返回0A* 的行为就与 Dijkstra 算法 完全一致——不再有任何方向性指引退化为纯粹的代价优先搜索。启发式函数的估计值越接近真实距离搜索收敛得越快估计越粗糙需要扩展的节点就越多。这一条件在源码中也有明确体现。A-Star/AStar.swift 中heuristic属性的文档注释写道The heuristic function needs to always return a value that is lower-than or equal to the actual cost for the resulting path of the A* search to be optimal.即只有启发式函数恒返回不超过实际代价的估计值A的结果才是最优的*。这与 README 中的论述完全一致也是使用该实现时必须牢记的约束。图解示例七步走完一次完整搜索下面用仓库 A-Star/Images/graph.png 中的简单有向图跑一遍完整流程。图例约定所有边代价均为 1启发式函数取节点到目标列之间的列差图中每个节点标注的h值。原始图结构与 A-Star/Images/graph.dot 一致起点Ah 3有三条出边分别指向B、C、D三者h 2B → Eh 1E → Fh 1D → Gh 1G → Hh 0绿色目标节点C没有任何出边死胡同分支。第一步扩展根节点 A我们扩展最左侧的根节点A蓝色将实际代价g置为0并把它的所有邻居B、C、D加入open 列表灰色每个邻居的g均为0 1 1。第二步把 A 放入 closed 列表选择估值最小的节点将A放入closed 列表浅蓝色这样即使图中存在环路也不会再次扩展它。接着从 open 列表中取出g h值最小的节点Bg h 1 2 3Cg h 1 2 3Dg h 1 2 3三者估值相同按约定选择最上面的节点B进行扩展。B的邻居E以g 2加入 open 列表。第三步重复流程无新节点可加继续从 open 列表中取估值最小的节点C并扩展。由于C没有任何出边本轮没有新节点加入 open 列表。第四步再扩展一个节点扩展下一个节点D新节点Gg 2, h 1加入 open 列表。至此 open 列表中有E2 1 3与G2 1 3。第五步估值相同选择上方节点由于最上方的E与最下方的G拥有相同的估值3我们选择最上方的E。从 A-Star/Images/step5.dot 可以看出E扩展后F以g 3, h 1加入 open 列表估值为4。这一步的选择并不算理想——如果能有一个更好的启发式函数本可以避免这个次优分支。第六步扩展估值更小的下方节点现在 open 列表中Fg h 3 1 4Gg h 2 1 3因为2 1 3 1我们扩展下方的G目标节点H以g 3, h 0加入 open 列表。第七步到达目标open 列表中H的估值为3 0 3小于F的4因此扩展H——它正是目标节点搜索结束。注意中间的F节点从未被扩展它的估值4大于最优解总代价3A → D → G → H共 3 步因此可以保证它不属于最优解无需再探索。最后一步回溯构建最优路径搜索完成后从目标节点H出发沿父节点指针逐级回溯H → G → D → A反转后得到最优路径A → D → G → H。源码解析泛型协议设计与核心实现理解了算法流程后我们来看仓库中完整的 Swift 实现。A-Star/AStar.swift 的设计非常干净通过两个协议将算法与具体图结构解耦。Graph 与 WeightedEdge 协议public protocol Graph { associatedtype Vertex: Hashable associatedtype Edge: WeightedEdge where Edge.Vertex Vertex /// Lists all edges going out from a vertex. func edgesOutgoing(from vertex: Vertex) - [Edge] } public protocol WeightedEdge { associatedtype Vertex /// The edges cost. var cost: Double { get } /// The target vertex. var target: Vertex { get } }要点Graph只要求实现一个方法edgesOutgoing(from:)用于列出从某顶点出发的所有出边顶点必须可哈希Hashable以便放入集合与字典WeightedEdge暴露边的代价cost与目标顶点target使用关联类型associatedtype而非泛型参数让任何遵循这两个协议的类型都能无缝接入AStar。AStar 类的数据结构public final class AStarG: Graph { public let graph: G public let heuristic: (G.Vertex, G.Vertex) - Double private var open: HashedHeapNodeG.Vertex // 待扩展节点最小堆 private var closed SetG.Vertex() // 已扩展顶点 private var costs DictionaryG.Vertex, Double() // 实际代价 g private var parents DictionaryG.Vertex, G.Vertex() // 父指针用于回溯路径 }四个核心数据结构与算法描述一一对应数据结构对应概念作用openHashedHeap最小堆open 列表按g h排序快速取出估值最小的节点closedSetclosed 列表记录已扩展顶点防止环路导致重复扩展costsDictionary实际代价g记录已确定的最短实际代价parentsDictionary父指针回溯重建最优路径path(start:target:) 主流程public func path(start: G.Vertex, target: G.Vertex) - [G.Vertex] { open.insert(NodeG.Vertex(vertex: start, cost: 0, estimate: heuristic(start, target))) while !open.isEmpty { guard let node open.remove() else { break } costs[node.vertex] node.cost if (node.vertex target) { let path buildPath(start: start, target: target) cleanup() return path } if !closed.contains(node.vertex) { expand(node: node, target: target) closed.insert(node.vertex) } } return [] // 无路径可达时返回空数组 }可见 A-Star/AStar.swift 的流程与图解示例完全吻合起点以cost 0、estimate heuristic(start, target)入堆循环内反复弹出估值最小的节点命中目标立即回溯路径未找到路径时返回空数组。cleanup()在结束时清空所有状态同一个AStar实例可以重复用于多次查询。节点估值与扩展逻辑Node的比较规则是整个算法的核心——它直接决定 open 列表的排序依据private struct NodeV: Hashable: Hashable, Comparable { var vertex: V var cost: Double // 起点到该节点的实际代价 g var estimate: Double // 该节点到目标的启发式估计 h static func (lhs: NodeV, rhs: NodeV) - Bool { return lhs.cost lhs.estimate rhs.cost rhs.estimate } static func (lhs: NodeV, rhs: NodeV) - Bool { return lhs.vertex rhs.vertex } }这里lhs.cost lhs.estimate rhs.cost rhs.estimate就是g h的估值公式见 A-Star/AStar.swift。注意仅比较顶点本身这使得 open 列表能以顶点为单位查重、去重。扩展节点的expand(node:target:)逻辑private func expand(node: NodeG.Vertex, target: G.Vertex) { let edges graph.edgesOutgoing(from: node.vertex) for edge in edges { let g cost(node.vertex) edge.cost if g cost(edge.target) { open.insert(NodeG.Vertex(vertex: edge.target, cost: g, estimate: heuristic(edge.target, target))) parents[edge.target] node.vertex } } }这是一个经典的**松弛relaxation**操作只有发现一条比已知更优的路径新 g 已记录 g时才把节点重新插入 open 列表并更新父指针。cost(_:)方法会依次查询costs字典与 open 堆中的记录未发现时返回Double.greatestFiniteMagnitude无穷大保证首次到达的节点必然满足松弛条件。数据结构选型为什么用 HashedHeapopen 列表需要支持两类高频操作取出估值最小的节点、按顶点查找其当前代价。仓库选用的是 Hashed Heap/HashedHeap.swift 中实现的哈希堆——普通二叉堆外加一层元素 → 数组下标的哈希索引。其文档注释明确写道A heap keeps elements ordered in a binary tree without the use of pointers. A hashed heap does that as well as having amortized constant lookups by value. This is used in the A* and other heuristic search algorithms to achieve optimal performance.关键操作复杂度均来自源码注释操作复杂度说明insert(_:)O(log n)插入后上浮维护堆性质remove()O(log n)弹出堆顶估值最小节点后下沉修复index(of:)摊销 O(1)借助哈希索引普通堆需 O(n)在AStar初始化时堆以HashedHeap(sort: )构建为最小堆A-Star/AStar.swift堆顶即g h最小的节点cost(_:)中正是通过open.index(of: node)以摊销常数时间定位节点并读取其代价Hashed Heap/HashedHeap.swift。这套组合让 A* 在频繁弹最小值 频繁按值查重的负载下保持高效。实战在网格图上使用 A*仓库的测试文件 A-Star/Tests/AStarTests.swift 给出了一个可以直接照搬的实战范式定义四邻接网格图配合曼哈顿距离启发式求解路径。定义图四邻接网格struct GridGraph: Graph { struct Vertex: Hashable { var x: Int var y: Int static func (lhs: Vertex, rhs: Vertex) - Bool { return lhs.x rhs.x lhs.y rhs.y } public var hashValue: Int { return x.hashValue ^ y.hashValue } } struct Edge: WeightedEdge { var cost: Double var target: Vertex } func edgesOutgoing(from vertex: Vertex) - [Edge] { return [ Edge(cost: 1, target: Vertex(x: vertex.x - 1, y: vertex.y)), Edge(cost: 1, target: Vertex(x: vertex.x 1, y: vertex.y)), Edge(cost: 1, target: Vertex(x: vertex.x, y: vertex.y - 1)), Edge(cost: 1, target: Vertex(x: vertex.x, y: vertex.y 1)), ] } }GridGraph用整数坐标(x, y)表示顶点edgesOutgoing返回上下左右四个邻居每条边代价为1——这是网格寻路最典型也是最简单的建模方式。定义启发式曼哈顿距离func manhattanDistance(_ s: GridGraph.Vertex, _ t: GridGraph.Vertex) - Double { return Double(abs(s.x - t.x) abs(s.y - t.y)) }曼哈顿距离|x1 - x2| |y1 - y2|在四邻接网格中永远不会高估实际步数因此是满足可采纳条件、保证 A* 最优的经典启发式。求解路径let graph GridGraph() let astar AStar(graph: graph, heuristic: manhattanDistance) let path astar.path( start: GridGraph.Vertex(x: 0, y: 0), target: GridGraph.Vertex(x: 10, y: 10) ) // path.count 21共 21 个节点含起点与终点测试testDiagonal验证了从(0, 0)到(10, 10)的对角线寻路返回 21 个节点0 10 * 2 1 21步的阶梯路径且首尾坐标正确testSameStartAndEnd则验证起点等于终点时返回仅含单个节点的路径。这两个用例覆盖了 A* 的边界情况可作为自定义图结构的回归测试模板。小结A* 的适用前提与使用要点回顾整篇A* 的威力来自启发式引导 代价松弛 堆结构三者的配合使用时需把握以下几点启发式必须可采纳估计值永远不超过真实代价这是 A* 最优性的前提启发式越贴近真实距离搜索越快极端情况h ≡ 0时退化为 Dijkstra 算法图结构只需实现Graph协议提供edgesOutgoing(from:)即可顶点需满足Hashable边需提供cost与targetopen 列表用最小堆仓库以HashedHeap实现g h最小者优先扩展索引查找摊销 O(1)路径重建依赖父指针命中目标后沿parents回溯并反转不可达时path(start:target:)返回空数组实例可复用每次搜索结束会cleanup()清空内部状态。无论是最短路径规划、游戏 AI 寻路还是需要在巨大状态空间中快速找到可行解的各类搜索问题理解了本文的g h估值、可采纳启发式与七步图解流程之后你都可以直接复用仓库中的 A-Star/AStar.swift 泛型实现并在 A-Star/Tests/AStarTests.swift 的基础上扩展自己的图与启发式函数。【免费下载链接】swift-algorithm-clubAlgorithms and data structures in Swift, with explanations!项目地址: https://gitcode.com/gh_mirrors/sw/swift-algorithm-club创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考