pgr_bdAstar
¶
pgr_bdAstar
— Devuelve la ruta más corta usando el algoritmo Bidireccional A*.
Disponibilidad
Versión 3.6.0
Standarizing output columns to
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
pgr_bdAstar
(Uno a Uno) ha añadido las columnasstart_vid
yend_vid
.pgr_bdAstar
(Uno a Muchos) ha añadido la columnaend_vid
.pgr_bdAstar
(Muchos a Uno) ha añadido la columnastart_vid
.
Versión 3.2.0
Nueva firma propuesta:
pgr_bdAstar
(Combinaciones)
Versión 3.0.0
Función oficial
Versión 2.5.0
Nuevas firmas propuestas:
pgr_bdAstar
(Uno a Muchos)pgr_bdAstar
(Muchos a Uno)pgr_bdAstar
(Muchos a Muchos)
Cambio de firma en
pgr_bdAstar
(Uno a Uno)Firma antigua ya no soportada
Versión 2.0.0
Oficial
pgr_bdAstar
(Uno a Uno)
Descripción¶
Las principales características son:
Funciona para grafos dirigidos y no dirigidos.
Ordenamiento es:
primero por
start_vid
(si existe)luego por
end_vid
Los valores se devuelven cuando hay una ruta.
Sean \(v\) y \(u\) nodos en el grafo:
Si no hay camino de \(v\) a \(u\):
no se devuelve ninguna fila correspondiente
agg_cost
de \(v\) a \(u\) es \(\infty\)
No hay camino cuando \(v = u\) por lo tanto
no se devuelve ninguna fila correspondiente
agg_cost
de v a u es \(0\)
Cuando las coordenadas (x,y) para el mismo identificador de vértice difieren:
Se utiliza una selección aleatoria de las coordenadas del vértice \((x,y)\).
Tiempo de ejecución: \(O((E + V) * \log V)\)
Los resultados son equivalentes a la unión de los resultados de pgr_bdAStar( Uno a Uno ) en:
pgr_bdAstar
(Uno a Muchos)pgr_bdAstar
(Muchos a Uno)pgr_bdAstar
(Muchos a Muchos)pgr_bdAstar
(Combinaciones)
Firmas¶
Resumen
[directed, heuristic, factor, epsilon]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
Los parámetros opcionales son parámetros con nombre y tienen un valor predeterminado.
Uno a Uno¶
[directed, heuristic, factor, epsilon]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
De vértice \(6\) a vértice \(12\) en un grafo dirigido usando la heurística \(2\)
SELECT * FROM pgr_bdAstar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
FROM edges',
6, 12,
directed => true, heuristic => 2
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 12 | 6 | 4 | 1 | 0
2 | 2 | 6 | 12 | 7 | 10 | 1 | 1
3 | 3 | 6 | 12 | 8 | 12 | 1 | 2
4 | 4 | 6 | 12 | 12 | -1 | 0 | 3
(4 rows)
Uno a Muchos¶
[directed, heuristic, factor, epsilon]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Desde el vértice \(6\) a los vértices \(\{12, 10\}\) en un grafo dirigido usando la heurística \(3\) con factor \(3.5\)
SELECT * FROM pgr_bdAstar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
FROM edges',
6, ARRAY[10, 12],
heuristic => 3, factor := 3.5
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
7 | 1 | 6 | 12 | 6 | 4 | 1 | 0
8 | 2 | 6 | 12 | 7 | 8 | 1 | 1
9 | 3 | 6 | 12 | 11 | 11 | 1 | 2
10 | 4 | 6 | 12 | 12 | -1 | 0 | 3
(10 rows)
Muchos a Uno¶
[directed, heuristic, factor, epsilon]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
De los vértices \(\{6, 8\}\) al vértice \(10\) en un grafo no dirigido usando la heurística \(4\)
SELECT * FROM pgr_bdAstar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
FROM edges',
ARRAY[6, 8], 10,
false, heuristic => 4
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 2 | 1 | 0
2 | 2 | 6 | 10 | 10 | -1 | 0 | 1
3 | 1 | 8 | 10 | 8 | 10 | 1 | 0
4 | 2 | 8 | 10 | 7 | 4 | 1 | 1
5 | 3 | 8 | 10 | 6 | 2 | 1 | 2
6 | 4 | 8 | 10 | 10 | -1 | 0 | 3
(6 rows)
Muchos a Muchos¶
[directed, heuristic, factor, epsilon]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
De los vértices \(\{6, 8\}\) a los vértices \(\{10, 12\}\) en un gráfico dirigido con factor \(0.5\)
SELECT * FROM pgr_bdAstar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
FROM edges',
ARRAY[6, 8], ARRAY[10, 12],
factor => 0.5
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 10 | 6 | 4 | 1 | 0
2 | 2 | 6 | 10 | 7 | 8 | 1 | 1
3 | 3 | 6 | 10 | 11 | 9 | 1 | 2
4 | 4 | 6 | 10 | 16 | 16 | 1 | 3
5 | 5 | 6 | 10 | 15 | 3 | 1 | 4
6 | 6 | 6 | 10 | 10 | -1 | 0 | 5
7 | 1 | 6 | 12 | 6 | 4 | 1 | 0
8 | 2 | 6 | 12 | 7 | 10 | 1 | 1
9 | 3 | 6 | 12 | 8 | 12 | 1 | 2
10 | 4 | 6 | 12 | 12 | -1 | 0 | 3
11 | 1 | 8 | 10 | 8 | 10 | 1 | 0
12 | 2 | 8 | 10 | 7 | 8 | 1 | 1
13 | 3 | 8 | 10 | 11 | 9 | 1 | 2
14 | 4 | 8 | 10 | 16 | 16 | 1 | 3
15 | 5 | 8 | 10 | 15 | 3 | 1 | 4
16 | 6 | 8 | 10 | 10 | -1 | 0 | 5
17 | 1 | 8 | 12 | 8 | 12 | 1 | 0
18 | 2 | 8 | 12 | 12 | -1 | 0 | 1
(18 rows)
Combinaciones¶
[directed, heuristic, factor, epsilon]
(seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
- Ejemplo:
Usando una tabla de combinaciones en un grafo dirigido con factor \(0.5\).
La tabla de combinaciones:
SELECT * FROM combinations;
source | target
--------+--------
5 | 6
5 | 10
6 | 5
6 | 15
6 | 14
(5 rows)
La consulta:
SELECT * FROM pgr_bdAstar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
FROM edges',
'SELECT * FROM combinations',
factor => 0.5
);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 5 | 6 | 5 | 1 | 1 | 0
2 | 2 | 5 | 6 | 6 | -1 | 0 | 1
3 | 1 | 5 | 10 | 5 | 1 | 1 | 0
4 | 2 | 5 | 10 | 6 | 4 | 1 | 1
5 | 3 | 5 | 10 | 7 | 8 | 1 | 2
6 | 4 | 5 | 10 | 11 | 9 | 1 | 3
7 | 5 | 5 | 10 | 16 | 16 | 1 | 4
8 | 6 | 5 | 10 | 15 | 3 | 1 | 5
9 | 7 | 5 | 10 | 10 | -1 | 0 | 6
10 | 1 | 6 | 5 | 6 | 1 | 1 | 0
11 | 2 | 6 | 5 | 5 | -1 | 0 | 1
12 | 1 | 6 | 15 | 6 | 4 | 1 | 0
13 | 2 | 6 | 15 | 7 | 8 | 1 | 1
14 | 3 | 6 | 15 | 11 | 9 | 1 | 2
15 | 4 | 6 | 15 | 16 | 16 | 1 | 3
16 | 5 | 6 | 15 | 15 | -1 | 0 | 4
(16 rows)
Parámetros¶
Columna |
Tipo |
Descripción |
---|---|---|
|
SQL de aristas como se describe a continuación |
|
|
SQL de combinaciones como se describe a abajo |
|
salida |
|
Identificador del vértice inicial de la ruta. |
salidas |
|
Arreglo de identificadores de vértices iniciales. |
destino |
|
Identificador del vértice final de la ruta. |
destinos |
|
Arreglo de identificadores de vértices finales. |
Parámetros opcionales¶
Columna |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
|
|
Parámetros opcionales de aStar¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
|
5 |
Número heurístico. Valores válidos 0~5.
|
|
|
|
Para la manipulación de unidades. math:factor > 0. |
|
|
|
Para resultados menos restringidos. \(epsilon >= 1\). |
Ver heuristicas disponibles y manupulación de factor.
Consultas Internas¶
SQL aristas¶
Parámetro |
Tipo |
x Defecto |
Descripción |
---|---|---|---|
|
ENTEROS |
Identificador de la arista. |
|
|
ENTEROS |
Identificador del primer vértice de la arista. |
|
|
ENTEROS |
Identificador del segundo vértice de la arista. |
|
|
FLOTANTES |
Peso de la arista (
|
|
|
FLOTANTES |
-1 |
Peso de la arista (
|
|
FLOTANTES |
Coordenada X del vértice |
|
|
FLOTANTES |
Coordenada Y del vértice |
|
|
FLOTANTES |
Coordenada X del vértice |
|
|
FLOTANTES |
Coordenada Y del vértice |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
- FLOTANTES:
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
SQL Combinaciones¶
Parámetro |
Tipo |
Descripción |
---|---|---|
|
ENTEROS |
Identificador del vértice de salida. |
|
ENTEROS |
Identificador del vértice de llegada. |
Donde:
- ENTEROS:
SMALLINT
,INTEGER
,BIGINT
Columnas de resultados¶
Devuelve el conjunto de (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Valor secuencial a partir de 1. |
|
|
Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta. |
|
|
Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta. |
|
|
Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. |
|
|
Identificador del nodo en la ruta de |
|
|
Identificador de la arista utilizado para ir del |
|
|
Costo para atravesar desde |
|
|
Costo agregado desde |
Ejemplos Adicionales¶
- Ejemplo 1:
Demostración de ignorar los valores repertidos, y resultado ordenado.
SELECT * FROM pgr_bdAstar(
'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]);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 7 | 10 | 7 | 8 | 1 | 0
2 | 2 | 7 | 10 | 11 | 9 | 1 | 1
3 | 3 | 7 | 10 | 16 | 16 | 1 | 2
4 | 4 | 7 | 10 | 15 | 3 | 1 | 3
5 | 5 | 7 | 10 | 10 | -1 | 0 | 4
6 | 1 | 7 | 15 | 7 | 8 | 1 | 0
7 | 2 | 7 | 15 | 11 | 9 | 1 | 1
8 | 3 | 7 | 15 | 16 | 16 | 1 | 2
9 | 4 | 7 | 15 | 15 | -1 | 0 | 3
10 | 1 | 10 | 7 | 10 | 5 | 1 | 0
11 | 2 | 10 | 7 | 11 | 8 | 1 | 1
12 | 3 | 10 | 7 | 7 | -1 | 0 | 2
13 | 1 | 10 | 15 | 10 | 5 | 1 | 0
14 | 2 | 10 | 15 | 11 | 9 | 1 | 1
15 | 3 | 10 | 15 | 16 | 16 | 1 | 2
16 | 4 | 10 | 15 | 15 | -1 | 0 | 3
17 | 1 | 15 | 7 | 15 | 3 | 1 | 0
18 | 2 | 15 | 7 | 10 | 5 | 1 | 1
19 | 3 | 15 | 7 | 11 | 8 | 1 | 2
20 | 4 | 15 | 7 | 7 | -1 | 0 | 3
21 | 1 | 15 | 10 | 15 | 3 | 1 | 0
22 | 2 | 15 | 10 | 10 | -1 | 0 | 1
(22 rows)
- Ejemplo 2:
Haciendo vids iniciales los mismos que vids destinos.
SELECT * FROM pgr_bdAstar(
'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
FROM edges',
ARRAY[7, 10, 15], ARRAY[7, 10, 15]);
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 7 | 10 | 7 | 8 | 1 | 0
2 | 2 | 7 | 10 | 11 | 9 | 1 | 1
3 | 3 | 7 | 10 | 16 | 16 | 1 | 2
4 | 4 | 7 | 10 | 15 | 3 | 1 | 3
5 | 5 | 7 | 10 | 10 | -1 | 0 | 4
6 | 1 | 7 | 15 | 7 | 8 | 1 | 0
7 | 2 | 7 | 15 | 11 | 9 | 1 | 1
8 | 3 | 7 | 15 | 16 | 16 | 1 | 2
9 | 4 | 7 | 15 | 15 | -1 | 0 | 3
10 | 1 | 10 | 7 | 10 | 5 | 1 | 0
11 | 2 | 10 | 7 | 11 | 8 | 1 | 1
12 | 3 | 10 | 7 | 7 | -1 | 0 | 2
13 | 1 | 10 | 15 | 10 | 5 | 1 | 0
14 | 2 | 10 | 15 | 11 | 9 | 1 | 1
15 | 3 | 10 | 15 | 16 | 16 | 1 | 2
16 | 4 | 10 | 15 | 15 | -1 | 0 | 3
17 | 1 | 15 | 7 | 15 | 3 | 1 | 0
18 | 2 | 15 | 7 | 10 | 5 | 1 | 1
19 | 3 | 15 | 7 | 11 | 8 | 1 | 2
20 | 4 | 15 | 7 | 7 | -1 | 0 | 3
21 | 1 | 15 | 10 | 15 | 3 | 1 | 0
22 | 2 | 15 | 10 | 10 | -1 | 0 | 1
(22 rows)
- Ejemplo 3:
Manualmente asignar combinaciones de vértices.
SELECT * FROM pgr_bdAstar(
'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)');
seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
1 | 1 | 6 | 7 | 6 | 4 | 1 | 0
2 | 2 | 6 | 7 | 7 | -1 | 0 | 1
3 | 1 | 6 | 10 | 6 | 4 | 1 | 0
4 | 2 | 6 | 10 | 7 | 8 | 1 | 1
5 | 3 | 6 | 10 | 11 | 9 | 1 | 2
6 | 4 | 6 | 10 | 16 | 16 | 1 | 3
7 | 5 | 6 | 10 | 15 | 3 | 1 | 4
8 | 6 | 6 | 10 | 10 | -1 | 0 | 5
9 | 1 | 12 | 10 | 12 | 13 | 1 | 0
10 | 2 | 12 | 10 | 17 | 15 | 1 | 1
11 | 3 | 12 | 10 | 16 | 16 | 1 | 2
12 | 4 | 12 | 10 | 15 | 3 | 1 | 3
13 | 5 | 12 | 10 | 10 | -1 | 0 | 4
(13 rows)
Ver también¶
Índices y tablas