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:

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

Parámetro

Tipo

x Defecto

Descripción

heuristic

INTEGER

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