# Algorithmus für kürzesten Weg mit Wegpunkten



## Laurin (30. Apr 2011)

Hallo,

ich habe ein Problem mit meinen Funktionen, die den kürzesten Weg durch ein Netz von Nodes finden sollen. Der Abstand von einem Node zu einem Nachbarn ist immer identisch, also es zählen nur die Anzahl der Schritte bzw. die Anzahl der Nodes im Pfad.

Ein Node besitzt ein Set von Nodes, das seine direkten Nachbarn enthält.

Die Funktion, die nur die kürzeste Strecke zwischen Start- und End-Node bestimmt funktioniert ohne Probleme:


```
private void followPath(Node pos) {
    testRoute.add(pos);
    // Wenn Route schon länger als die kürzeste Route ist
    if (testRoute.size() >= shortestRoute.size() && shortestRoute.size() > 0) {
      testRoute.removeLast();
      return;
    }
    
    // Wenn der End-Node erreicht wurde und die Route die bis jetzt kürzeste ist.
    if (pos.equals(endNode)) {
      if (testRoute.size() < shortestRoute.size() || shortestRoute.size() == 0) {
        shortestRoute = new LinkedList<Node>(testRoute);
      }
      testRoute.removeLast();
      return;
    }
    // Gehe in alle Nachbarn, die noch nicht auf der Route liegen
    for (Node neighbor : pos.getNeighbors()) {
      if (!testRoute.contains(neighbor)) {
        followPath(neighbor);
      }
    }
    
    testRoute.removeLast();
    return;
  }
```

Die funktion wird mit dem Start-Node aufgerufen.

Das Problem ist die Funktion, bei der Wegpunkte angegeben sind, die passiert werden müssen.
*Dabei muß für ein passieren der Node nicht betreten werden. Ein Node soll auch als passiert gelten, wenn er direkt neben der Route liegt, also ein Nachbar eines Elementes der Route ist.*

So habe ich es probiert:


```
private void followPathInclude(Node pos) {
    testRoute.add(pos);
    // In newlyPassed werden die Nodes gespeichert, die bei betreten des neuen Nodes passiert
    // werden und die vorher noch nicht passiert waren. Beim "Zurückziehen" vom Pfad werden diese
    //dann aufgeräumt.
    HashSet<Node> newlyPassed = new HashSet<Node>();
    if (include.contains(pos) && !passed.contains(pos)) {
      newlyPassed.add(pos);
      passed.add(pos);
    }
    for (Node neighbor : pos.getNeighbors()) {
      if (include.contains(neighbor) && !passed.contains(neighbor)) {
        newlyPassed.add(neighbor);
        passed.add(neighbor);
      }
    }
    // Nötige Abbruchbedingung, da die Bedingung, daß ein Node nur einmal im Pfad auftauchen darf
    // wegfallen muß
    if (testRoute.size() > this.maxLength) {
      testRoute.removeLast();
      passed.removeAll(newlyPassed);
      return;
    }
    // Wenn Route schon länger als die kürzeste Route ist
    if (testRoute.size() >= shortestRoute.size() && shortestRoute.size() > 0) {
      testRoute.removeLast();
      passed.removeAll(newlyPassed);
      return;
    }
    // Wenn der End-Node erreicht wurde, die Route die bis jetzt kürzeste ist und alle zu passierenden
    // Nodes (Set include) passiert wurden (Set passed)
    if (pos.equals(endNode)) {
      if (passed.containsAll(include)) {
        if (testRoute.size() < shortestRoute.size() || shortestRoute.size() == 0) {
          shortestRoute = new LinkedList<Node>(testRoute);
          testRoute.removeLast();
          passed.removeAll(newlyPassed);
          return;
        }
      } 
    }
    // Diesmal müssen alle Nodes begangen werden, da Mehrfachvorkommen im Pfad nötig sein kann
    for (Node neighbor : pos.getNeighbors()) {
        followPathInclude(neighbor);
    }
    
    testRoute.removeLast();
    passed.removeAll(newlyPassed);
    return;
  }
```

Die maximale Länge habe ich auf ((Anzahl aller existierenden Nodes) - 2) * 2 begrenzt.
Das Problem ist, daß er manchmal einfach nicht fertig wird mit der Berechnung, er probiert ja alle möglichen Routen durch, um vllt. doch noch eine kürzere zu finden.
Mein Test-Netz hat 44 Knoten, wenn ich da zB 6 Wegpunkte angebe hat er das Ergebnis schon nach ein paar Sekunden. Wenn ich im sage, er soll alle 44 Knoten passieren, war er nach 20 Minuten noch nicht fertig. Das ist nicht akzeptabel, da es später mit ca. 1000 Nodes insgesammt und 0-1000 Wegpunkten funktionieren muss.

Ich brauche drigend eine Lösung dafür...

Vielen Dank
Laurin


----------



## TheDarkRose (30. Apr 2011)

Kennst du den A* Algorythmus? Da deine Nodes alle dieselben Kosten haben, dürfte der sogar vereinfacht auch funktionieren.


----------



## Laurin (30. Apr 2011)

Den A*-Algorithmus konnte ich bis jetzt noch nicht anpassen, daß er Start- und Endpunkt als wirklich zu betretende Punkte nimmt aber an Wegpunkten nur vorbeigehen und diese nicht betreten muß...


----------



## ice-breaker (30. Apr 2011)

Klingt ein wenig nach dem Königsberger Brückenproblem, vllt findest du in diese Richtung etwas.


----------



## Laurin (30. Apr 2011)

Das Brückenproblem hat nichts mit dem finden der kürzesten Route zu tun, sondern damit, ob es eine Route gibt, bei dem jeder Node genau einmal betreten wird (Eulerweg).

Im vorliegenden Fall ist es aber erstens egal, ob ein Node mehrfach betrten wird (muß er zwangsweise bei Sackgassen-Strecken) und zweitens ob ein Node gar nicht betreten wird, solange alle Wegpunkte passiert werden (zB. ein Sackgassenende-Wegpunkt sollte nie in der Route vorkommen, da er schon durch den Vorgänger als passiert zählt).


----------



## ice-breaker (30. Apr 2011)

Laurin hat gesagt.:


> Im vorliegenden Fall ist es aber erstens egal, ob ein Node mehrfach betrten wird



es klang so, als ob die Wegpunkte nur einmal betreten werden sollen


----------



## Laurin (30. Apr 2011)

Die Wegpunkte sollen gar nicht betreten werden, sie sollen nur am Weg liegen (wobei es aber auch nicht falsch ist, falls sie doch genau auf dem Weg liegen, halt so, wie es am kürzesten ist).


----------



## TheDarkRose (30. Apr 2011)

Wie meinst du das, mit am weg liegen?


----------



## Laurin (30. Apr 2011)

So wie ich das im ersten Post geschrieben habe:
*Dabei muß für ein Passieren der Node nicht betreten werden. Ein Node soll auch als passiert gelten, wenn er direkt neben der Route liegt, also ein Nachbar eines Elementes der Route ist.*


----------



## DarkLegend (30. Apr 2011)

Nun ich vermute dass es keinen klassischen Algorithmus für dein Problem finden wirst.
Dass die Knoten auch am Rande liegen dürfen, macht es sicherlich immer kaputt 

Vielleicht hilft dir auch der Dijkstra-Algorithmus. (oder so. da war mal was im Studium mit Graphen und so)

Kannst evtl nach dem Workaround suchen. Eine spontane idee wäre eine Zwischenschicht einzuziehen, die Knoten nicht als einzelne Punkte, sondern als Summe des Knotens + allen Nachbarn representiert.

und und wenn du jetzt zum Punkt 1/1 willst, suchste alle Knoten, die diesen 1/1 enthalten und kannst darüber z.B. den Dijkstra füttern.

Aber nur ne spontane Idee ohne lange drüber nachgedacht zu haben


----------



## Laurin (30. Apr 2011)

Das Problem ist einfach, daß ich zu wenig Rechenleistung habe. Ein Ergebnis würde der Algorithmus liefern.
Meine Implementierung basiert ja von der Idee auf dem Dijkstra-Algorithmus. Ich brauche da ja keine Längen, weil die Kantenlänge konstant ist.

Was zum gleichen Ergebnis führt, ist das Berechnen der kürzesten Strecken von einem Wegpunkt zum nächsten (bzw. bis man bis auf einen Node am WP dran ist) und anschließendes Zusammensetzen der einzelnen Strecken.
Das habe ich dann für alle Permutationen der Wegpunkte gemacht und dann die Permutation mit der insgesammt kürzesten Route bestimmt.

Dabei sieht man auch die Komplexität des Problems, bei n Wegpunkten neben Start und Endpunkt erhält man n! Permutationen. Bei jeder Permutation müssen n+1 kürzeste Wege berechnet werden. Also werden insgesammt (n+1)! kürzeste Wege berechnet. Die komplexität mit der vorherigen permutation ist in etwa die selbe, wie wenn ich mit dem ersten Ansatz alle möglichen Pfade im Netz durchgehe (entweder keine Permutation, aber dafür eine sehr tiefe Rekursion oder Permutation mit vielen, aber flachen Rekursionen).

Daraus folgt, bei meinem Testnetz mit 44 Nodes komme ich, wenn ich den kürzesten Weg über alle Nodes wissen will auf 44! = 2,7*10^54 Permutationen und es werden 1,2*10^56 kürzeste Wege berechnet.
Bei den gewünschten 1000 Wegpunkten bin ich bei Potenzen im Bereich von 10^2500...

Ich hatte mir überlegt, alle kürzesten direkten Routen die es gibt zwischenzuspeichern, das sind (n*(n+3))/2.
Bei 1000 Nodes wären das ungefähr 500000 Routen.

Ich weiß aber noch nicht, wie mir das weiterhilft, denn so kriege ich zwar schnell (oder vermutlich auch langsam, da ich denke daß das Einlesen vom Dateisystem länger dauert als die Routen zu berechnen, das sind ja immerhin 500000 LinkedLists) die kürzesten Routen von einem Node zu jedem anderen Node, aber ich müßte sie dann wiederum alle permutieren, um die Kombination der kürzesten direkten Routen zu finden, die die kürzeste Gesamtroute bildet...

Edit:
Bis zu 8 Wegpunkte kann man noch gut berechnen, da braucht es bis zu 300MB Ram und es dauert ein paar Sekunden, bei 9 WP schon 450, aber der kommt auch nach einer Minute noch nicht zu einem Ergebnis und bei 10 WP werden schon 2GB Ram verbraucht während er rechnet...


----------



## DarkLegend (30. Apr 2011)

"Besser fährt man hier mit der Verwendung der Datenstruktur Fibonacci-Heap. Diese ermöglicht es ebenfalls, die Operationen insert, empty und decreaseKey (amortisiert betrachtet) in \mathcal{O}(1) zu realisieren, die Komplexität von extractMin ist hier \mathcal{O}(\log n). Die gesamte Laufzeit beträgt dann lediglich O (n*log n + m)
Aus Wikipedia  zum Dijkstra...
Also irgendwas machst du falsch 
Kannste mal das ganze Programm hochstellen, dass ich mir keine Main zusammen zimmern muss? Finde das Problem ganz spannend.


----------



## Laurin (30. Apr 2011)

Ich habe das Projekt angehängt.
Der Eintrag bei Wikipedia bezieht sich so wie ich das sehe nur auf das finden der kürzesten Route von A nach B, nicht von A nach B vorbei an 1000 Wegpunken


----------



## Landei (30. Apr 2011)

Ich habe mir deinen Code nicht angeschaut, aber wäre das kein Fall für "teile und herrsche"? Nimm den "mittleren" Wegpunkt M. Bestimme alle kürzesten Strecken von A nach M und seinen Nachbarn. Bestimme alle kürzesten Wege von M und seinen Nachbarn nach B. Wiederhole dazu das Verfahren rekursiv für alle Teilstrecken.


----------



## Logaff (1. Mai 2011)

ich würd sagen du guckst mal nach "Problem des Handlungsreisenden", dauert natürlich enormst lange bei 44 Knoten, bzw 1000 Knoten. es gibt verschiedene möglichkeiten annährend den kürzesten weg zu finden, zb aussgehend vom startpunkt immer die längsten wege gehen bzw immer die kürzesten wege

Lektüre Verweis

wer will kann ALLE Ausgaben vom "Algorithmus der Woche" als pdf haben, hab sie aufn Rechner (alle von der Webseite gezogen)

edit: wenn ich mich recht an mein bio unterricht vor 5 wochen erinnere, bin ich zum entschluss gekommen das es (n-1)! wege gibt und bei 1000 Punkten ist das schon enorm


----------



## Laurin (2. Mai 2011)

Das Problem ist eben, daß die schnellen Methoden nicht unbedingt die kürzeste Route finden. Die MST-Heuristik beim Traveling-Salesman-Problem liefert zB eine Route, die nicht mehr als doppelt so lang ist wie die tatsächlich kürzeste Route.
Und eine "einigermaßen kurze" Route finde ich auch in 5 Minuten, wenn ich mir das Netz selbst ansehe und mit Bleistift und Zettel ein paar vielversprechende Routen abzähle...

Bis jetzt habe ich noch keine Lösung gefunden, die die sicher kürzeste Route findet und dabei zB linear skaliert.
Die einzige Möglichkeit, die ich bis jetzt sehe, ist die Berechnung auf 5-6 Wegpunkte zu beschränken und bei mehr Wegpunkten diese manuell zu verschieben (evtl. mit Gruppen und Zwischenzielen). Das wäre eine Art manuelles Divide & Conquer.

Ein automatisches Divide & Conquer ist deshalb nicht möglich, da die Reihenfolge der Wegpunkte ungeordnet ist. Beispiel:
Ich habe einen Startpunkt S, einen Endpunkt E und 10 Wegpunkte W1-W10. Aus den Wegpunkten nehme ich mir jetzt W5 heraus und teile das Problem in S -> (W1-W4) -> W5 und W5 -> (W6-W10) -> E auf. Die beiden Teilprobleme sind jetzt im schnell lösbaren Bereich. Aber es findet nich unbedingt die schnellste Strecke, da ich zufällig bestimme, das W1-W4 vor W5 und W6-W10 nach W5 auf der Route liegen. Die tatsächlich kürzeste Route könnte aber S->W10->W1->W9->W2->W8->W3->W7->W4->W6->W5->E sein.
Also müßte ich das Problem wieder rekursiv mit allen Möglichkeiten durchprobieren. Nicht etwa nur 10 Mal für 10 Wegpunkte, sonderen deutlich öfter, da zusätzlich zum "Zwischenpunkt" noch alle Möglichkeiten der anderen Punkte (vor oder hinter dem "Zwischenpunkt) probiert werden müssen. Also wären wir wieder genau bei allen Permutationen der Wegpunkte.


----------



## DarkLegend (2. Mai 2011)

Naja du berechnest halt jede Menge Overhead mit den Permutationen...
 wenn du z.B. 1-->2-->3-->4 ausrechnest... und danach 2-->1-->3-->4 dann haste 3 nach 4 doppelt gerechnet.
je mehr Wegpunkte, desto größer der Overhead.
Evtl. macht es mehr Sinn zunächst eine Matrix mit den Abständen aller Wegpunkten (und deren Nachbarn) untereinander zu berechnen
Auf Basis dieser Matrix kannst du danach Summen bilden und den kürzesten Weg recht easy finden.

[Edit] 
Außerdem funktioniert bei dir glaube ich derzeit nicht, dass ein benachbarter Wegpunkt ausreicht, um den Wegpunkt als besucht zu markieren.


----------



## ThreadPool (2. Mai 2011)

Laurin hat gesagt.:


> Bis jetzt habe ich noch keine Lösung gefunden, die die sicher kürzeste Route findet und dabei zB linear skaliert. [...]



Wirst du auch nicht finden denke ich. Wenn ich das richtig verstanden habe entspricht dein Problem bei der Anzahl von 0 Wegpunkten dem einfachen Kürzeste-Wege-Problem, bei exakt so vielen Wegpunkten wie Knoten dem Problem des Handlungsreisenden (NP-hart). Der Rest ist irgendwas dazwischen wobei die Komplexität mit der zunehmender Anzahl der Wegpunkte sehr schnell ansteigt. Bei Näherungslösungen stellt sich dann eben nur die Frage, wenn es in akzeptabler Zeit nicht optimal zu lösen ist wie weit ist es für dich akzeptabel vom Optimum abzuweichen.


----------



## Laurin (2. Mai 2011)

DarkLegend hat gesagt.:


> [Edit]
> Außerdem funktioniert bei dir glaube ich derzeit nicht, dass ein benachbarter Wegpunkt ausreicht, um den Wegpunkt als besucht zu markieren.


Doch, das funktioniert, sowohl mit dem Code aus dem ersten Post als auch mit dem Quelltext.
Beim End-Node wird geprüft, ob der aktuelle Node der End-Node ist; bei Waypoint-Nodes wird geprüft, ob der aktuelle Punkt der Waypoint-Node ist oder ob ein Nachbar des aktuellen Nodes ein Waypoint-Node ist.
Und eventuell wäre es schneller, alle möglichen kürzesten Routen zwischenzuspeichern (hatte ich ja auch schon angesprochen). Da hätte ich dann über 500000 Routen (bei 1000 Nodes). Dazu bräuchte ich dann auch noch eine Kontrollstruktur, die mir aus aus 2 Nodes schnell die entsprechende Route raussucht.
Und das Hauptproblem ist damit immer noch nicht gelöst, denn auch wenn ich die kürzesten Routen schnell habe, muss ich immer noch alle Permutationen von Wegpunkten probieren, um die Gesamt-Kürzeste-Route zu bekommen. Und wenn es im Ende dann statt 5 Jahren nur 3 Jahre dauert, ist mir damit auch nicht geholfen...

Edit:


ThreadPool hat gesagt.:


> Wenn ich das richtig verstanden habe entspricht dein Problem bei der Anzahl von 0 Wegpunkten dem einfachen Kürzeste-Wege-Problem, bei exakt so vielen Wegpunkten wie Knoten dem Problem des Handlungsreisenden (NP-hart).


Es ist sogar noch etwas komplexer als das Problem des Handlungsreisenden. Beim Handlungsreisenden ermittelt man ja eine Rundstrecke, also Start- und Endpunkt sind identisch. Damit ist die Route für jeden Punkt als Start/Endpunkt die selbe, der Startpunkt verschiebt sich, aber die Reihenfolge bleibt gleich.
Hier sind Start- und Endpunkt verschieden (bzw. können verschieden sein). Bei unterschiedlichen Start und Endpunkten kann auch die Reihenfolge variieren.


----------



## MrWhite (2. Mai 2011)

Laurin hat gesagt.:
			
		

> Bis jetzt habe ich noch keine Lösung gefunden, die die sicher kürzeste Route findet und dabei zB linear skaliert.



Wie schon von ThreadPool gesagt, wenn du die kürzeste Route finden willst stehst du vor einem NP Problem und wirst ab einer bestimmten Anzahl von Nodes die kürzesten Routen nicht mehr in adäquater Zeit berechnen können. Das ist nunmal so und du wirst auch keine Lösung finden, die linear skaliert.

Dann helfen nur noch andere Mittel, z.B. heuristische Verfahren oder genetische Algorithmen, die in relativ kurzer Zeit "gute" Lösungen finden.


----------



## Laurin (2. Mai 2011)

MrWhite hat gesagt.:


> Dann helfen nur noch andere Mittel, z.B. heuristische Verfahren oder genetische Algorithmen, die in relativ kurzer Zeit "gute" Lösungen finden.



Und genau dafür brauch ich dann auch keinen Algorithmus mehr, daß sehe ich auch mit bloßem Auge, wie ich zB die Wegpunkte in eine sinnvolle Reihenfolge kriege.
Und wenn ich einfach loslaufe und darauf achte, keine Wege unnötig mehrfach zu gehen, komme ich über alle Punkte in dem Fehlerbereich von heuristischen Algorithmen.


----------



## MrWhite (2. Mai 2011)

Laurin hat gesagt.:


> Und genau dafür brauch ich dann auch keinen Algorithmus mehr, daß sehe ich auch mit bloßem Auge, wie ich zB die Wegpunkte in eine sinnvolle Reihenfolge kriege.
> Und wenn ich einfach loslaufe und darauf achte, keine Wege unnötig mehrfach zu gehen, komme ich über alle Punkte in dem Fehlerbereich von heuristischen Algorithmen.



Wenn du dich da mal nicht täuschst...

Dann machs halt ohne den Computer. Einen Algorithmus mit linearem Laufzeitverhalten wirst du nicht (er-)finden.


----------

