pgRouting Manual (2.0.0)

pgr_bdAstar - Camino más corto bidireccional A*

«  pgr_astar - Camino más corto A*   ::   Contents   ::   pgr_bdDijkstra - Camino más corto bidireccional de Dijkstra  »


pgr_bdAstar - Camino más corto bidireccional A*

Nombre

pgr_bdAstar - Regresa el camino más corto usando el algoritmo A* bidireccional.

Sinopsis

Este es un algoritmo de búsqueda bidireccional A*. Busca desde la fuente hasta el destino y al mismo tiempo desde el destino al origen y termina cuando estos las búsquedas se reúnen en el centro. Devuelve un conjunto de registros pgr_costResult (seq, id1, id2, costo) que conforman un camino.

pgr_costResult[] pgr_bdAstar(sql text, source integer, target integer,
                             directed boolean, has_rcost boolean);

Descripción

sql:

Consulta SQL que debe proporcionar un conjunto de registros con los siguientes campos:

SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table
id:int4 identificador del borde
source:int4 Identificador del vértice inicial del borde
target:int4 Identificador del vértice final del borde
cost:float8 valor del costo del recorrido sobre el borde. Un costo negativo evitará que el borde sea insertado en el gráfico.
x1:Coordenada x del punto del inicio del borde
y1:Coordenada y del punto del inicio del borde
x2:Coordenada x del punto del final del borde
y2:Coordenada y del punto del final del borde
reverse_cost:(opcional) el costo para el recorrido inverso del borde. Se utiliza sólo cuando los parámetros directed y has_rcost son True (ver el comentario anterior acerca de los costos negativos).
source:

int4 identificador del punto de partida

target:

int4 Identificador del punto de llegada

directed:

true Si la gráfica es direccionada

has_rcost:

Si es True, el campo reverse_cost del conjunto de registros generados se utilizan para el calcular el costo de la travesía del borde en la dirección opuesta.

Arroja un conjunto del tipo de datos pgr_costResult[]:

seq:Secuencia de registros
id1:Identificador del nodo visitado
id2:Identificador del borde (-1 para el ultimo registro)
cost:costo para atravesar desde el nodo id1 usando el borde``id2`` hasta su otro extremo

Advertencia

Usted debe reconectarse a la base de datos después de CREATE EXTENSION pgRouting . De lo contrario la función arrojará el error Error computing path: std::bad_alloc.

Historia

  • Nuevo en la versión 2.0.0

Ejemplos

  • Sin reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_bdAstar(
        'SELECT id, source, target, cost, x1, y1, x2, y2 FROM edge_table',
        4, 10, false, false
    );

 seq | node | edge | cost
-----+------+------+------
   0 |    4 |    3 |    0
   1 |    3 |    5 |    1
   2 |    6 |   11 |    1
   3 |   11 |   12 |    0
   4 |   10 |   -1 |    0
(5 rows)
  • Con reverse_cost
SELECT seq, id1 AS node, id2 AS edge, cost
    FROM pgr_bdAstar(
        'SELECT id, source, target, cost, x1, y1, x2, y2, reverse_cost FROM edge_table',
        4, 10, true, true
    );

 seq | node | edge | cost
-----+------+------+------
   0 |    4 |    3 |    1
   1 |    3 |    5 |    1
   2 |    6 |    8 |    1
   3 |    5 |   10 |    1
   4 |   10 |   -1 |    0
(5 rows)

Las consultas usan la red de ejemplo Datos Muestra

«  pgr_astar - Camino más corto A*   ::   Contents   ::   pgr_bdDijkstra - Camino más corto bidireccional de Dijkstra  »