pgr_aStar
— La ruta más corta utilizando el algoritmo A*.
Disponibilidad
Soporte
Las características principales son:
directed
.directed
se configura a verdadero.start_vid
(si existe)end_vid
agg_cost
de \(v\) a \(u\) es \(\infty\)agg_cost
de v a u es \(0\)start_vid
y end_vid
en el resultado se utiliza para distinguir a qué ruta pertenece.Resumen
pgr_aStar(edges_sql, from_vid, to_vid [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(edges_sql, from_vid, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(edges_sql, from_vids, to_vid [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(edges_sql, from_vids, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
OR EMPTY SET
Los parámetros opcionales son parámetros con nombre y tienen un valor predeterminado.
Uso de valores predeterminados
pgr_aStar(edges_sql, from_vid, to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo: | De vértice \(2\) a vértice \(12\) en un grafo dirigido |
---|
SELECT * FROM pgr_astar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
2, 12);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 2 | 4 | 1 | 0
2 | 2 | 5 | 8 | 1 | 1
3 | 3 | 6 | 11 | 1 | 2
4 | 4 | 11 | 13 | 1 | 3
5 | 5 | 12 | -1 | 0 | 4
(5 rows)
pgr_aStar(edges_sql, from_vid, to_vid [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo: | De vértice \(2\) a vértice \(12\) en un grafo no dirigido usando la heurística \(2\) |
---|
SELECT * FROM pgr_astar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
2, 12,
directed := false, heuristic := 2);
seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
1 | 1 | 2 | 2 | 1 | 0
2 | 2 | 3 | 3 | 1 | 1
3 | 3 | 4 | 16 | 1 | 2
4 | 4 | 9 | 15 | 1 | 3
5 | 5 | 12 | -1 | 0 | 4
(5 rows)
pgr_aStar(edges_sql, from_vid, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo: | Desde el vértice \(2\) a los vértices \(\{3, 12\}\) en un grafo dirigido usando la heurística \(2\) |
---|
SELECT * FROM pgr_astar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
2, ARRAY[3, 12], heuristic := 2);
seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
1 | 1 | 3 | 2 | 4 | 1 | 0
2 | 2 | 3 | 5 | 8 | 1 | 1
3 | 3 | 3 | 6 | 9 | 1 | 2
4 | 4 | 3 | 9 | 16 | 1 | 3
5 | 5 | 3 | 4 | 3 | 1 | 4
6 | 6 | 3 | 3 | -1 | 0 | 5
7 | 1 | 12 | 2 | 4 | 1 | 0
8 | 2 | 12 | 5 | 10 | 1 | 1
9 | 3 | 12 | 10 | 12 | 1 | 2
10 | 4 | 12 | 11 | 13 | 1 | 3
11 | 5 | 12 | 12 | -1 | 0 | 4
(11 rows)
pgr_aStar(edges_sql, from_vids, to_vid [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo: | De los vértices \(\{7, 2\}\) al vértice \(12\) en un grafo dirigido usando la heurística \(0\) |
---|
SELECT * FROM pgr_astar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
ARRAY[7, 2], 12, heuristic := 0);
seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
1 | 1 | 2 | 2 | 4 | 1 | 0
2 | 2 | 2 | 5 | 10 | 1 | 1
3 | 3 | 2 | 10 | 12 | 1 | 2
4 | 4 | 2 | 11 | 13 | 1 | 3
5 | 5 | 2 | 12 | -1 | 0 | 4
6 | 1 | 7 | 7 | 6 | 1 | 0
7 | 2 | 7 | 8 | 7 | 1 | 1
8 | 3 | 7 | 5 | 10 | 1 | 2
9 | 4 | 7 | 10 | 12 | 1 | 3
10 | 5 | 7 | 11 | 13 | 1 | 4
11 | 6 | 7 | 12 | -1 | 0 | 5
(11 rows)
pgr_aStar(edges_sql, from_vids, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET
Ejemplo: | De los vértices \(\{7, 2\}\) a los vértices \(\{3, 12\}\) en un gráfico dirigido usando la heurística \(2\) |
---|
SELECT * FROM pgr_astar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
ARRAY[7, 2], ARRAY[3, 12], heuristic := 2);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 2 | 3 | 2 | 4 | 1 | 0
2 | 2 | 2 | 3 | 5 | 8 | 1 | 1
3 | 3 | 2 | 3 | 6 | 9 | 1 | 2
4 | 4 | 2 | 3 | 9 | 16 | 1 | 3
5 | 5 | 2 | 3 | 4 | 3 | 1 | 4
6 | 6 | 2 | 3 | 3 | -1 | 0 | 5
7 | 1 | 2 | 12 | 2 | 4 | 1 | 0
8 | 2 | 2 | 12 | 5 | 10 | 1 | 1
9 | 3 | 2 | 12 | 10 | 12 | 1 | 2
10 | 4 | 2 | 12 | 11 | 13 | 1 | 3
11 | 5 | 2 | 12 | 12 | -1 | 0 | 4
12 | 1 | 7 | 3 | 7 | 6 | 1 | 0
13 | 2 | 7 | 3 | 8 | 7 | 1 | 1
14 | 3 | 7 | 3 | 5 | 8 | 1 | 2
15 | 4 | 7 | 3 | 6 | 9 | 1 | 3
16 | 5 | 7 | 3 | 9 | 16 | 1 | 4
17 | 6 | 7 | 3 | 4 | 3 | 1 | 5
18 | 7 | 7 | 3 | 3 | -1 | 0 | 6
19 | 1 | 7 | 12 | 7 | 6 | 1 | 0
20 | 2 | 7 | 12 | 8 | 7 | 1 | 1
21 | 3 | 7 | 12 | 5 | 10 | 1 | 2
22 | 4 | 7 | 12 | 10 | 12 | 1 | 3
23 | 5 | 7 | 12 | 11 | 13 | 1 | 4
24 | 6 | 7 | 12 | 12 | -1 | 0 | 5
(24 rows)
Parámetro | Tipo | Descripción |
---|---|---|
edges_sql | TEXT |
edges_sql consulta interna. |
from_vid | ANY-INTEGER |
Identificador de vértice inicial. Parámetro en: |
from_vids | ARRAY[ANY-INTEGER] |
Arreglo de identificadores de vértices iniciales. Parámetro en: |
to_vid | ANY-INTEGER |
Identificador de vértice final. Parámetro en: |
to_vids | ARRAY[ANY-INTEGER] |
Matriz de identificadores de vértices finales. Parámetro en: |
Parámetro | Tipo | Valores predeterminados | Descripción |
---|---|---|---|
dirigido | BOOLEAN |
true |
|
heurística | INTEGER |
5 |
Número heurístico. Valores actuales válidos 0~5. Default
|
factor | FLOAT |
1 |
Para la manipulación de unidades. math:factor > 0. Ver Factor |
epsilon | FLOAT |
1 |
Para resultados menos restringidos. \(epsilon >= 1\). |
edges_sql: | Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas: |
---|
Columna | Tipo | Valores predeterminados | Descripción |
---|---|---|---|
id | ANY-INTEGER |
Identificador de la arista. | |
origen | ANY-INTEGER |
Identificador del primer punto final en el vértice de la arista. | |
objetivo | ANY-INTEGER |
Identificador del segundo punto final en el vértice de la arista. | |
costo | ANY-NUMERICAL |
Peso de la arista (source, target)
|
|
reverse_cost | ANY-NUMERICAL |
-1 | Peso de la arista (target, source),
|
x1 | ANY-NUMERICAL |
Coordenada X del vértice source. | |
y1 | ANY-NUMERICAL |
Coordenada Y del vértice source. | |
x2 | ANY-NUMERICAL |
Coordenada X del vértice objetivo. | |
y2 | ANY-NUMERICAL |
Coordenada Y del vértice target. |
Donde:
ANY-INTEGER: | SMALLINT, INTEGER, BIGINT |
---|---|
ANY-NUMERICAL: | SMALLINT, INTEGER, BIGINT, REAL, FLOAT |
Devuelve el conjunto de (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
Columna | Tipo | Descripción |
---|---|---|
seq | INT |
Valor secuencial a partir de 1. |
path_seq | INT |
Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta. |
start_vid | BIGINT |
Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta. |
end_vid | BIGINT |
Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. |
nodo | BIGINT |
Identificador del nodo en la ruta de start_vid a end_vid . |
arista | BIGINT |
Identificador del borde utilizado para ir del nodo al siguiente nodo de la secuencia de ruta. -1 para el último nodo de la ruta. |
costo | FLOAT |
Costo de desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta. |
agg_cost | FLOAT |
Coste agregado de start_v to node . |