Der kürzeste Pfad zwischen Knoten in einem Graphen kann durch verschiedene Algorithmen (Dikstra, A-Stern usw.) gefunden werden.Was sind die Anwendungen des Shortest-Path-Algorithmus?
Aber welche Anwendungen hat dieses Problem? (Ich kenne schon einige, aber ich würde gerne noch viele Beispiele sehen).
Bitte geben Sie nur eine Bewerbung/Antwort! Erläutern Sie die Anwendung und wie sie in ein Problem mit dem kürzesten Pfad umgewandelt werden kann.
ein Netzwerk von Computern gegeben (zB eine Peer-to-Peer-Anwendung), den kürzesten Weg von Maschine A zu Rechner B
SLaks, aber warum brauchen Sie in einer Peer-to-Peer-Anwendung den kürzesten Pfad? – skanatek
In einer Peer-to-Peer-Anwendung sind die beiden Maschinen nicht unbedingt über eine einzige Verbindung verbunden. Alle Verbindungen durchlaufen ein anfängliches Gateway und dann viele zwischen Routern oder Switches, die im Wesentlichen ein Netzwerk bilden. Hier kommt der kürzeste Weg Algo. –
eine Reihe von Städten mit Autobahnen Da findet sie verbinden, den kürzesten Weg finden von New York nach Chicago.
Der Verkehr und die Länge der Autobahnen sind Pfadgewichte.
Dies kann auch für verschiedene Computerspiele verwendet werden. – SLaks
In Videospielen werden diese Algorithmen häufig verwendet, um den kürzesten Pfad zwischen zwei Punkten auf einer Karte zu finden. "Pathfinding", wie es in diesem Zusammenhang genannt wird, kann von AI zum Zeichnen von Routen oder von der Spiel-Engine verwendet werden, um Benutzern beim Plotten von Routen zu helfen.
Ein Beispiel, dass ich es wahrscheinlich verwendet wird, ist in voreingestellten Punkten Geräte, die durch bestimmte Punkte mit einer bestimmten Menge an Batterieladung oder Kraftstoff fahren müssen.
In der Armee haben wir bestimmte kleine unbemannte Luftfahrzeuge/Geräte, die einen vorgegebenen Punkt haben, den es zu erkunden gilt, und da es sehr weit reisen muss, wäre es auf einem kleinen Gerät zu teuer um es über Satellit zu steuern, und die Funksteuerung würde sich verschlechtern, bevor sie den weitesten Punkt erreicht. Hier kommt der Algorithmus ins Spiel.
Setzen Sie einfach einen Punkt, den Sie die Sache suchen und freigeben möchten. Lassen Sie es den kürzesten Weg finden, um alle Punkte abzudecken. Es erfordert keine großen Werkzeuge, daher ist es erschwinglicher und tragbarer.
Das ist Reiseverkäufer, nicht der kürzeste Weg. – SLaks
ts ist ein sp-Klasse-Problem obwohl –
Was ist ein "SP-Klasse-Problem"? –
Social Network ... den kürzesten Weg zwischen zwei Personen (Abscheidegrad) finden
Das klingt wirklich interessant! Aber woran könnte das gewöhnt sein? – BlackBear
Sie wissen in linkedIn, sie bieten, dass eine Person Ihre 2. Verbindung oder 3. Verbindung ist, dort 2 ist der kürzeste Weg von Ihnen zu dieser Person. –
Gezeigt, dass jedes Volk in Amerika mit 6 Beziehung miteinander verwandt sind :) –
Kürzester Weg Probleme bilden die Grundlage für eine ganze Klasse von Optimierungsproblemen, die durch eine Technik gelöst werden können genannt Spalte Generation. Beispiele umfassen Vehikel-Routing-Problem, überlebbares Netzwerk-Design-Problem, unter anderem. Bei solchen Problemen gibt es ein Masterproblem (normalerweise ein lineares Programm), in dem jede Spalte einen Pfad darstellt (man denke an einen Pfad in einem Fahrzeugroutingproblem als eine Kandidatenroute, die ein Fahrzeug nehmen kann, denke an einen Pfad in einem Netzwerk) Designproblem als eine mögliche Route, über die eine Ware zwischen einer Quelle und einem Ziel gesendet werden kann). Das Master-Problem wird wiederholt gelöst. Jedes Mal, wenn die Metriken der Lösung verwendet werden, wird ein separates Problem (das Spaltenuntergenerierungsproblem genannt) gelöst. Dieses Problem stellt sich als ein Problem des kürzesten Pfades heraus (normalerweise mit Seitenbeschränkungen oder negativen Bogenlängen, die das Problem NP-Hard darstellen). Wenn ein neuer nützlicher Pfad erhalten wird, wird er zu dem ursprünglichen Master-Problem hinzugefügt, das nun über eine größere Teilmenge von Pfaden wieder aufgelöst wird, was zu immer besseren (kostengünstigeren) Lösungen führt.
Danke, ich googelte "Spalte Generation" und fand ein Buch über das Thema ... – ragnarius
Kürzeste Pfadalgorithmen können verwendet werden, um word ladder puzzles zu lösen.
Zum Beispiel ändern das Wort „Katze“ in das Wort „Hund“ durch einen Buchstaben zu einem Zeitpunkt, zu ändern - „Katze“, „Fledermaus“, „Tasche“, „Moor“, „Hund“
Es gibt eine interessante, nicht direkt offensichtliche Anwendung der Algorithmen für den kürzesten Weg, die wahrscheinlich häufig im algorithmischen Handels- und Finanzsektor verwendet werden, der sich mit dem Handel von Vermögenswerten und Gütern beschäftigt.
Stellen Sie sich vor, Sie könnten 1000 USD in 950 EUR umwandeln und dann 950 EUR in 1020 CAD, die Sie wieder in 1007 USD umrechnen :) Nur durch die Konvertierung von Währung zu Währung können Sie Geld verdienen.
Diese Situation wird als Arbitragemöglichkeit bezeichnet. Dies kann mit jedem Vermögenswert und zwischen verschiedenen Märkten geschehen.
In diesem Fall werden die Beziehungen zwischen den Assets als gerichteter kantengewichteter Graph modelliert, und das Auffinden sogenannter negativer Zyklen im Graphen ergibt diese Arbitrage-Möglichkeiten.
Sie können weitere Details mit schönen Erklärung und Beispiele siehe hier: http://algs4.cs.princeton.edu/44sp/
Der kürzeste Weg oft in SNA (Social Network Analysis) verwendet wird Between Zentralität unter anderem zu berechnen. Gewöhnlich neigen Menschen mit den stärksten Bindungen dazu, auf dem kürzesten Weg zu kommunizieren. Wenn Sie in einem Graphen wissen, dass der kürzeste Weg zwischen Menschen (Knoten) Ihnen verborgene starke Bindungen zeigen kann. Sie können viele interessante Dinge in einem Diagramm entdecken, indem Sie einfach einige Metriken berechnen.
Sie könnten Ihren Weg nach Hause mit weniger Bars finden, und vermeiden Sie es. –