pgr_aStarCost¶
pgr_aStarCost
—Costo total de la ruta más corta usando el algoritmo :A*.
Disponibilidad
Versión 3.2.0
Nueva firma propuesta:
pgr_aStarCost
(Combinaciones)
Versión 3.0.0
Función oficial
Versión 2.4.0
Nueva función propuesta
Descripción¶
La función pgr_aStarCost
sumarisa el costo de la ruta más corta usando el algoritmo A*.
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)\)
No devuelve una ruta.
Devuelve la suma de los costos de la ruta más corta para cada par de combinación de nodos requeridos.
Sea el caso de que los resultados se almacenen en una tabla, el índice unico lo conformarían el par (start_vid, end_vid)
Para grafos no dirigidos, los resultados son simétricos.
El agg_cost de (u, v) es el mismo que para (v, u).
Loas valores regresandos son ordenados en orden ascendente:
start_vid ascendente
end_vid ascendente
Firmas¶
Resumen
[directed, heuristic, factor, epsilon]
(start_vid, end_vid, agg_cost)
Uno a Uno¶
[directed, heuristic, factor, epsilon]
(start_vid, end_vid, agg_cost)
- Ejemplo:
De vértice \(6\) a vértice \(12\) en un grafo dirigido usando la heurística \(2\)
SELECT * FROM pgr_aStarCost(
'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)
Uno a Muchos¶
[directed, heuristic, factor, epsilon]
(start_vid, end_vid, 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_aStarCost(
'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)
Muchos a Uno¶
[directed, heuristic, factor, epsilon]
(start_vid, end_vid, 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_aStarCost(
'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)
Muchos a Muchos¶
[directed, heuristic, factor, epsilon]
(start_vid, end_vid, 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_aStarCost(
'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)
Combinaciones¶
[directed, heuristic, factor, epsilon]
(start_vid, end_vid, 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_aStarCost(
'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)
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¶
Conjunto de (start_vid, end_vid, agg_cost)
Columna |
Tipo |
Descripción |
---|---|---|
|
|
Identificador del vértice de salida. |
|
|
Identificador del vértice final. |
|
|
Costo afregado desde |
Ejemplos Adicionales¶
- Ejemplo 1:
Demostración de ignorar los valores repertidos, y resultado ordenado.
SELECT * FROM pgr_aStarCost(
'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)
- Ejemplo 2:
Haciendo vids iniciales los mismos que vids destinos.
SELECT * FROM pgr_aStarCost(
'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)
- Ejemplo 3:
Manualmente asignar combinaciones de vértices.
SELECT * FROM pgr_aStarCost(
'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)
Ver también¶
Índices y tablas