双向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 是 \(\infty\)

  • 当 \(v = u\) 没有路径，因此

    • 没有返回对应的行

    • 从 v 到 u 的 agg_cost 是 \(0\)

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

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

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

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

  • 预计终止速度比 pgr_astar 更快

查看可用的 heuristics 和 factor 处理。

另请参阅

• A* - 函数族

• https://www.boost.org/libs/graph/doc/astar_search.html

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

索引和表格

• Index

• Search Page