Kürzester Weg

[Heraklit]

Hi,
ich versuche in Java ein Programm zu schreiben, das den kürzesten Weg in einem Labyrinth ausfindig macht (Nach zwei Anläufen leider immer noch ohne Ergebnis)! Die Grafische Oberfläche hab ich schon vorliegen. Es ist also nur noch der Algorithmus bzw. das Programm selbst zu schreiben!

Der Algorithmus sucht im Labyrinth nach den kürzesten Weg zwischen Start- und Zielpunkt. Dieses Labyrinth ist im Prinzip eine 2-dimensionale Array, die sich einerseits aus nichtpassierbaren Elementen, nämlich Objekten der Klasse "Mauer", sowie einem Startelement "Start" und einem Zielelement "Ziel" zusammensetzt. Die restlichen Elemente ergeben die passierbaren Elemente des Labyrinths. So...

Ich habe folgende verbale Beschreibung des Algorithmus gefunden, jedoch gelingt es mir nicht, sie in Java umzusetzen:
------------------------------------------------------------
// Zunächst ein paar Bemerkungen zur Notation:
// (K,W): K bezeichnet einen Punkt/Knoten des Labyrinths,
// W den bisher zurückgelegten Weg.
// W+K: Dies bedeutet, dass der Knoten K zum Weg W angefügt wird.

WEGSUCHE(Graph G, Startknoten S, Zielknoten T)
{
Füge (S,{}) in die Liste L der noch nicht besuchten Knoten
while L nicht leer
{
Nimm einen Knoten/Wegpaar (K,W) aus der Liste L
Ist K der gesuchte Knoten T, dann return W
Markiere K als besucht
Füge für jeden unbesuchten Nachfolgerknoten N
von K das Paar (N,W+K) in Liste L ein
}
}

// Hierbei sei bemerkt, dass L eine Schlange (Queue) oder ein
// Keller (Stack) ist! Wenn ich das richtig verstanden habe, wird
// bei Verwendung des Stacks für die Liste L eine Tiefensuche
// durchgeführt, andernfalls eine Breitensuche!
--------------------------------------------------------------

Neben der Graphischen Oberfläche, steht mir noch das Gerüst der zu implementierenden Methode zur Verfügung:

------------------------------------------------------------------
// Die Klasse Koordinaten hat zwei Eigenschaften: int x und int y
// und soll die Koordinaten von Zellen im Irrgarten enthalten.
// Ein Weg im Irrgarten ist eine Folge (Array) von solchen
// Koordinaten.

public Koordinaten [] sucheWeg(Zelle [][] garten)
{
// Ob ein Element des Labyrinths der Zielpunkt ist, der
// Startpunkt oder ein Mauerelement, lässt sich durch folgende
// Abfragen feststellen
// (Hier am Beispiel des Elements garten[0][0])

if (garten[0][0] instanceof Ziel)
{ }

if (garten[0][0] instanceof Start)
{ }

if (garten[0][0] instanceof Mauer)
{ }

// Zuletzt wird der Weg als Array zurückgegeben;
// hier werden beispielsweise die Punkte (1,1),(2,2),(3,3)
// zurückgeliefert!

Koordinaten [] result = {new Koordinaten(1,1),
new Koordinaten(2,2),
new Koordinaten(3,3) };
return result;
}

Wie lautet die Implementation dieser Methode?

Vielen Dank für eure Antwort.

 

[Illuvatar]

Hausaufgaben machen wir dir nicht. Und mehr Tips als das da oben könnwn wir dir kaum geben.

 

[Guest]

a) Das ist keine Hausaufgabe, sondern WAR eine Aufgabenstellung im Zuge der Programmiervorlesung.
b) Ich brauch auch keine Tips, sondern die Lösung!
c) Nach intensiver und erfolgloser Recherche im Netz, bin ich zu dem Ergebnis gekommen, dass es sich hierbei um einen ganz gebräuchlichen Algorithmus handelt, der für einen Informatiker, der sich in Java auskennt ein Kinderspiel sein müsste! Da ich jedoch am Anfang stehe, habe ich auch die ewigen langen Lösungen aus dem Netz nicht nachvollziehen können!
d) Bei meiner ersten (Pseudo)Lösung wurde ein völlig wirrer Weg ausgegeben, der zwar zum Ziel führt, aber bestimmt nicht so wie ich mir das vorgestellt habe. Beim zweiten Mal, war das Programm völlig verbuggt...
e) Würde mich wirklich freuen, wenn jemand die Implementierung dieser Methode liefern könnte (Die Lösung ist mit Sicherheit nicht lang)

mfg

 

[semi]

Vielleicht hilft dir folgender naiver, rekursiver Algorithmus.

AP = Aktueller Punkt

1.) AP bereits besucht (in Wegliste), raus
2.) AP ist Wand, raus
3.) AP ist Ausgang => Punkte der Wegliste merken und raus
4.) AP in Wegliste einfügen
5.) Gehe zu 1 mit LP = LINKS_VON(AP)
6.) Gehe zu 1 mit VP = VORNE_VON(AP)
7.) Gehe zu 1 mit RP = RECHTS_VON(AP)
8.) AP aus Wegliste entfernen und raus

9.) Aus den gemerkten Listen die kürzeste(n) ausgeben

Was links, rechts und vorne in einem 2D Raum ist, hängt davon ab wohin man guckt.

Die Suche ist unnötig umständlich, als erster Ansatz sollte es aber reichen. Optimieren kannst du dann selber.
Das, was du am häufigsten zu sehen kriegst, wenn du es falsch implementierst, wird StackOverflowException sein.
Viel Spaß bei Endlosschleifen. (immer schön Speichern bevor du es ausführst) :bae:

 

[bygones]

machs dir einfacher:

google oder such im forum nach Djikstra bzw. A* Algorithmus !