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 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 |
|
Identificador de la arista. |
|
origen |
|
Identificador del primer punto final en el vértice de la arista. |
|
objetivo |
|
Identificador del segundo punto final en el vértice de la arista. |
|
cost |
|
Peso de la arista (source, target)
|
|
reverse_cost |
|
-1 |
Peso de la arista (target, source),
|
x1 |
|
Coordenada X del vértice source. |
|
y1 |
|
Coordenada Y del vértice source. |
|
x2 |
|
Coordenada X del vértice objetivo. |
|
y2 |
|
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 |
|
Identificador del primer punto final en el vértice de la arista. |
|
objetivo |
|
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 |
|
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