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 |
---|---|---|---|
|
ANY-INTEGER |
Identificador de la arista. |
|
|
ANY-INTEGER |
Identificador del primer vértice extremo de la arista. |
|
|
ANY-INTEGER |
Identificador del segundo vértice extremo de la arista. |
|
|
ANY-NUMERICAL |
Weight of the edge (
|
|
|
ANY-NUMERICAL |
-1 |
Weight of the edge (
|
|
ANY-NUMERICAL |
X coordinate of |
|
|
ANY-NUMERICAL |
Y coordinate of |
|
|
ANY-NUMERICAL |
X coordinate of |
|
|
ANY-NUMERICAL |
Y coordinate of |
Donde:
- ANY-INTEGER
SMALLINT
,INTEGER
,BIGINT
- ANY-NUMERICAL
SMALLINT
,INTEGER
,BIGINT
,REAL
,FLOAT
Consulta de combinaciones¶
Parámetro |
Tipo |
Descripción |
---|---|---|
|
ANY-INTEGER |
Identifier of the departure vertex. |
|
ANY-INTEGER |
Identifier of the arrival vertex. |
Donde:
- ANY-INTEGER
SMALLINT
,INTEGER
,BIGINT
Parámetros¶
Parámetro |
Tipo |
Descripción |
---|---|---|
Edges SQL |
|
Consulta de bordes como se describió anteriormente. |
Combinaciones SQL |
|
Consulta de combinaciones como se describió anteriormente. |
start_vid |
|
Comenzando identificador de vértice. |
start_vids |
|
Comenzando identificadores de vértices. |
end_vid |
|
Terminando identificador de vértice. |
end_vids |
|
Terminando identificadores de vértices. |
dirigido |
|
|
heuristic |
|
(opcional). Número heurístico. Valores válidos actuales 0~5. Predeterminado
|
factor |
|
(opcional). Para la manipulación de unidades. \(factor > 0\). Predeterminado |
epsilon |
|
(opcional). Para resultados menos restringidos. \(epsilon >= 1\). Predeterminado “” 1””. |
Ver también¶
Índices y tablas