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	`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