pgr_bdAstarCost¶

pgr_bdAstarCost - Total cost of the shortest path using the bidirectional A* algorithm.

可用性

版本3.2.0
- 新拟议的签名：
  - pgr_bdAstarCost (组合)
版本3.0.0
- 官方函数
版本2.4.0
- 新拟议函数

描述¶

The pgr_bdAstarCost function sumarizes of the cost of the shortest path using the bidirectional A* algorithm.

主要特点是：

流程适用于有向图和无向图。
顺序是：
- 首先按 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)\)

它不返回路径。
返回所请求的每对节点组合的最短路径的成本总和。
假设返回的值存储在表中，因此唯一索引将是一对：(start_vid, end_vid)
对于无向图，结果是对称的。
- (u, v) 的 agg_cost 与 (v, u) 相同。
返回值按升序排列：
- start_vid 升序
- end_vid 升序

签名¶

总结

pgr_bdAstarCost(Edges SQL, start vid, end vid, [options])
pgr_bdAstarCost(Edges SQL, start vid, end vids, [options])
pgr_bdAstarCost(Edges SQL, start vids, end vid, [options])
pgr_bdAstarCost(Edges SQL, start vids, end vids, [options])
pgr_bdAstarCost(Edges SQL, Combinations SQL, [options])
options: [directed, heuristic, factor, epsilon]

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

一对一¶

pgr_bdAstarCost(Edges SQL, start vid, end vid, [options])

options: [directed, heuristic, factor, epsilon]

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:: 在具有heuristic \(2\) 的有向图上，从顶点 \(6\) 到顶点 \(12\)

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  6, 12,
  directed => true, heuristic => 2
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      12 |        3
(1 row)

一对多¶

pgr_bdAstarCost(Edges SQL, start vid, end vids, [options])

options: [directed, heuristic, factor, epsilon]

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:: 在具有heuristic \(3\) 和factor \(3.5\) 的有向图上，从顶点 \(6\) 到顶点 \(\{10, 12\}\)

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  6, ARRAY[10, 12],
  heuristic => 3, factor := 3.5
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      10 |        5
         6 |      12 |        3
(2 rows)

多对一¶

pgr_bdAstarCost(Edges SQL, start vids, end vid, [options])

options: [directed, heuristic, factor, epsilon]

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:: 在具有heuristic \(4\) 的无向图上，从顶点 \(\{6, 8\}\) 到顶点 \(10\)

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[6, 8], 10,
  false, heuristic => 4
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      10 |        1
         8 |      10 |        3
(2 rows)

多对多¶

pgr_bdAstarCost(Edges SQL, start vids, end vids, [options])

options: [directed, heuristic, factor, epsilon]

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:: 在具有factor \(0.5\) 的有向图上，从顶点 \(\{6, 8\}\) 到顶点 \(\{10, 12\}\)

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[6, 8], ARRAY[10, 12],
  factor => 0.5
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |      10 |        5
         6 |      12 |        3
         8 |      10 |        5
         8 |      12 |        1
(4 rows)

组合¶

pgr_bdAstarCost(Edges SQL, Combinations SQL, [options])

options: [directed, heuristic, factor, epsilon]

返回 (start_vid, end_vid, agg_cost) 的集合

OR EMPTY SET

示例:: 在有向图上使用组合表，且使用factor \(0.5\)。

组合表：

SELECT * FROM combinations;
 source | target
--------+--------
      5 |      6
      5 |     10
      6 |      5
      6 |     15
      6 |     14
(5 rows)

查询：

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  'SELECT * FROM combinations',
  factor => 0.5
);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         5 |       6 |        1
         5 |      10 |        6
         6 |       5 |        1
         6 |      15 |        4
(4 rows)

参数¶

列	类型	描述
Edges SQL	`TEXT`	Edges SQL 如下所述
Combinations SQL	`TEXT`	Combinations SQL 如下所述
start vid	`BIGINT`	路径起始顶点的标识符。
start vids	`ARRAY[BIGINT]`	起始顶点的标识符数组。
end vid	`BIGINT`	路径结束顶点的标识符。
end vids	`ARRAY[BIGINT]`	结束顶点的标识符数组。

可选参数¶

列	类型	默认	描述
`directed`	`BOOLEAN`	`true`	当 `true` 时，该图被视为有有向如果为 `false` ，则该图被视为无向。

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\)。

参数

类型

默认

描述

heuristic

INTEGER

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 处理。

内部查询¶

Edges SQL¶

参数	类型	默认	描述
`id`	ANY-INTEGER		边的标识符。
`source`	ANY-INTEGER		边的第一个端点顶点的标识符。
`target`	ANY-INTEGER		边的第二个端点顶点的标识符。
`cost`	ANY-NUMERICAL		边(`source`, `target`)的权重当为负时：边（`source`, `target`）不存在，因此它不是图的一部分。
`reverse_cost`	ANY-NUMERICAL	-1	边 (`target`, `source`)的权重，当为负时：边（ `target`, `source` ）不存在，因此它不是图的一部分。
`x1`	ANY-NUMERICAL		`source` 顶点的X坐标。
`y1`	ANY-NUMERICAL		`source` 顶点的Y坐标。
`x2`	ANY-NUMERICAL		`target` 顶点的X坐标。
`y2`	ANY-NUMERICAL		`target` 顶点的Y坐标。

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT
ANY-NUMERICAL:: SMALLINT, INTEGER, BIGINT, REAL, FLOAT

分量 SQL¶

参数	类型	描述
`source`	ANY-INTEGER	出发顶点的标识符。
`target`	ANY-INTEGER	到达顶点的标识符。

其中：

ANY-INTEGER:: SMALLINT, INTEGER, BIGINT

结果列¶

(start_vid, end_vid, agg_cost) 的集合

列	类型	描述
`start_vid`	`BIGINT`	起始顶点的标识符。
`end_vid`	`BIGINT`	结束顶点的标识符。
`agg_cost`	`FLOAT`	从 `start_vid` 到 `end_vid` 的总成本。

其他示例¶

示例1:: 演示中重复的值被忽略，且结果被排序。

 SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[7, 10, 15, 10, 10, 15], ARRAY[10, 7, 10, 15]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         7 |      10 |        4
         7 |      15 |        3
        10 |       7 |        2
        10 |      15 |        3
        15 |       7 |        3
        15 |      10 |        1
(6 rows)

示例2:: 使 start vids 与 end vids 相同。

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
 start_vid | end_vid | agg_cost
-----------+---------+----------
         7 |      10 |        4
         7 |      15 |        3
        10 |       7 |        2
        10 |      15 |        3
        15 |       7 |        3
        15 |      10 |        1
(6 rows)

示例3:: 手动指定的顶点组合。

SELECT * FROM pgr_bdAstarCost(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edges',
  'SELECT * FROM (VALUES (6, 10), (6, 7), (12, 10)) AS combinations (source, target)');
 start_vid | end_vid | agg_cost
-----------+---------+----------
         6 |       7 |        1
         6 |      10 |        5
        12 |      10 |        4
(3 rows)

另请参阅¶

索引和表格