• Versiones soportadas: Última (3.3) 3.2 3.1 3.0

• Versiones no soportadas: 2.6 2.5 2.4 2.3 2.2 2.1 2.0

pgr_bdAstar

pgr_bdAstar — Shortest path using the bidirectional A* algorithm.

Boost Graph Inside

Availability

• Versión 3.2.0

  • New proposed signature:

    • pgr_bdAstar (Combinations)

• Versión 3.0.0

  • Función oficial

• Versión 2.5.0

  • New Proposed signatures:

    • pgr_bdAstar (One to Many)

    • pgr_bdAstar (Many to One)

    • pgr_bdAstar (Many to Many)

  • Signature change on pgr_bdAstar (One to One)

    • Firma antigua ya no soportada

• Versión 2.0.0

  • Official pgr_bdAstar (One to One)

Descripción

Las características principales son:

• El tipo predeterminado de grafo es dirigido cuando

  • Falta la el indicador de directed.

  • El indicador de directed se configura a «true».

• A menos que se especifique lo contrario, la orden es:

  • primero por start_vid (si existe)

  • luego por end_vid

• Los valores se devuelven cuando hay una ruta

• Permita que \(v\) y \(u\) sean 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\)

• Los bordes con costes negativos no se incluyen en el grafo.

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

• Los resultados son equivalentes a la unión de los resultados de pgr_bdAStar( Uno a Uno ) en:

  • pgr_bdAstar( Uno a Muchos )

  • pgr_bdAstar( Muchos a Uno )

  • pgr_bdAstar( Muchos a Muchos )

• start_vid y end_vid en el resultado se utiliza para distinguir a qué ruta pertenece.

Signatures

Resumen

pgr_bdAstar(Edges SQL, start vid, end vid [, directed] [, heuristic] [, factor] [, epsilon])
pgr_bdAstar(Edges SQL, start vid, end vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_bdAstar(Edges SQL, start vids, end vid [, directed] [, heuristic] [, factor] [, epsilon])
pgr_bdAstar(Edges SQL, start vids, end vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_bdAstar(Edges SQL, Combinations SQL  [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)
OR EMPTY SET

Los parámetros opcionales son parámetros con nombre y tienen un valor predeterminado.

Uno a Uno

pgr_bdAstar(Edges SQL, start vid, end vid [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

From vertex \(2\) to vertex \(11\) on a directed graph with heuristic \(2\)

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edge_table',
  2, 11,
  directed => true, heuristic => 2
);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |   10 |    1 |        1
   3 |        3 |   10 |   12 |    1 |        2
   4 |        4 |   11 |   -1 |    0 |        3
(4 rows)

One to Many

pgr_bdAstar(Edges SQL, start vid, end vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

From vertex \(2\) to vertices \(\{3, 11\}\) on a directed graph with heuristic \(3\) and factor \(3.5\)

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edge_table',
  2, ARRAY[3, 11],
  heuristic => 3, factor := 3.5
);
 seq | path_seq | end_vid | node | edge | cost | agg_cost
-----+----------+---------+------+------+------+----------
   1 |        1 |       3 |    2 |    4 |    1 |        0
   2 |        2 |       3 |    5 |    8 |    1 |        1
   3 |        3 |       3 |    6 |    9 |    1 |        2
   4 |        4 |       3 |    9 |   16 |    1 |        3
   5 |        5 |       3 |    4 |    3 |    1 |        4
   6 |        6 |       3 |    3 |   -1 |    0 |        5
   7 |        1 |      11 |    2 |    4 |    1 |        0
   8 |        2 |      11 |    5 |    8 |    1 |        1
   9 |        3 |      11 |    6 |   11 |    1 |        2
  10 |        4 |      11 |   11 |   -1 |    0 |        3
(10 rows)

Muchos a Uno

pgr_bdAstar(Edges SQL, start vids, end vid [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

From vertices \(\{2, 10\}\) to vertex \(3\) on an undirected graph with heuristic \(4\)

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edge_table',
  ARRAY[2, 10], 3,
  false, heuristic => 4
);
 seq | path_seq | start_vid | node | edge | cost | agg_cost
-----+----------+-----------+------+------+------+----------
   1 |        1 |         2 |    2 |    2 |    1 |        0
   2 |        2 |         2 |    3 |   -1 |    0 |        1
   3 |        1 |        10 |   10 |   12 |    1 |        0
   4 |        2 |        10 |   11 |   11 |    1 |        1
   5 |        3 |        10 |    6 |    5 |    1 |        2
   6 |        4 |        10 |    3 |   -1 |    0 |        3
(6 rows)

Muchos a Muchos

pgr_bdAstar(Edges SQL, start vids, end vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

From vertices \(\{2, 10\}\) to vertices \(\{3, 11\}\) on a directed graph with factor \(0.5\)

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edge_table',
  ARRAY[2, 10], ARRAY[3, 11],
  factor => 0.5
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         2 |       3 |    2 |    4 |    1 |        0
   2 |        2 |         2 |       3 |    5 |    8 |    1 |        1
   3 |        3 |         2 |       3 |    6 |    9 |    1 |        2
   4 |        4 |         2 |       3 |    9 |   16 |    1 |        3
   5 |        5 |         2 |       3 |    4 |    3 |    1 |        4
   6 |        6 |         2 |       3 |    3 |   -1 |    0 |        5
   7 |        1 |         2 |      11 |    2 |    4 |    1 |        0
   8 |        2 |         2 |      11 |    5 |    8 |    1 |        1
   9 |        3 |         2 |      11 |    6 |   11 |    1 |        2
  10 |        4 |         2 |      11 |   11 |   -1 |    0 |        3
  11 |        1 |        10 |       3 |   10 |   10 |    1 |        0
  12 |        2 |        10 |       3 |    5 |    8 |    1 |        1
  13 |        3 |        10 |       3 |    6 |    9 |    1 |        2
  14 |        4 |        10 |       3 |    9 |   16 |    1 |        3
  15 |        5 |        10 |       3 |    4 |    3 |    1 |        4
  16 |        6 |        10 |       3 |    3 |   -1 |    0 |        5
  17 |        1 |        10 |      11 |   10 |   12 |    1 |        0
  18 |        2 |        10 |      11 |   11 |   -1 |    0 |        1
(18 rows)

Combinaciones

pgr_bdAstar(Edges SQL, Combinations SQL  [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

Using a combinations table on a directed graph with factor \(0.5\).

The combinations table:

SELECT * FROM combinations_table;
 source | target
--------+--------
      1 |      2
      1 |      3
      2 |      1
      2 |      4
      2 |     17
(5 rows)

The query:

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edge_table',
  'SELECT * FROM combinations_table',
  factor => 0.5
);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         1 |       2 |    1 |    1 |    1 |        0
   2 |        2 |         1 |       2 |    2 |   -1 |    0 |        1
   3 |        1 |         1 |       3 |    1 |    1 |    1 |        0
   4 |        2 |         1 |       3 |    2 |    4 |    1 |        1
   5 |        3 |         1 |       3 |    5 |    8 |    1 |        2
   6 |        4 |         1 |       3 |    6 |    9 |    1 |        3
   7 |        5 |         1 |       3 |    9 |   16 |    1 |        4
   8 |        6 |         1 |       3 |    4 |    3 |    1 |        5
   9 |        7 |         1 |       3 |    3 |   -1 |    0 |        6
  10 |        1 |         2 |       1 |    2 |    1 |    1 |        0
  11 |        2 |         2 |       1 |    1 |   -1 |    0 |        1
  12 |        1 |         2 |       4 |    2 |    4 |    1 |        0
  13 |        2 |         2 |       4 |    5 |    8 |    1 |        1
  14 |        3 |         2 |       4 |    6 |    9 |    1 |        2
  15 |        4 |         2 |       4 |    9 |   16 |    1 |        3
  16 |        5 |         2 |       4 |    4 |   -1 |    0 |        4
(16 rows)

Parámetros

Columna	Tipo	Descripción
Edges SQL	TEXT	Edges SQL as described below
Combinations SQL	TEXT	Combinations SQL as described below
start vid	BIGINT	Identifier of the starting vertex of the path.
start vids	ARRAY[BIGINT]	Array of identifiers of starting vertices.
end vid	BIGINT	Identifier of the ending vertex of the path.
end vids	ARRAY[BIGINT]	Array of identifiers of ending vertices.

Optional parameters

Columna	Tipo	default	Descripción
directed	BOOLEAN	true	When true the graph is considered Directed When false the graph is considered as Undirected.

aStar optional Parameters

Parámetro	Tipo	x Defecto	Descripción
heuristic	INTEGER	5	Heuristic number. Current valid values 0~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	1	Para la manipulación de unidades. math:factor > 0. Ver Factor
epsilon	FLOAT	1	Para resultados menos restringidos. \(epsilon >= 1\).

Consultas internas

Edges SQL

Parámetro	Tipo	x Defecto	Descripción
id	ANY-INTEGER		Identificador de la arista.
source	ANY-INTEGER		Identificador del primer vértice extremo de la arista.
target	ANY-INTEGER		Identificador del segundo vértice extremo de la arista.
cost	ANY-NUMERICAL		Weight of the edge (source, target) When negative: edge (source, target) does not exist, therefore it’s not part of the graph.
reverse_cost	ANY-NUMERICAL	-1	Weight of the edge (target, source), When negative: edge (target, source) does not exist, therefore it’s not part of the graph.
x1	ANY-NUMERICAL		X coordinate of source vertex.
y1	ANY-NUMERICAL		Y coordinate of source vertex.
x2	ANY-NUMERICAL		X coordinate of target vertex.
y2	ANY-NUMERICAL		Y coordinate of target vertex.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Combinations SQL

Parámetro	Tipo	Descripción
source	ANY-INTEGER	Identifier of the departure vertex.
target	ANY-INTEGER	Identifier of the arrival vertex.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Columnas de Resultados

Returns set of (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Columna	Tipo	Descripción
seq	INTEGER	Valor secuencial a partir de 1.
path_seq	INTEGER	Posición relativa en la ruta. Tiene el valor 1 para el principio de una ruta.
start_vid	BIGINT	Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta. Muchos a Uno Muchos a Muchos
end_vid	BIGINT	Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta. Uno a Muchos Muchos a Muchos
node	BIGINT	Identificador del nodo en la ruta de start_vid a end_vid.
edge	BIGINT	Identifier of the edge used to go from node to the next node in the path sequence. -1 for the last node of the path.
cost	FLOAT	Costo del desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.
agg_cost	FLOAT	Aggregate cost from start_vid to node.

Additional Examples

Example 1

Demonstration of repeated values are ignored, and result is sorted.

 SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edge_table',
  ARRAY[5, 3, 4, 3, 3, 4], ARRAY[3, 5, 3, 4]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         3 |       4 |    3 |    5 |    1 |        0
   2 |        2 |         3 |       4 |    6 |    9 |    1 |        1
   3 |        3 |         3 |       4 |    9 |   16 |    1 |        2
   4 |        4 |         3 |       4 |    4 |   -1 |    0 |        3
   5 |        1 |         3 |       5 |    3 |    5 |    1 |        0
   6 |        2 |         3 |       5 |    6 |    8 |    1 |        1
   7 |        3 |         3 |       5 |    5 |   -1 |    0 |        2
   8 |        1 |         4 |       3 |    4 |    3 |    1 |        0
   9 |        2 |         4 |       3 |    3 |   -1 |    0 |        1
  10 |        1 |         4 |       5 |    4 |   16 |    1 |        0
  11 |        2 |         4 |       5 |    9 |    9 |    1 |        1
  12 |        3 |         4 |       5 |    6 |    8 |    1 |        2
  13 |        4 |         4 |       5 |    5 |   -1 |    0 |        3
  14 |        1 |         5 |       3 |    5 |    8 |    1 |        0
  15 |        2 |         5 |       3 |    6 |    9 |    1 |        1
  16 |        3 |         5 |       3 |    9 |   16 |    1 |        2
  17 |        4 |         5 |       3 |    4 |    3 |    1 |        3
  18 |        5 |         5 |       3 |    3 |   -1 |    0 |        4
  19 |        1 |         5 |       4 |    5 |    8 |    1 |        0
  20 |        2 |         5 |       4 |    6 |    9 |    1 |        1
  21 |        3 |         5 |       4 |    9 |   16 |    1 |        2
  22 |        4 |         5 |       4 |    4 |   -1 |    0 |        3
(22 rows)

Example 2

Making start_vids the same as end_vids.

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edge_table',
  ARRAY[5, 3, 4], ARRAY[5, 3, 4]);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         3 |       4 |    3 |    5 |    1 |        0
   2 |        2 |         3 |       4 |    6 |    9 |    1 |        1
   3 |        3 |         3 |       4 |    9 |   16 |    1 |        2
   4 |        4 |         3 |       4 |    4 |   -1 |    0 |        3
   5 |        1 |         3 |       5 |    3 |    5 |    1 |        0
   6 |        2 |         3 |       5 |    6 |    8 |    1 |        1
   7 |        3 |         3 |       5 |    5 |   -1 |    0 |        2
   8 |        1 |         4 |       3 |    4 |    3 |    1 |        0
   9 |        2 |         4 |       3 |    3 |   -1 |    0 |        1
  10 |        1 |         4 |       5 |    4 |   16 |    1 |        0
  11 |        2 |         4 |       5 |    9 |    9 |    1 |        1
  12 |        3 |         4 |       5 |    6 |    8 |    1 |        2
  13 |        4 |         4 |       5 |    5 |   -1 |    0 |        3
  14 |        1 |         5 |       3 |    5 |    8 |    1 |        0
  15 |        2 |         5 |       3 |    6 |    9 |    1 |        1
  16 |        3 |         5 |       3 |    9 |   16 |    1 |        2
  17 |        4 |         5 |       3 |    4 |    3 |    1 |        3
  18 |        5 |         5 |       3 |    3 |   -1 |    0 |        4
  19 |        1 |         5 |       4 |    5 |    8 |    1 |        0
  20 |        2 |         5 |       4 |    6 |    9 |    1 |        1
  21 |        3 |         5 |       4 |    9 |   16 |    1 |        2
  22 |        4 |         5 |       4 |    4 |   -1 |    0 |        3
(22 rows)

Example 3

Manually assigned vertex combinations.

SELECT * FROM pgr_bdAstar(
  'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2
  FROM edge_table',
  'SELECT * FROM (VALUES (2, 3), (2, 5), (11, 3)) AS combinations (source, target)');
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         2 |       3 |    2 |    4 |    1 |        0
   2 |        2 |         2 |       3 |    5 |    8 |    1 |        1
   3 |        3 |         2 |       3 |    6 |    9 |    1 |        2
   4 |        4 |         2 |       3 |    9 |   16 |    1 |        3
   5 |        5 |         2 |       3 |    4 |    3 |    1 |        4
   6 |        6 |         2 |       3 |    3 |   -1 |    0 |        5
   7 |        1 |         2 |       5 |    2 |    4 |    1 |        0
   8 |        2 |         2 |       5 |    5 |   -1 |    0 |        1
   9 |        1 |        11 |       3 |   11 |   13 |    1 |        0
  10 |        2 |        11 |       3 |   12 |   15 |    1 |        1
  11 |        3 |        11 |       3 |    9 |   16 |    1 |        2
  12 |        4 |        11 |       3 |    4 |    3 |    1 |        3
  13 |        5 |        11 |       3 |    3 |   -1 |    0 |        4
(13 rows)

Ver también

• aStar - Familia de Funciones

• A* Bidireccional - Familia de Funciones

• Datos Muestra

• https://www.boost.org/libs/graph/doc/astar_search.html

• https://en.wikipedia.org/wiki/A*_search_algorithm

Índices y tablas

• Índice

• Página de Búsqueda