Problem des kürzesten Weges

Das Kürzeste-Wege-Problem ist ein klassisches Algorithmusproblem in der Graphentheorieforschung, das darauf abzielt, den kürzesten Weg zwischen zwei Knoten in einem Graphen (bestehend aus Knoten und Pfaden) zu finden. Das Kürzeste-Wege-Problem ist eines der klassischen Probleme auf dem Gebiet der kombinatorischen Optimierung. Es wird häufig in vielen Bereichen wie der Informatik, der Verkehrstechnik, der Kommunikationstechnik, der Systemtechnik, der Operationsforschung, der Informationstheorie und der Kontrolltheorie eingesetzt. Der Dijkstra-Algorithmus ist ein klassischer Kürzestpfad-Algorithmus.

Zu den spezifischen Formen des Algorithmus gehören: (empfohlenes Lernen: PHP-Video-Tutorial)

Das Problem, den kürzesten Weg vom Startpunkt aus zu bestimmen – das heißt, das Problem, den kürzesten Weg bei gegebenem Startknoten zu finden.

Das Problem, den kürzesten Weg zum Endpunkt zu bestimmen – Im Gegensatz zum Problem der Bestimmung des Startpunkts besteht dieses Problem darin, den kürzesten Weg bei gegebenem Endknoten zu finden. In einem ungerichteten Graphen entspricht dieses Problem vollständig dem Problem der Bestimmung des Startpunkts. In einem gerichteten Graphen entspricht dieses Problem dem Problem der Bestimmung des Startpunkts durch Umkehr der Richtungen aller Pfade.

Das Problem besteht darin, den kürzesten Weg vom Startpunkt zum Endpunkt zu bestimmen, dh anhand des Startpunkts und des Endpunkts den kürzesten Weg zwischen den beiden Knoten zu finden.

Globales Kürzeste-Wege-Problem – Finden Sie alle kürzesten Wege im Diagramm.

Dijkstra-Algorithmus

Der Dijkstra-Algorithmus ist ein klassischer Algorithmus für kürzeste Wege. Seine Grundidee besteht darin, eine Menge S festzulegen, um die Eckpunkte zu speichern, die den kürzesten Weg gefunden haben Der Anfangszustand von S enthält nur den Quellpunkt v. Für vi∈V-S wird angenommen, dass die gerichtete Kante vom Quellpunkt v nach vi der kürzeste Weg ist. In Zukunft wird jedes Mal, wenn ein kürzester Weg v, ..., vk erhalten wird, vk zur Menge S hinzugefügt und der Weg v, ..., vk, vi mit der ursprünglichen Hypothese und der mit verglichen Die kleinere Pfadlänge wird als kürzester Pfad gewählt und der obige Vorgang wird wiederholt, bis alle Eckpunkte in der Menge V zur Menge S hinzugefügt sind. Dieser Algorithmus wird verwendet, um den global optimalen kürzesten Pfad zu finden. Wenn die Anzahl der Netzwerkknoten groß ist und die Anzahl der Netzwerkkanten groß ist, kann der Dijkstra-Algorithmus Probleme nicht lösen Punktbeschränkungen müssen gut erfüllt werden.

Ameisenkolonie-Algorithmus

Der Ameisenkolonie-Algorithmus wurde erstmals 1991 von Dorigo, Maniezzo und Colorni vorgeschlagen. Er basiert auf dem Nahrungssuchverhalten von Ameisen. Durch Untersuchungen wurde herausgefunden, dass Informationen zwischen einzelnen Ameisen durch eine Art Pheromon, sogenannte Pheromone, übertragen werden. Ameisen können beim Gehen die Intensität der umliegenden Pheromone spüren und sich in die Richtung mit hoher Pheromonkonzentration bewegen. Wenn eine Ameise Futter findet, gibt sie Pheromone als Markierung auf dem Weg zurück zum Nest ab Finden Sie entlang dieser Straße Nahrung. Wenn mehrere Ameisen unter den Begleitern Nahrung gefunden haben, die Weglängen jedoch unterschiedlich sind, laufen immer mehr Ameisen pro Zeiteinheit durch den kurzen Weg, da die Zeit, die Ameisen für die Hin- und Rückfahrt benötigen, relativ gering ist Weg, Je stärker die Pheromonkonzentration ist, desto mehr Ameisen werden sich auf dem Weg befinden und nach und nach wird ein optimaler Weg ausgewählt.

Klassifizierung

kann in zwei Unterprobleme unterteilt werden, nämlich das Single-Source-Shortest-Path-Problem und das Shortest-Path-Problem zwischen allen Scheitelpunktpaaren. Ersteres besteht darin, den kürzesten Weg von einem bestimmten Scheitelpunkt zu allen anderen Scheitelpunkten im Diagramm zu finden. Der zweite Algorithmus besteht darin, den kürzesten Weg zwischen jedem Scheitelpunktpaar im Diagramm zu finden . Deutscher Algorithmus usw.

Weitere technische Artikel zum Thema PHP finden Sie in der Spalte PHP-Grafik-Tutorial, um mehr darüber zu erfahren!

Das obige ist der detaillierte Inhalt vonProblem des kürzesten Weges. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!