A* Bidireccional - Familia de Funciones

  • pgr_bdAstar - Algoritmo bidireccional A* para obtener rutas.

  • pgr_bdAstarCost - Algoritmo bidireccional A* para calcular el coste de las rutas.

  • pgr_bdAstarCostMatrix Algoritmo bidireccional A* para calcular una matriz de coste de rutas.

Descripción

La búsqueda bidireccional, basado en algoritmo de A*, encuentra el camino más corto desde el vértice inicial (start_vid) hasta el vértice final (end_vid). Ejecuta dos búsquedas simultáneas: uno hacia adelande del start_vid y la otra en reversa desde el end_vid, parando cuando las dos se encuentran en el medio. Esta aplicación puede utilizarse con un grafo dirigido y un grafo sin dirección.

Las características principales son:

  • El proceso se realiza sólo en las aristas con costos positivos.

  • Valores son regresados cuando hay una ruta.

  • Cuando el vértice inicial y el vértice final son iguales, no hay camino.

    • El agg_cost de los valores no incluídos (v, v) es 0

  • Cuando el vértice inicial y el vértice final son diferentes y no hay camino:

    • El “agg_cost” de los valores no incluídos “(u, v)” es :math: infty

  • Duración (peor de los casos): \(O ((E + V) * \log V)\)

  • Para grandes gráficos donde hay un camino entre el vértice inicial y el vértice final:

    • Se espera que termine más rápido que pgr_astar

Firmas

Consulta de aristas

Parámetro

Tipo

x Defecto

Descripción

id

ANY-INTEGER

Identificador de la arista.

source

ANY-INTEGER

Identificador del primer vértice extremo de la arista.

target

ANY-INTEGER

Identificador del segundo vértice extremo de la arista.

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.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Consulta de combinaciones

Parámetro

Tipo

Descripción

source

ANY-INTEGER

Identifier of the departure vertex.

target

ANY-INTEGER

Identifier of the arrival vertex.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Parámetros

Parámetro

Tipo

Descripción

Edges SQL

TEXT

Consulta de bordes como se describió anteriormente.

Combinaciones SQL

TEXT

Consulta de combinaciones como se describió anteriormente.

start_vid

ANY-INTEGER

Comenzando identificador de vértice.

start_vids

ARRAY[ANY-INTEGER]

Comenzando identificadores de vértices.

end_vid

ANY-INTEGER

Terminando identificador de vértice.

end_vids

ARRAY[ANY-INTEGER]

Terminando identificadores de vértices.

dirigido

BOOLEAN

  • Opcional.

    • Cuando false el gráfico se considera como No Dirigido

    • El valor predeterminado `` true`` considera el gráfico como Dirigido.

heuristic

INTEGER

(opcional). Número heurístico. Valores válidos actuales 0~5. Predeterminado 5

  • 0: h(v) = 0 (utilizar este valor para comparar con 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

(opcional). Para la manipulación de unidades. \(factor > 0\). Predeterminado 1. Ver Factor

epsilon

FLOAT

(opcional). Para resultados menos restringidos. \(epsilon >= 1\). Predeterminado “” 1””.

Ver también

Índices y tablas