pgRouting Manual (2.0.0)

pgr_astar - Plus court chemin A*

«  pgr_apspWarshall - Plus court chemin toutes paires, Algorithme Floyd-Warshall   ::   Contenu   ::   pgr_bdAstar - plus court chemin bidirectionnel A*  »

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.

«  pgr_apspWarshall - Plus court chemin toutes paires, Algorithme Floyd-Warshall   ::   Contenu   ::   pgr_bdAstar - plus court chemin bidirectionnel A*  »