Supported versions: latest (3.8) 3.7 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
Unsupported versions:2.6 2.5

双向A* - 函数族

双向A*（发音为"A星"）算法基于A*算法。

• pgr_bdAstar - 获取路径的双向A*算法。

• pgr_bdAstarCost - 双向 A* 算法计算路径成本。

• pgr_bdAstarCostMatrix - 用于计算路径成本矩阵的双向 A* 算法。

描述

基于A*算法，双向搜索找到从起始顶点(start_vid)到结束顶点(end_vid)的最短路径。 它同时运行两项搜索：一项从 start_vid 向前搜索，一项从 end_vid 向后搜索，当两者在中间相遇时停止。 该实现可以与有向图和无向图一起使用。

主要特点是：

• 流程适用于有向图和无向图。

• 顺序是：

  • 首先按 start_vid （如果存在）

  • 然后按 end_vid

• 当存在路径时返回值。

• 设 $v$ 和 $u$ 为图上的节点：

  • 如果没有从 $v$ 到 $u$ 的路径：

    • 没有返回对应的行

    • 从 $v$ 到 $u$ 的 agg_cost 是 $\mathrm{\infty }$

  • 当 $v=u$ 没有路径，因此

    • 没有返回对应的行

    • 从 v 到 u 的 agg_cost 是 $0$

• 当同一顶点标识符的 $(x,y)$ 坐标不同时：

  • 使用随机选择的顶点的 $(x,y)$ 坐标。

• 运行时间： $O((E+V)\ast \log V)$

• 对于起始顶点和结束顶点之间存在路径的大型图:

  • 预计其执行速度将快于 pgr_aStar 函数

查看可用的 heuristics 和 factor 处理。

另请参阅

• A* - 函数族

• Boost: A* search

• https://en.wikipedia.org/wiki/A*_search_algorithm

索引和表格

• Index

• Search Page