Heraklit
03-04-2005, 23:00
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.
P.S.: Das ist keine Hausaufgabe oder ähnliches!
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.
P.S.: Das ist keine Hausaufgabe oder ähnliches!