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

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

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

Parámetros

Parámetro Tipo Descripción
edges_sql TEXT Consulta de aristas SQL 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