pgr_aStar

pgr_aStar — La ruta más corta utilizando el algoritmo A*.

Boost Graph Interno

Disponibilidad

• Versión 3.2.0

  • Nueva función propuesta:

    • pgr_aStar(Combinaciones)

• Versión 3.0.0

  • Función oficial

• Versión 2.4.0

  • Nuevas funciones Propuestas:

    • pgr_aStar(Uno a Muchos)

    • pgr_aStar(Muchos a Uno)

    • pgr_aStar(Muchos a Muchos)

• Versión 2.3.0

  • Cambio de firma en pgr_aStar(Uno a Uno)

    • Firma antigua ya no soportada

• Versión 2.0.0

  • Oficial pgr_aStar(Uno a Uno)

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 verdadero.

• 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_aStar( Uno a Uno ) en:

  • pgr_aStar( Uno a Muchos )

  • pgr_aStar( Muchos a Uno )

  • pgr_aStar( Muchos a Muchos )

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

Firmas

Resumen

pgr_aStar(Edges SQL, from_vid,  to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, from_vid,  to_vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, from_vids, to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, from_vids, to_vids [, directed] [, heuristic] [, factor] [, epsilon])
pgr_aStar(Edges SQL, Combinations SQL  [, directed] [, heuristic] [, factor] [, epsilon]) -- Proposed on v3.2

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.

Uso de valores predeterminados

pgr_aStar(Edges SQL, from_vid, to_vid)
RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

De vértice \(2\) a vértice \(12\) en un grafo dirigido

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    4 |    1 |        0
   2 |        2 |    5 |    8 |    1 |        1
   3 |        3 |    6 |   11 |    1 |        2
   4 |        4 |   11 |   13 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

Uno a Uno

pgr_aStar(Edges SQL, from_vid,  to_vid  [, directed] [, heuristic] [, factor] [, epsilon])

RETURNS SET OF (seq, path_seq, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

De vértice \(2\) a vértice \(12\) en un grafo no dirigido usando la heurística \(2\)

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, 12,
    directed := false, heuristic := 2);
 seq | path_seq | node | edge | cost | agg_cost
-----+----------+------+------+------+----------
   1 |        1 |    2 |    2 |    1 |        0
   2 |        2 |    3 |    3 |    1 |        1
   3 |        3 |    4 |   16 |    1 |        2
   4 |        4 |    9 |   15 |    1 |        3
   5 |        5 |   12 |   -1 |    0 |        4
(5 rows)

Uno a Muchos

pgr_aStar(Edges SQL, from_vid,  to_vids [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, end_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

Desde el vértice \(2\) a los vértices \(\{3, 12\}\) en un grafo dirigido usando la heurística \(2\)

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    2, ARRAY[3, 12], heuristic := 2);
 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 |      12 |    2 |    4 |    1 |        0
   8 |        2 |      12 |    5 |   10 |    1 |        1
   9 |        3 |      12 |   10 |   12 |    1 |        2
  10 |        4 |      12 |   11 |   13 |    1 |        3
  11 |        5 |      12 |   12 |   -1 |    0 |        4
(11 rows)

Muchos a Uno

pgr_aStar(Edges SQL, from_vids, to_vid  [, directed] [, heuristic] [, factor] [, epsilon])
RETURNS SET OF (seq, path_seq, start_vid, node, edge, cost, agg_cost)
OR EMPTY SET

Ejemplo

De los vértices \(\{7, 2\}\) al vértice \(12\) en un grafo dirigido usando la heurística \(0\)

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

Muchos a Muchos

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

Ejemplo

De los vértices \(\{7, 2\}\) a los vértices \(\{3, 12\}\) en un gráfico dirigido usando la heurística \(2\)

SELECT * FROM pgr_astar(
    'SELECT id, source, target, cost, reverse_cost, x1, y1, x2, y2 FROM edge_table',
    ARRAY[7, 2], ARRAY[3, 12], heuristic := 2);
 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 |      12 |    2 |    4 |    1 |        0
   8 |        2 |         2 |      12 |    5 |   10 |    1 |        1
   9 |        3 |         2 |      12 |   10 |   12 |    1 |        2
  10 |        4 |         2 |      12 |   11 |   13 |    1 |        3
  11 |        5 |         2 |      12 |   12 |   -1 |    0 |        4
  12 |        1 |         7 |       3 |    7 |    6 |    1 |        0
  13 |        2 |         7 |       3 |    8 |    7 |    1 |        1
  14 |        3 |         7 |       3 |    5 |    8 |    1 |        2
  15 |        4 |         7 |       3 |    6 |    9 |    1 |        3
  16 |        5 |         7 |       3 |    9 |   16 |    1 |        4
  17 |        6 |         7 |       3 |    4 |    3 |    1 |        5
  18 |        7 |         7 |       3 |    3 |   -1 |    0 |        6
  19 |        1 |         7 |      12 |    7 |    6 |    1 |        0
  20 |        2 |         7 |      12 |    8 |    7 |    1 |        1
  21 |        3 |         7 |      12 |    5 |   10 |    1 |        2
  22 |        4 |         7 |      12 |   10 |   12 |    1 |        3
  23 |        5 |         7 |      12 |   11 |   13 |    1 |        4
  24 |        6 |         7 |      12 |   12 |   -1 |    0 |        5
(24 rows)

Combinaciones

pgr_aStar(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

Usando una tabla de combinaciones en un grafo dirigido usando heurística \(2\).

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

Parámetros

Parámetro	Tipo	Descripción
Edges SQL	TEXT	Consulta de bordes como se describe a continuación.
Combinaciones SQL	TEXT	Consulta de combinaciones como se describe a continuación.
from_vid	ANY-INTEGER	Identificador de vértice inicial. Parámetro en: Uno a Uno Uno a Muchos
from_vids	ARRAY[ANY-INTEGER]	Arreglo de identificadores de vértices iniciales. Parámetro en: Muchos a Uno Muchos a Muchos
to_vid	ANY-INTEGER	Identificador de vértice final. Parámetro en: Uno a Uno Muchos a Uno
to_vids	ARRAY[ANY-INTEGER]	Matriz de identificadores de vértices finales. Parámetro en: Uno a Muchos Muchos a Muchos

Parámetros opcionales

Parámetro	Tipo	Valores predeterminados	Descripción
dirigido	BOOLEAN	true	En caso de true el grafo se considera como Dirigido. Cuando false el gráfico se considera como No Dirigido
heurística	INTEGER	5	Número heurístico. Valores actuales válidos 0~5. Default 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

Consulta de aristas

edges_sql

Una consulta SQL, que debe regresar un conjunto de filas con las siguientes columnas:

Columna	Tipo	Valores predeterminados	Descripción
id	ANY-INTEGER		Identificador de la arista.
origen	ANY-INTEGER		Identificador del primer punto final en el vértice de la arista.
objetivo	ANY-INTEGER		Identificador del segundo punto final en el vértice de la arista.
costo	ANY-NUMERICAL		Peso de la arista (source, target) Cuando es negativo: la arista (source, target) no existe, por lo tanto no es parte del grafo.
reverse_cost	ANY-NUMERICAL	-1	Peso de la arista (target, source), En caso negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.
x1	ANY-NUMERICAL		Coordenada X del vértice source.
y1	ANY-NUMERICAL		Coordenada Y del vértice source.
x2	ANY-NUMERICAL		Coordenada X del vértice objetivo.
y2	ANY-NUMERICAL		Coordenada Y del vértice target.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

ANY-NUMERICAL

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

Consulta de combinaciones

Columna	Tipo	Valores predeterminados	Descripción
origen	ANY-INTEGER		Identificador del primer punto final en el vértice de la arista.
objetivo	ANY-INTEGER		Identificador del segundo punto final en el vértice de la arista.

Donde:

ANY-INTEGER

SMALLINT, INTEGER, BIGINT

Columnas de Resultados

Devuelve el conjunto de (seq, path_seq [, start_vid] [, end_vid], node, edge, cost, agg_cost)

Columna	Tipo	Descripción
seq	INT	Valor secuencial a partir de 1.
path_seq	INT	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
nodo	BIGINT	Identificador del nodo en la ruta de start_vid a end_vid.
arista	BIGINT	Identificador del borde utilizado para ir del nodo al siguiente nodo de la secuencia de ruta. -1 para el último nodo de la ruta.
costo	FLOAT	Costo de desplazamiento desde node usando `` edge`` hasta el siguiente nodo en la secuencia de ruta.
agg_cost	FLOAT	Coste agregado de start_v to node.

Ver también

• aStar - 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