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.

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

Parámetros opcionales de aStar

Parámetro

Tipo

x Defecto

Descripción

heuristic

INTEGER

5

Número heurístico. Valores válidos 0~5.

  • 0: \(h(v) = 0\) (Utilizar 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)\)

factor

FLOAT

1

Para la manipulación de unidades. math:factor > 0.

epsilon

FLOAT

1

Para resultados menos restringidos. \(epsilon >= 1\).

Ver heuristicas disponibles y manupulación de factor.

Documentación avanzada

Heurística

Actualmente las funciones heurísticas disponibles son:

  • 0: \(h(v) = 0\) (Utilizar 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

Ver también

Índices y tablas