pgr_aStar

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

_images/boost-inside.jpeg

Adentro: Boost Graph

Disponibilidad

  • Versión 3.6.0

    • Estandarización de las columnas de salida a (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)

      • pgr_aStar (Uno a Uno) ha añadido las columnas start_vid y end_vid.

      • pgr_aStar (Uno a Muchos) ha añadido la columna end_vid.

      • pgr_aStar (Muchos a Uno) ha añadido la columna start_vid.

  • Versión 3.2.0

  • Versión 3.0.0

    • Función oficial

  • Versión 2.4.0

  • Versión 2.3.0

    • Cambio de firma en pgr_astar (Uno a Uno)

      • Firma antigua ya no soportada

  • Versión 2.0.0

Descripción

Las principales características son:

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

Firmas

Resumen

pgr_aStar(SQL de aristas, salida, destino, K, [opciones])
pgr_aStar(SQL de aristas, salida, destinos, K, [opciones])
pgr_aStar(SQL de aristas, salidas, destino, K, [opciones])
pgr_aStar(SQL de aristas, salidas, destinos, K, [opciones])
pgr_aStar(SQL de aristas, SQL de combinaciones, [opciones])
opcionales: [directed, heuristic, factor, epsilon]
Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO

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

Uno a Uno

pgr_aStar(SQL de aristas, salida, destino, K, [opciones])
opcionales: [directed, heuristic, factor, epsilon]
Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
Ejemplo:

De vértice \(6\) a vértice \(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 edges',
  6, 12,
  directed => true, heuristic => 2);
 seq | path_seq | start_vid | end_vid | node | edge | cost | agg_cost
-----+----------+-----------+---------+------+------+------+----------
   1 |        1 |         6 |      12 |    6 |    4 |    1 |        0
   2 |        2 |         6 |      12 |    7 |   10 |    1 |        1
   3 |        3 |         6 |      12 |    8 |   12 |    1 |        2
   4 |        4 |         6 |      12 |   12 |   -1 |    0 |        3
(4 rows)

Uno a Muchos

pgr_aStar(SQL de aristas, salida, destinos, K, [opciones])
opcionales: [directed, heuristic, factor, epsilon]
Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
Ejemplo:

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

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

Muchos a Uno

pgr_aStar(SQL de aristas, salidas, destino, K, [opciones])
opcionales: [directed, heuristic, factor, epsilon]
Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
Ejemplo:

De los vértices \(\{6, 8\}\) al vértice \(10\) en un grafo no dirigido usando la heurística \(4\)

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

Muchos a Muchos

pgr_aStar(SQL de aristas, salidas, destinos, K, [opciones])
opcionales: [directed, heuristic, factor, epsilon]
Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
Ejemplo:

De los vértices \(\{6, 8\}\) a los vértices \(\{10, 12\}\) en un gráfico dirigido con factor \(0.5\)

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

Combinaciones

pgr_aStar(SQL de aristas, SQL de combinaciones, [opciones])
opcionales: [directed, heuristic, factor, epsilon]
Regresa el conjunto de (seq, path_seq, start_vid, end_vid, node, edge, cost, agg_cost)
O CONJUNTO VACÍO
Ejemplo:

Usando una tabla de combinaciones en un grafo dirigido con factor \(0.5\).

La tabla de combinaciones:

SELECT * FROM combinations;
 source | target
--------+--------
      5 |      6
      5 |     10
      6 |      5
      6 |     15
      6 |     14
(5 rows)

La consulta:

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

Parámetros

Columna

Tipo

Descripción

SQL de aristas

TEXT

SQL de aristas como se describe a continuación

SQL de combinaciones

TEXT

SQL de combinaciones como se describe a abajo

salida

BIGINT

Identificador del vértice inicial de la ruta.

salidas

ARRAY[BIGINT]

Arreglo de identificadores de vértices iniciales.

destino

BIGINT

Identificador del vértice final de la ruta.

destinos

ARRAY[BIGINT]

Arreglo de identificadores de vértices finales.

Parámetros opcionales

Columna

Tipo

x Defecto

Descripción

directed

BOOLEAN

true

  • Cuando true el gráfo se considera Dirigido

  • Cuando false el gráfo se considera No Dirigido.

Parámetros opcionales de aStar

Parámetro

Tipo

x Defecto

Descripción

heuristic

INTEGER

5

Número heurístico. Valores válidos 0~5.

  • 0: \(h(v) = 0\) (Utilizar este valor para comparar con pgr_dijkstra)

  • 1: \(h(v) = abs(max(\Delta x, \Delta y))\)

  • 2: \(h(v) = abs(min(\Delta x, \Delta y))\)

  • 3: \(h(v) = \Delta x * \Delta x + \Delta y * \Delta y\)

  • 4: \(h(v) = sqrt(\Delta x * \Delta x + \Delta y * \Delta y)\)

  • 5: \(h(v) = abs(\Delta x) + abs(\Delta y)\)

factor

FLOAT

1

Para la manipulación de unidades. math:factor > 0.

epsilon

FLOAT

1

Para resultados menos restringidos. \(epsilon >= 1\).

Ver heuristicas disponibles y manupulación de factor.

Consultas Internas

SQL aristas

Parámetro

Tipo

x Defecto

Descripción

id

ENTEROS

Identificador de la arista.

source

ENTEROS

Identificador del primer vértice de la arista.

target

ENTEROS

Identificador del segundo vértice de la arista.

cost

FLOTANTES

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

FLOTANTES

-1

Peso de la arista (target, source),

  • Cuando negativo: la arista (target, source) no existe, por lo tanto no es parte del grafo.

x1

FLOTANTES

Coordenada X del vértice source.

y1

FLOTANTES

Coordenada Y del vértice source.

x2

FLOTANTES

Coordenada X del vértice target.

y2

FLOTANTES

Coordenada Y del vértice target.

Donde:

ENTEROS:

SMALLINT, INTEGER, BIGINT

FLOTANTES:

SMALLINT, INTEGER, BIGINT, REAL, FLOAT

SQL Combinaciones

Parámetro

Tipo

Descripción

source

ENTEROS

Identificador del vértice de partida.

target

ENTEROS

Identificador del vértice de llegada.

Donde:

ENTEROS:

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

INTEGER

Valor secuencial a partir de 1.

path_seq

INTEGER

Posición relativa en la ruta. Tiene el valor 1 para el inicio de una ruta.

start_vid

BIGINT

Identificador del vértice inicial. Se devuelve cuando hay varias vetrices iniciales en la consulta.

end_vid

BIGINT

Identificador del vértice final. Se devuelve cuando hay varios vértices finales en la consulta.

node

BIGINT

Identificador del nodo en la ruta de start_vid a end_vid.

edge

BIGINT

Identificador de la arista utilizado para ir del node al siguiente nodo de la secuencia de ruta. -1 para el último nodo de la ruta.

cost

FLOAT

Costo para atravesar desde node usando edge hasta el siguiente nodo en la secuencia de la ruta.

agg_cost

FLOAT

Costo agregado desde start_vid hasta node.

Ejemplos Adicionales

Ejemplo 1:

Demostración de ignorar los valores repertidos, y resultado ordenado.

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

Ejemplo 2:

Haciendo vids iniciales los mismos que vids destinos.

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

Ejemplo 3:

Manualmente asignar combinaciones de vértices.

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

Ver también

Índices y tablas