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.

Versiones anteriores de esta página

  • Versiones soportadas: actual(3.1) 3.0 2.6

  • Versiones no soportadas: 2.5

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 un camino.

  • 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

edges_sql

Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:

Columna

Tipo

Valores predeterminados

Descripción

id

ANY-INTEGER

Identificador de la arista.

origen

ANY-INTEGER

Identificador del primer punto final en el vértice de la arista.

objetivo

ANY-INTEGER

Identificador del segundo punto final en el vértice de la arista.

cost

ANY-NUMERICAL

Peso de la arista (source, target)

  • Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.

reverse_cost

ANY-NUMERICAL

-1

Peso de la arista (target, source),

  • En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

x1

ANY-NUMERICAL

Coordenada X del vértice source.

y1

ANY-NUMERICAL

Coordenada Y del vértice source.

x2

ANY-NUMERICAL

Coordenada X del vértice objetivo.

y2

ANY-NUMERICAL

Coordenada Y del vértice target.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Consulta de combinaciones

Columna

Tipo

Valores predeterminados

Descripción

origen

ANY-INTEGER

Identificador del primer punto final en el vértice de la arista.

objetivo

ANY-INTEGER

Identificador del segundo punto final en el vértice de la arista.

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