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

pgRouting Manual (2.0.0)