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:

  • 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 \(\infty\)

    • 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) * \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

Ver heuristicas disponibles y manupulación de factor.

Ver también

Índices y tablas