pgr_astar - Plus court chemin A*¶

Nom¶

pgr_astar — Retourne le plus court chemin en utilisant l’algorithme A*.

Synopsis¶

L’algorithme A* (prononcé “A Etoile”) est basé sur l’algorithme de Dijkstra avec une heuristique qui autorise de résoudre la plupart des problèmes de plus court chemin par l’évaluation de seulement d’un sous-ensemble du graphe général. Retourne un ensemble de lignes pgr_costResult (seq, id1, id2, cost), qui fabriquent un chemin.

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

Description¶

sql:

une requête SQL, qui devrait retourner un ensemble de lignes avec les colonnes suivantes :

SELECT id, source, target, cost, x1, y1, x2, y2 [,reverse_cost] FROM edge_table

id:	`int4` identifiant de l’arête
source:	`int4` identifiant du sommet source
target:	`int4` identifiant du sommet cible
cost:	`float8` valeur, du coût de l’arête traversée. Un coût négatif va prévenir l’arête d’être insérée dans le graphe.
x1:	`x` coordonnée du point de départ de l’arête
y1:	`y` coordonnée du point de départ de l’arête
x2:	`x` coordonnée du point final de l’arête
y2:	`y` coordonnée du point final de l’arête
reverse_cost:	(optionnel) le coût pour la traversée inverse de l’arête. Ceci est seulement utilisé quand les paramètres `directed` et `has_rcost` sont `true` (voir la remarque ci-dessus sur les coûts négatifs).

source:

int4 id du point de départ

target:

int4 id du point final

directed:

true si le graphe est dirigé

has_rcost:

si true, la colonne reverse_cost du SQL générant l’ensemble des lignes va être utilisé pour le coût de la traversée de l’arête dans la direction opposée.

Retourne un ensemble de pgr_costResult[]:

seq:	séquence de ligne
id1:	ID noeud
id2:	ID arête (`-1` pour la dernière ligne)
cost:	coût pour traverser à partir de `id1` en utilisant `id2`

Histoire

Renommé depuis la version 2.0.0

Exemples¶

Sans reverse_cost

SELECT seq, id1 AS node, id2 AS edge, cost
        FROM pgr_astar(
                'SELECT id, source, target, cost, x1, y1, x2, y2 FROM edge_table',
                4, 1, false, false
        );

 seq | node | edge | cost
-----+------+------+------
   0 |    4 |   16 |   1
   1 |    9 |    9 |   1
   2 |    6 |    8 |   1
   3 |    5 |    4 |   1
   4 |    2 |    1 |   1
   5 |    1 |   -1 |   0

(4 rows)

Avec reverse_cost

SELECT seq, id1 AS node, id2 AS edge, cost
        FROM pgr_astar(
                'SELECT id, source, target, cost, x1, y1, x2, y2, reverse_cost FROM edge_table',
                4, 1, true, true
        );

 seq | node | edge | cost
-----+------+------+------
   0 |    4 |    3 |    1
   1 |    3 |    2 |    1
   2 |    2 |    1 |    1
   3 |    1 |   -1 |    0
(4 rows)

Les requêtes utilisent le réseau Données d’échantillon.

pgRouting Manual (2.0.0)