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.
Deutsche Übersetzung
Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.
Vielen Dank im Voraus.
Dokument erstellt 28/12/2009, zuletzt geändert 26/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/graphes-chemin.html
Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.
- ↑ 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.
Referenzen
INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri
(September 2008)
Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.
