Algorhitmus zur Berechnung des schnellsten Weges

Computer: Software & Programmierung Programmierung allgemein
#1

Hallo,

ich weiss das es zu meinem Problem einen bestimmten Algorhitmus gibt. Mir fällt leider nicht der Name davon ein.

Ich stell einfach mal mein Problem vor:

Ich habe ein Programm geschrieben(Objektorientiert Java), dass den schnellsten Weg von A nach B mit verschiedenen Buslinien herausfinden soll. Hintergrund ist folgender. Es gibt 5 verschiedene Möglichkeiten mit verschiedenen Buslinien von A nach B zu gelangen. Jede ist zu einer bestimmten Uhrzeit die schnellste. Bisher lass ich alle Möglichkeiten ausrechnen und lasse die Möglichkeiten ausser Acht, die eine bestimmte Zeit überschreiten. Dies ist sehr rechenintensiv und es treten viele Rekursionen auf. Da ich dieses Programm für mein Handy programmieren will, brauch ich hier einen besseren bzw. sinnvolleren Algorhitmus. Wie gesagt, ich weis das es da einen gibt, aber mir fällt der Name nicht ein. Wer kann mir sagen, wie diese Problemstellung in der Informatik genannt wird und wo ich mehr über diesen Algo erfahren kann und welche Lösungen es für mein Problem gibt?

Vielen Dank

MFG Ralph

#2

Hallo,

ich weiss das es zu meinem Problem einen bestimmten
Algorhitmus gibt. Mir fällt leider nicht der Name davon ein.

Hallo,

meinst du vielleicht die A-Stern-Suche?

Diese würde weniger Schritte brauche, um den günstigsten Weg zu berechnen, da sie eine Heuristik integriert…

Gruss, Omar Abo-Namous

#3

Nein, die hab ich noch nicht gehört, aber mal googlen was sich darüber finden lässt. Schon mal danke!!!

Sonst noch wer ne Idee??

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#4

Hi!
Schau dir mal folgenden Artikel an.Im unteren Teil werden die verscheidenen Möglichkeiten beschrieben.
http://www.verkehrsseiten.de/de/instruct/auskunft.htm
Gruß.Timo

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

#5

Ich habe ein Programm geschrieben(Objektorientiert Java), dass
den schnellsten Weg von A nach B mit verschiedenen Buslinien
herausfinden soll.

Vielleicht Dijkstra’s Labeling-Algorithmus? Der ist prinzipiell dazu gedacht, in einem Graph einen billigen/optimalen Weg von einem festen Start- zu einem festen Zielpunkt zu finden und tut das auch recht gut.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

#6

Hallo,

ich weiss das es zu meinem Problem einen bestimmten
Algorhitmus gibt. Mir fällt leider nicht der Name davon ein.

Hi Ralph,

Wir haben den Algorithmus in der Schule als „Travelling Salesman Algorithmus“ gelernt. Den müsste ich aber erst in Java übersetzen, Du findest Ihn sicher - GIYF.

Gruß,
Rudy

#7

A* und mehr
Hi,

auf Englisch gibts hier eine gute Einführung ind die Pfadfindung und -planung:
http://ai-depot.com/BotNavigation/Path.html

Grüsse,

Herb

#8

Hey danke an alle,

Travelling Salesman Algorithmus hieß der Algo von dem ich gehört hab. Danke euch vielmals für die schnelle Hilfe!!!

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]