Dijkstra-Algorithmus
[EDIT]Abgetrennt von In einer Switch Anweisung eine Variable verarbeiten?[/EDIT]
Hallo Traumzauberbaum,
das hat jetzt mit dem Thread an sich nichts mehr zu tun, aber wenn Du Dijkstra zitierst, hast Du seinen Algorithmus zur Berechnung kurzer Wege schon mal einsetzen können - ich frag nur interessehalber 🙂
Gruß Hape
Hallo hape,
das hat jetzt mit dem Thread an sich nichts mehr zu tun,
genau, deshalb gehören solche Fragen auch in einen neuen Thread 🙂 ==> abgetrennt.
Ein weiterer alternativer Algorithmus ist der A*-Algorithmus, der den Algorithmus von Dijkstra um eine Abschätzfunktion erweitert. Falls diese gewisse Eigenschaften erfüllt, kann damit der kürzeste Pfad unter Umständen schneller gefunden werden.
meines wissens wird in der Praxis deshalb auch meist A* und nicht der Dijkstra-Algorithmus verwendet. Siehe auch A* (Pathfinding) mit Sechsecken?
Was ist den der Hintergrund deiner Frage?
herbivore
Hallo herbivore,
den Algorithmus kenne ich noch nicht, und mich würde interessieren, in welchem klassischen Anwendungsfall man diesen einsetzt.
Das ist eher so eine Schön-zu-wissen-hat-aber-keinen-konkreten-Anlaß-Frage 🙂
Gruß Hape
Der Dijkstra Algorithmus berechnet eher einen Graphen der kürzesten Wege von einem Startknoten aus. Der A* Algorithmus zielt eher darauf ab nur den kürzesten Weg zwischen zwei Knoten zu ermitteln.
Der Unterschied ist eigentlich sehr klein. Wenn du den Dijkstra Algorithmus anschaust, wählt er ja immer als nächste Kante die mit dem geringsten Gewicht.
Der A* Algorithmus macht das etwas allgemeiner, dort wird die "günstigste" Kante ausgewählt.
Was günstig bedeutet, wird durch eine Heuristik definiert, die bestimmte Eigenschaften erfüllen muss, damit ein brauchbares Ergebnis garantiert ist.
Beispielsweise wenn die Knoten Koordinaten haben ist eine geläufige Heuristik die Luftlinie zum Zielknoten.
Und wenn du einfach festlegst, dass die günstigste Kante die mit dem geringsten Gewicht ist, kommst du offensichtlich wieder bei Dijkstra raus.
e.f.q.
Aus Falschem folgt Beliebiges
Ich hab da letzt von 'nem Kollegen von einem Algorithmus gehört, bei dem jeder Abschnitt des Gesamtweges in eine Art virtuelles Wasserbehältnis umgerechnet wird. Jedes Behältnis ist unterschiedlich tief. Je "unwegsamer", desto tiefer. Dann wird am Anfang des Weges virtuell Wasser in den Weg eingelassen. Am Ende ist der Weg der beste, der am schnellsten voll ist.
Geile Idee. Wie nennt man diesen Algorithmus?
Ich weiss zwar nicht, wie der Algorithmus heisst, aber prinzipiell basiert er doch auch auf der Summe der "Unwegbarkeiten".
Jedes Feld erhält einen Float-Wert für seine Unwegbarkeit (0 = unproblematisch, PosInf = unmöglich). Jetzt wählt man denjenigen Weg, der unter allen Wegen die geringste Unwegbarkeitssumme aufweist.
Das Problem bei diesem Algorithmus ist, dass man alle Wege schon vorher berechnen muss. Ob man jetzt von "Wasserlöchern" spricht oder "Unwegbarkeiten", es bleibt der selbe Algorithmus.
Toll, ich fühl mich nach lesen dieses Thread total dumm X(
Das ist wohl der Unterschied, zwischen Studium und schulischer Ausbildung... Ich habe noch nie etwas von einen der genannten Algorithmen gehört.
Sind die lebenswichtig, konntet ihr die schonmal anwenden, ist es besser wenn ich mich da mal durchles?
Es ist toll jemand zu sein, der nichts von der persönlichen Meinung Anderer hält. - frisch-live.de
Keine Ahnung wie man das nennt. 😁
Das klingt aber eher nach eine bildlichen Veranschaulichung einer Gruppe von Algorithmen die nach einem ähnlichen Prinzip arbeiten. Doof ist nur, das sich beim "Wasser einlassen", das Wasser selbstständig und gleichzeitig verteilt. Das ist beim virtuellen Wasser nunmal nicht so und alle Wege (oder Kanäle) müssen einzeln durchgerechnet werden. Mir scheint nach deiner Beschreibung so als müsste man erst "alle Wege vollschütten" um hinterher zu wissen welcher der kürzeste ist. Damit müsste man wieder alle Möglichkeiten durchtesten und ist nicht schneller als sonst irgendwie.
Wenn das so ist, dann ist das Bild mit dem Wasser mehr oder weniger irreführend. Hat man aber öfters. Ich habe auch schon Leute getroffen die sich bei dem Algorithmus => Hier, den meine ich! ≤ wirklich vorgestellt haben, das man da kleine virtuelle Ameisen-Abbilder programmiert die schon wissen wo es Futter gibt. 8o
Edit:
@Frisch:
Wenn du zu einem Optimierungs-Problem mit vielen Unbekannten eine gute Lösung brauchst, musst du meist auf solche Algorithmen zurückgreifen. Standard-Beispiele sind meist sowas wie:
Du hast 100 Rohstofflager und 100 Produzenten mit soundsoviel LKW. Wie schaffst du nun zum geringsten Preis allen Produzenten die benötigten Rohstoffe hin.
Oder auch: Such mir den kürzesten Weg von A nach B, wenn es unheimlich viele Möglichkeiten für die Wege gibt, bei einem Routenplaner zum Beispiel.
Solange du nicht solche Optimierungsdinger programmieren musst, kannst du eigentlich einen großen Bogen um diese Algorithmen machen. 😉
Original von frisch
Toll, ich fühl mich nach lesen dieses Thread total dumm X(Das ist wohl der Unterschied, zwischen Studium und schulischer Ausbildung... Ich habe noch nie etwas von einen der genannten Algorithmen gehört.
Sind die lebenswichtig, konntet ihr die schonmal anwenden, ist es besser wenn ich mich da mal durchles?
Äh... ich hab Realschulabschluss, Ausbildung zum IT-Systemelektroniker und 6 1/2 Jahre Berufserfahrung als Entwickler von TK Software... Und ich fühl mich hier auch nicht unbedingt dumm. Gibt ja auch einen Unterschied zwischen Dummheit und Unwissenheit.
Unwissend ist, wenn ich mit 120 durche Ortschaft fahr, erwischt werd und nicht wusste, daß es verboten war. Dumm ist, wenn ich's zwei Mal tu.
Aber das ist OT...
Genau wie Luth schrieb: "das Wasser selbstständig und gleichzeitig verteilt"
Und deswegen klingen solche Algorithmen auch so toll und einfach. Nur leider gibt es noch keine Rechner, die dermassen parallel arbeiten, um solch ein (triviales) Problem in zumindest linearer Zeit zu lösen.
Vielleicht haben wir irgendwann einen Quantenrechner unter dem Schreibtisch stehen, dann können solche Probleme im null Komma nix gelöst werden...
@Borg: falsch, dann sind sie schon gelöst! 😁 😁 😁
(klugscheißmodus an Für alle Unwissenden: Beim Quantenrechner soll es THEORETISCH möglich sein, eine Lösung für ein Problem zu erhalten, welches noch gar nicht definiert wurde klugscheißmodus aus)
Wie das denn? Wenn schon Gerüchte, dann bitte etwas ausführlicher.^^ Soweit ich weis muss man auch bei der dortigen Architektur das Problem ausformulieren. Die im ausformulierten Problem inhärente (≤== schreibt man das wirklich so?) Lösung kann dann nur schneller gefunden werden. 🤔
Ich find den Artikel gerade nicht wieder... Ich such den mal. 🙂