Versiones no soportadas:2.6 2.5 2.4
A* - Familia de Funciones¶
El algoritmo A * (pronunciado «A estrella») se basa en el algoritmo de Dijkstra con una heurística que permite resolver problemas de ruta más cortos evaluando sólo un subconjunto de la gráfica.
pgr_aStar - Algoritmo A* para la ruta más corta.
pgr_aStarCost - Obtener el costo agregado de las rutas más cortas.
pgr_aStarCostMatrix - Obtener la matriz de costos de las rutas más cortas.
Descripción¶
Las características principales 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
y nodos en el grafo:Si no hay camino de
a :no se devuelve ninguna fila correspondiente
agg_cost
de a es
No hay camino cuando
por lo tantono se devuelve ninguna fila correspondiente
agg_cost
de v a u es
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
.
Tiempo de ejecució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. |
Ver heuristicas disponibles y manupulación de factor.
Documentación avanzada¶
Heurística¶
Actualmente las funciones heurísticas disponibles son:
0:
(Utilizar este valor para comparar con pgr_dijkstra)1:
2:
3:
4:
5:
Donde
Factor¶
Análisis 1
Trabajando con cost/reverse_cost como longitud en grados, x / y en lat/lon: Factor = 1 (sin necesidad de cambiar unidades)
Análisis 2
Trabajando con cost/reverse_cost donde la longitud es en metros, x / y es lat/lon: Factor dependere de la ubicación de los puntos:
Latitud |
Conversión |
Factor |
---|---|---|
45 |
1 grado de longitud es 78846,81 m |
78846 |
0 |
1 grado de longitud es 111319,46 m |
111319 |
Análisis 3
Trabajando con cost/reverse_cost con el tiempo en segundos, x / y en lat/lon: Factor: que depende de la ubicación de los puntos y en la velocidad promedio, digamos que 25m/s es la velocidad.
Latitud |
Conversión |
Factor |
---|---|---|
45 |
1 grado de longitud es (78846.81m)/(25m/s) |
3153 s |
0 |
1 grado de longitud es (111319.46 m)/(25m/s) |
4452 s |
Ver también¶
Índices y tablas