Kürzesten Weg zwischen zwei Punkten?

00Albert

Hi,

ich hab eine Tabelle (Excel) in der Punkte hinterlegt sind und deren Verbindung zu anderen Punkten, also sowas ähnliches wie eine Karte. Was dabei nicht zum tragen kommt ist die Entfernung zwischen den Punkten.

Wenn ich nun den kürzesten Weg zwischen zwei Punkten Herausfinden will, wie würde man das am geschicktesten durchführen? Gibts da bereits Algorithmen die sowas abbilden?

Grüße

00Albert schrieb:

Hi,

ich hab eine Tabelle (Excel) in der Punkte hinterlegt sind und deren Verbindung zu anderen Punkten, also sowas ähnliches wie eine Karte. Was dabei nicht zum tragen kommt ist die Entfernung zwischen den Punkten.

Wenn ich nun den kürzesten Weg zwischen zwei Punkten Herausfinden will, wie würde man das am geschicktesten durchführen? Gibts da bereits Algorithmen die sowas abbilden?

Grüße

Auf Deutsch: du hast einen Graph. Dafür gibt es viele Algorithmen, das einfachste wäre wohl eine Tiefensuche, wobei du immer den aktuell kürzesten gefundenen Weg speicherst.

icarus2

Es ist nicht einfach eine gute Antwort zu geben mit den bisherigen Informationen.

Offensichtlich hast du einen Graphen. Die Punkte in der Excel Tabelle sind Knoten des Graphen und die Kanten sind Verbindungen zu anderen Punkten.

Sind alle Verbindungen gleich lang? Oder gibt es unterschiedlich lange Verbindungen? Ist der Graph gerichtet oder nicht (das heisst, wenn man vom Punkt x zu Punkt y kann, kann man dann umgekehrt auch von y nach x)?

00Albert

Also die Entfernungen zwischen den Punkten sind immer gleich lang und man kann in jede Richtung gehen. Würde man die Punkte grafisch verbinden hätte man eine Art Netzwerk. Es ist aber nicht so, das jeder Punkt jeden verbindet.

Vielleicht kann das es etwas illustrieren was ich da habe:

o
  |
o-o-o-o-o
  | |
  o-o-o

icarus2

Ich bin mir noch immer nicht ganz sicher wie der Graph deines Problems genau aussieht. Aber schau dir einmal den Dijkstra Algorithmus und den Algorithmus von Floyd und Warshall an.

Mit diesen loest man normalerweise kuerzeste Wege Probleme.

*Edit
Ich denke der Dijkstra Algorithmus ist etwas einfacher zu verstehen. Fuer den Floyd und Warshall zu verstehen braucht man Dynamische Programmierung.

Jester

Wenn alle Kantenlängen gleich sind reicht eine Breitensuche.

icarus2

Jester schrieb:

Wenn alle Kantenlängen gleich sind reicht eine Breitensuche.

Ich war mir zu Beginn etwas unsicher, ob das wirklich immer zum kuerzesten Weg fuehrt. Aber ich habs mir kurz durchgedacht und man kann es so machen.

00Albert

Ich hab mir das mal in der Wiki angesehen, klingt irgendwie logisch was da passiert. Mal sehen ob ich das irgendwie ins Excel abgebildet bekomme.

icarus2

00Albert schrieb:

Ich hab mir das mal in der Wiki angesehen, klingt irgendwie logisch was da passiert. Mal sehen ob ich das irgendwie ins Excel abgebildet bekomme.

In deinem spezifischen Fall ist aber Jesters Loesung am besten. Ist weitaus am einfachsten zu implementieren und duerfte auch am effizientesten sein.

00Albert

Ich hab mal versucht die Breitensuche in Excel nachzuempfinden. Ich bin soweit, das ich zum Ergebnis komme, das es einen Weg gibt der Start und Ende verbindet aber ich versteh nicht wie man das so abbildet, das man auch die nötigen Knoten Abspeichert die man abläuft um ins Ziel zu kommen.

Das Makro macht folgendes:

Suchen des Startknotens in der Matrix
Kopieren der Matrixzeile in die Arbeitstabelle Zeile 1

Wiederhole bis Nachbarknoten des gleich Endeknoten ist
  Wiederholung bis alle Nachbarknoten des Knotens geprüft wurden
    Auslesen der des Nachbarknotens aus der Matrixzeile
    Suchen des Nachbarknotens in der Matrix
    Kopieren der Matrixzeile in die Arbeitstabelle Zeile + 1

Das ergibt dann halt eine Liste in der alle Knoten drin sind die betrachtet wurden und am Schluss halt den Endknoten, mit dem das Makro terminiert.

In der Wiki ist ein Phyton Beispiel, das versteh ich aber nicht, da mir nicht klar ist wie die da ihre Daten speichern und auswerten.

Habt ihr da eine Idee?

Grüße

Michael E.

Merke dir für jeden Knoten den Vorgänger und baue dir den Weg nachher rückwärts wieder auf.

00Albert

Hm, also ich hab ein wenig das Gefühl sowas geht mit Excel VBa nicht richtig oder ich weiß nicht wie.

Ich hab ja in einer zweiten Tabelle die ganzen relevanten Knoten mit deren Nachbarn. Da sind nun aber neben den nötigen Knoten auch alle anderen Knoten drin die Nachbar sind, weil die ja auch geprüft wurden.

Beispiel:

Das Kommt raus, wenn der Weg von 3 nach 8 gesucht wird. die erste Spalte sind die Knoten und die nachfolgenden die Nachbarn, wobei 0 zum auffüllen ist und keine Verbindung bedeutet.

Grüße

inflames2k

Aus deiner Ergebnismenge lässt sich doch etwas ableiten. Ich hab jetzt keine Ahnung von Tiefen und Breiten-Suche. Aber ich denke, folgender Weg sollte entsprechend der kürzeste von 3 bis 8 sein:

3-5-8

Ums nachzuvollziehen die relevanten Stellen hervorgehoben:

3 1 2 4 5
1 3 0 0 0
2 3 0 0 0
4 3 6 0 0
5 3 8 6 0
6 4 5 7 9
8 5 10 0 0

00Albert

Ja das ist schon klar das das der kürzeste Weg ist aber wie bring ich das der Maschine bei, bzw. das die mir das auch so ausgibt?

00Albert

Wasn Krampf aber ich hab jetzt Excel dazu gebracht rückwärts den Weg zusammenzubauen.

Jetzt würde mich aber noch interessieren wie soll man das bewerten wenn es mehrere Möglichkeiten gibt zum Endknoten zu kommen.

z.B.:

Start ist 1 und Ende ist 4.

1 - 2
|   |
3 - 4

Formal sind die Wege ja gleichwertig, da ich keine Kanten bewerte.

Grüße

icarus2

Schau dir nochmal die Breitensuche (sollte man unbedingt kennen) an fuer einen Graphen. Die ist wirklich nicht schwierig zu verstehen und damit kann man sehr leicht einen der kuerzesten Wege finden (der ist ja wie du bemerkt hast nicht immer eindeutig).

Unter Wikipedia - Breitensuche findest du Erklearungen sowie einen informellen und einen formalen Beschreib des Algos.

xroads42

welcher raum?

geeky

00Albert schrieb:

Formal sind die Wege ja gleichwertig, da ich keine Kanten bewerte.

Wenn man die Knoten durchnummeriert hat nimmt man häufig von den gleichwertigen Wegen einfach den, der über die kleineren Nummern wandert (Also 1-2-4 würde bei deinem Beispiel vor 1-3-4 bevorzugt) - oder halt einfach einen beliebigen