A* - 函数族

A*（发音为“A星”）算法基于 Dijkstra 算法，其启发式算法使其能够通过仅评估整个图的子集来解决大多数最短路径问题。

• pgr_aStar - A* 最短路径算法。

• pgr_aStarCost - 获取最短路径的总成本。

• pgr_aStarCostMatrix - 获取最短路径的成本矩阵。

描述

主要特点是：

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

• 顺序是：

  • 首先按 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)\)

aStar 可选参数

参数	类型	默认	描述
heuristic	INTEGER	5	Heuristic 数字。当前有效值0~5。 0: \(h(v) = 0\) (使用该值与 pgr_dijkstra 进行比较) 1: \(h(v) = abs(max(\Delta x, \Delta y))\) 2: \(h(v) = abs(min(\Delta x, \Delta y))\) 3: \(h(v) = \Delta x * \Delta x + \Delta y * \Delta y\) 4: \(h(v) = sqrt(\Delta x * \Delta x + \Delta y * \Delta y)\) 5: \(h(v) = abs(\Delta x) + abs(\Delta y)\)
factor	FLOAT	1	对于单位操作。 \(factor > 0\)。
epsilon	FLOAT	1	对于限制较少的结果。 \(epsilon >= 1\)。

查看可用的 heuristics 和 factor 处理。

高级文档

Heuristic

目前可用的heuristic函数有：

• 0: \(h(v) = 0\) (使用该值与 pgr_dijkstra 进行比较)

• 1: \(h(v) = abs(max(\Delta x, \Delta y))\)

• 2: \(h(v) = abs(min(\Delta x, \Delta y))\)

• 3: \(h(v) = \Delta x * \Delta x + \Delta y * \Delta y\)

• 4: \(h(v) = sqrt(\Delta x * \Delta x + \Delta y * \Delta y)\)

• 5: \(h(v) = abs(\Delta x) + abs(\Delta y)\)

其中 \(\Delta x = x_1 - x_0\) 和 \(\Delta y = y_1 - y_0\)

因素

分析1

使用 cost/reverse_cost 作为长度（以度为单位），x/y 以纬度/经度为单位：因子 = 1（无需更改单位）

分析2

使用 cost/reverse_cost 作为以米为单位的长度，以纬度/经度为单位的 x/y： Factor = 将取决于点的位置：

纬度	转换	因素
45	1 经度为 78846.81 米	78846
0	1经度为111319.46 m	111319

分析3

使用 cost/reverse_cost 作为以秒为单位的时间，以 lat/lon 为单位的 x/y： 因子：取决于点的位置和平均速度，例如 25m/s 是速度。

纬度	转换	因素
45	1经度为(78846.81m)/(25m/s)	3153 s
0	1经度为(111319.46 m)/(25m/s)	4452 s

另请参阅

• 双向A* - 函数族

• Boost: A* search

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

索引和表格

• Index

• Search Page