Chemins extrémaux des graphes pondérés
Les pages suivantes décrivent certains algorithmes utilisés pour trouver des chemins extrémaux dans un graphe (pathfinding).
Selon les données que nous possédons sur le graphe de départ, nous devrons sélectionner quel algorithme exécuter, en fonction de ses possibilités et de ses performances.
Typologie des problèmes
En fonction des données du graphe de départ, nous pouvons donc formuler un certain nombre d'hypothèses parmi celles évoquées ci-dessous.
H1 : Graphe orienté
L'hypothèse H1 présume que le graphe est orienté. Il s'agit presque d'un axiome, car nous pouvons considérer tout graphe non orienté comme un graphe orienté symétrique1.
H2 : Chemin minimum
Ce que nous recherchons le plus souvent comme chemin dans un graphe, c'est le chemin de poids (de coût) minimum. Parfois, il est nécessaire de chercher le chemin de poids maximum (par exemple dans le cas d'un gain).
Dans nos exemples d'algorithmes de recherches de chemins extrémaux, nous prendrons la convension de rechercher le chemin minimum.
H3 : Graphes simplement connexes
L'hypothèse H3 présume que le graphe est simplement connexe.
H4 : Pas de boucles
L'hypothèse H4 présume que le graphe ne contient pas de boucles.
H5 : Racine
L'hypothèse H5 présume que le graphe possède une racine, qui est le point de départ de notre chemin.
Si notre graphe ne possède pas de racine (ou s'il possède plus d'une racine), nous pouvons ajouter un sommet de départ, qui deviendra notre racine. Nous devons alors relier ce sommet à tout sommet candidat racine (sommet racine, ou sommet isolé) par un arc de poids zéro.
H6 : Pas de circuit absorbant
L'hypothèse H6 présume que le graphe ne possède pas de circuit absorbant2. Un circuit absorbant n'est pas borné, et il tend à l'infini.
Classification des algorithmes
En fonction des différentes hypothèses que nous pouvons formuler à propos d'un graphe, nous pouvons orienter notre choix d'algorithme à utiliser.
Circuits - Absence de circuit. Exemple : l'algorithme de Moore-Dijkstra retourne un chemin qui n'est pas optimum si nous n'avons pas de circuit.
- Présence de circuit. Exemple : on ne peut pas utiliser l'algorithme de Bellman-Kalaba.
- Poids quelconques. Le marquage ne peut plus être définitif. Exemples :
l'algorithme de Ford-Bellman utilise la méthode d'ajustement progressif.
l'algorithme de Bellman-Kalaba fonctionne quand-même si le graphe ne comporte pas de circuit.
l'algorithme de Moore-Dijkstra ne fonctionnera pas en présence d'arcs de poids négatifs3. - Poids positifs ou nuls. Exemple : l'algorithme de Moore-Dijkstra3.
- Poids tous égaux. Exemple : l'algorithme de Moore-Dijkstra modifié4.
- Un chemin minimal entre la racine (départ) et le sommet d'arrivée5.
- Un chemin minimal entre la racine (départ) et chacun des autres sommets6.
- Un chemin minimal entre chaque couple de sommets7.
Nederlandse vertaling
U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.
Bij voorbaat dank.
Document heeft de 28/12/2009 gemaakt, de laatste keer de 26/10/2018 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/graphes-chemin.html
De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.
- ↑ Orienté symétrique : Nous pouvons remplacer chaque arête d'un arc non orienté par deux arcs aux directions oposées.
- ↑ Circuit absorbant : Un circuit absorbant, dans le cas d'un chemin minimal, est un circuit pour lequel chaque passage diminue le poids du chemin. C'est le contraire pour un chemin maximal.
- ↑a,b Moore-Dijkstra & poids négatifs : L'algorithme de Moore-Dijkstra ne permet pas la présence de pondération négative dans notre exemple car nous sommes à la recherche de chemin extrême minimum. Dans le cas de la recherche d'un chemin extrême maximum avec l'algorithme de Moore-Dijkstra le graphe ne peut contenir aucun arc de pondération positive, et nous devons légèrement modifier le pseudo code.
- ↑ Moore-Dijkstra modifié : Dans la version modifiée de l'algorithme de Moore-Dijkstra, nous utilisons un ensemble de sommets marqués simultanément lors d'une seule itération.
- ↑ Racine -> arrivée : Algorithme heuristique A* si la destination est préalablement déterminée, mais chaque algorithme de type racine -> ∀sommet convient.
- ↑ Racine -> ∀sommet : En général, ce type d'algorithme n'est pas plus compliqué qu'un algorithme racine -> arrivée.
- ↑ ∀sommet -> ∀sommet : Algorithmes qui utilisent une matrice mise à jour au cours d'itérations successives.
Referenties
INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri
(September 2008)
Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.
