Versiones no soportadas:2.6 2.5
A* Bidireccional - Familia de Funciones¶
El algoritmo bidirectional A* (leído «A estrella») se basa en el algoritmo A*.
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 costes 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 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
y nodos en el grafo:Si no hay camino de
a :no se devuelve ninguna fila correspondiente
agg_cost
de a es
No hay camino cuando
por lo tantono se devuelve ninguna fila correspondiente
agg_cost
de v a u es
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
.
Tiempo de ejecución:
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
Ver heuristicas disponibles y manupulación de factor.
Ver también¶
Índices y tablas