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:

  • El proceso 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 coste/coste_inverso como longitud en grados, x/y en lat/lon: Factor = 1 (no es necesario cambiar las unidades)

Análisis 2

Trabajando con coste/coste_inverso como longitud en metros, x/y en lat/lon: Factor = dependería de la ubicación de los puntos:

Latitud

Conversión

Factor

45

1 grado de longitud son 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