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.

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

Parameters

Column

Type

Description

Edges SQL

TEXT

Edges SQL as described below

Combinations SQL

TEXT

Combinations SQL as described below

start vid

BIGINT

Identifier of the starting vertex of the path.

start vids

ARRAY[BIGINT]

Array of identifiers of starting vertices.

end vid

BIGINT

Identifier of the ending vertex of the path.

end vids

ARRAY[BIGINT]

Array of identifiers of ending vertices.

Optional parameters

Column

Type

default

Description

directed

BOOLEAN

true

  • When true the graph is considered Directed

  • When false the graph is considered as Undirected.

aStar optional Parameters

Parameter

Type

Default

Description

heuristic

INTEGER

5

Heuristic number. Current valid values 0~5.

  • 0: h(v) = 0 (Use this value to compare with pgr_dijkstra)

  • 1: h(v) abs(max(dx, dy))

  • 2: h(v) abs(min(dx, dy))

  • 3: h(v) = dx * dx + dy * dy

  • 4: h(v) = sqrt(dx * dx + dy * dy)

  • 5: h(v) = abs(dx) + abs(dy)

factor

FLOAT

1

For units manipulation. \(factor > 0\). See Factor

epsilon

FLOAT

1

For less restricted results. \(epsilon >= 1\).

Inner queries

Edges SQL

Parameter

Type

Default

Description

id

ANY-INTEGER

Identifier of the edge.

source

ANY-INTEGER

Identifier of the first end point vertex of the edge.

target

ANY-INTEGER

Identifier of the second end point vertex of the edge.

cost

ANY-NUMERICAL

Weight of the edge (source, target)

  • When negative: edge (source, target) does not exist, therefore it’s not part of the graph.

reverse_cost

ANY-NUMERICAL

-1

Weight of the edge (target, source),

  • When negative: edge (target, source) does not exist, therefore it’s not part of the graph.

x1

ANY-NUMERICAL

X coordinate of source vertex.

y1

ANY-NUMERICAL

Y coordinate of source vertex.

x2

ANY-NUMERICAL

X coordinate of target vertex.

y2

ANY-NUMERICAL

Y coordinate of target vertex.

Where:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Combinations SQL

Parameter

Type

Description

source

ANY-INTEGER

Identifier of the departure vertex.

target

ANY-INTEGER

Identifier of the arrival vertex.

Where:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Documentación avanzada

The A* (pronounced «A Star») algorithm is based on Dijkstra’s algorithm with a heuristic, that is an estimation of the remaining cost from the vertex to the goal, that allows to solve most shortest path problems by evaluation only a sub-set of the overall graph.

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

Ver también

Índices y tablas