Versiones soportadas: latest (3.7) 3.6 3.5 3.4 3.3 3.2 3.1 3.0 main dev
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 v y u nodos en el grafo:

    • Si no hay camino de v a u:

      • no se devuelve ninguna fila correspondiente

      • agg_cost de v a u es

    • No hay camino cuando v=u por lo tanto

      • no se devuelve ninguna fila correspondiente

      • agg_cost de v a u es 0

  • 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 (x,y).

  • Tiempo de ejecución: O((E+V)logV)

  • 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