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.
Versiones anteriores de esta página
Las características principales son:
directed
.directed
se configura a «true».start_vid
(si existe)end_vid
agg_cost
de \(v\) a \(u\) es \(\infty\)agg_cost
de v a u es \(0\)El algoritmo A * (pronunciado «A estrella») se basa en el algoritmo de Dijkstra con un heurística, que es una estimación de los costos desde el vértice al objetivo, esto permite resolver problemas de ruta más cortos evaluando sólo un subconjunto de la gráfica original. Tiempo de ejecución: \(O((E + V) * \log V)\)
Actualmente las funciones heurísticas disponibles son:
Donde \(\Delta x = x_1 - x_0\) y \(\Delta y = y_1 - y_0\)
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 |