aStar - 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.

Versiones anteriores de esta página

Información general

Las características principales son:

  • El tipo predeterminado de grafo es dirigido cuando
    • Falta la el indicador de directed.
    • El indicador de directed se configura a «true».
  • A menos que se especifique lo contrario, la orden es:
    • primero por start_vid (si existe)
    • luego por end_vid
  • Los valores se devuelven cuando hay una ruta
  • Permita que \(v\) y \(u\) sean 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\)
  • Los bordes con costes negativos no se incluyen en el grafo.
  • 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)\)

Documentación avanzada

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)\)

Heurística

Actualmente las funciones heurísticas disponibles son:

  • 0: \(h(v) = 0\) (Utilizat este valor para comparar con pgr_dijkstra)
  • 1: \(h(v) = abs(max(\Delta x, \Delta y))\)
  • 2: \(h(v) = abs(min(\Delta x, \Delta y))\)
  • 3: \(h(v) = \Delta x * \Delta x + \Delta y * \Delta y\)
  • 4: \(h(v) = sqrt(\Delta x * \Delta x + \Delta y * \Delta y)\)
  • 5: \(h(v) = abs(\Delta x) + abs(\Delta y)\)

Donde \(\Delta x = x_1 - x_0\) y \(\Delta y = y_1 - y_0\)

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