pgr_astar - Camino más corto A*¶
Nombre¶
pgr_astar — Regresa el camino más corto usando el algoritmo A*.
Sinopsis¶
El algoritmo A* (pronunciado “A Star”) se basa en el algoritmo de Dijkstra con una heurística que evalua sólo un subconjunto de la gráfica general, permiténdole resolver la mayoría de los problemas del camino más corto. Devuelve un conjunto de registros pgr_costResult (seq, id1, id2, cost) que conforman un camino.
pgr_costResult[] pgr_astar(sql text, source integer, target integer,
directed boolean, has_rcost boolean);
Descripción¶
sql: | Consulta SQL, que debe proporcionar un conjunto de registros con los siguientes campos: SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table
|
||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
source: | int4 identificador del punto de partida del recorrido |
||||||||||||||||||
target: | int4 identificador del punto de llegada del recorrido |
||||||||||||||||||
directed: | true Si la gráfica es direccionada |
||||||||||||||||||
has_rcost: | Si es True, el campo reverse_cost del conjunto de registros generados se utilizan para el calcular el costo de la travesía del borde en la dirección opuesta. |
Arroja un conjunto del tipo de datos pgr_costResult[]:
seq: | Secuencia de registros |
---|---|
id1: | Identificador del nodo visitado |
id2: | Identificador del borde usado (-1 para el último) |
cost: | Costo del recorrido desde el nodo id1 usando el borde id2 hasta su otro extremo |
Historia
- Renombrado en la versión 2.0.0
Ejemplos¶
- Sin reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_astar(
'SELECT id, source, target, cost, x1, y1, x2, y2 FROM edge_table',
4, 1, false, false
);
seq | node | edge | cost
-----+------+------+------
0 | 4 | 16 | 1
1 | 9 | 9 | 1
2 | 6 | 8 | 1
3 | 5 | 4 | 1
4 | 2 | 1 | 1
5 | 1 | -1 | 0
(4 rows)
- Con reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
FROM pgr_astar(
'SELECT id, source, target, cost, x1, y1, x2, y2, reverse_cost FROM edge_table',
4, 1, true, true
);
seq | node | edge | cost
-----+------+------+------
0 | 4 | 3 | 1
1 | 3 | 2 | 1
2 | 2 | 1 | 1
3 | 1 | -1 | 0
(4 rows)
Las consultas usan la red de ejemplo Datos Muestra