Wegsuche in Labyrinth

[kelekcibo]

Hallo,

erstmal vorweg: kein Code, etc. Nicht nur wegen Plagiat, weil ich will von selbst drauf kommen... Warum poste ich, falls ich von selbst drauf kommen will? Ich habe schon über 15h mit der hausi verbracht und jede mögliche Situation durchdacht (möglicherweise ist das der Grund, warum ich nicht drauf komme), aber immer noch keine endültige, aber teilweise richtige Lösung.

Es geht um eine änliche Aufgabe wie Roboter Karol (siehe Google), wobei die Methoden in unserem Programm nur Schritt, Linksdrehen, Rechtsdrehen, platzieren, aufheben ist (siehe: https://steffen-boehme.de/arbeit/unterri/hessen/info/g8/q1/pdf/134.pdf)

Nun gibt es ein Spielfeld[x][y] mit Breite x und höhe y. Jedes Feld hat eine bestimmte Höhe (auch Hindernisse, max. 9). Nun sollen wir ein Programm schreiben, dass automatisch eine optimale Sequenz findet, die von einem random Startpunkt (x,y) mit einer random Blickrichtung (oben/.../links), zu einem random Zielpunkt führt. Mir wurder der A*-Alg. empfohlen, aber den schaue ich mir noch an. Aber im Falle, dass ich es trotzdem net pack, wollte ich es hier gefragt haben. Tutoren helfen natürlich, aber ich konnte es trotzdem nicht verstehen.

Meine Frage: Wie kann ich entscheiden, ob ein Zug sinnvoll war oder nicht? Wenn ich richtung Zielpunkt ein Schritt mache, heißt es ja nicht unbedingt, dass der Zug sinnvoll war. Wir haben außerdem Hilfsmethoden wie LetztenMoves waren unnötig oder warSchonHier.

Vielen Dank im Voraus, falls ihr mir paar tipps gebent könnt, ohne die Lösung zu sagen!!

 

[kelekcibo]

Tut mir leid für den spam

 

[fhoffmann]

Ich lade keine fremden Dokumente herunter. Deshalb sei doch so nett, die ursprüngliche Aufgabenstellung bereitzustellen.

 

[kelekcibo]

Ich lade keine fremden Dokumente herunter. Deshalb sei doch so nett, die ursprüngliche Aufgabenstellung bereitzustellen.

Aso, die pdf Datei is ausm internet, in der nur die beispiel Instruktionen von roboter karol stehen, aber wie ich erwähnt habe, gibt es in meinem Fall nur Instruktionen wie Schritt, nehmen, platzieren, links/rechzsdrehen

 

[kelekcibo]

Ich lade keine fremden Dokumente herunter. Deshalb sei doch so nett, die ursprüngliche Aufgabenstellung bereitzustellen.

Nun kommen wir zum eigentlichen Teil: wir wollen für Carol Pfade finden, um auf einem gegebenen Spielfeld playground von einer Ausgangssituation x, y, direction zu einer Zielposition findX, findY zu kommen. Implementieren Sie dafür eine Methode mit dem folgenden Methodenkopf:

public static boolean findInstructions(int[][] playground, int x, int y, int direction, int blocks, int findX, int findY, char[] instructions)

Neben den schon genannten Parametern übergeben wir der Methode zusätzlich noch ein char-Array instructions. In dieses Array soll die Instruktionssequenz gespeichert werden, die Carol zum Ziel führt. Dabei soll genau dieses übergebene Array verwendet werden, welches (wie für Arrays üblich) eine feste Länge besitzt. Die Methode muss daher nach Lösungen suchen, die maximal instructions.length viele Instruktionen benötigen (hierdurch wird auch der Rechenaufwand limitiert).

Da es möglich ist, dass eine solche Lösung nicht existiert, soll genau dann false zurückgegeben werden, wenn die Suche nicht erfolgreich war. Falls die Suche jedoch erfolgreich war, wird true zurückgegeben und in instructions steht eine Instruktionssequenz, mit der Carol zum Ziel kommt. Ist diese Sequenz kürzer als das Array, sollen alle verbleibenden Felder mit 'e' gefüllt sein, der Endinstruktion in der Pinguin Carol Simulation. Lösen Sie diese Aufgabe mittels Rekursion.

 

[kelekcibo]

Ich teile mal mein Lösungsvorschlag:

Ich habe eine Hilfsmethode zusammengebastelt, die die selbe Parameter wie die findInstruction Methode hat, nur dass ich da noch den Parameter mitgebe, der sagt wie viele Befehle im array sind (int filled). Und diesen rufe ich rekursiv auf und finde Instruktionen. Da aber an jedem Punkt fast alle Instruktionen möglich sind, wusste ich nich mehr weiter wie ich überprüfen kann, ob die richtige Instruktion ausgewählt wird

 

[kelekcibo]

Implementieren Sie die findOptimalSolution-Methode, die den folgenden Methodenkopf besitzt:

public static char[] findOptimalSolution(int[][] playground, int x, int y, int direction, int blocks, int findX, int findY, int searchLimit)

Diese Methode soll findInstructions nutzen, um die/eine optimale Instruktionssequenz zu finden. Eine Instruktionssequenz ist optimal, wenn es keine kürzere gibt, die einen Pfad von der Ausgangssituation zum Zielort beschreibt.

Das searchLimit ist hierbei die maximale Länge, bis zu der nach Lösungen gesucht werden soll. Das dient vor allem der Begrenzung des Suchaufwands. Zurückgeben soll die Methode null, falls keine solche Lösung existiert, und sonst ein char-Array, das

 

[mihe7]

Um A* zu verstehen, schaut man sich erst einmal an, wie es ohne A* funktionieren würde.

Gehen wir mal von einem 4x4 Feld (links oben sei (0,0), rechtes unten (3,3)) aus. Der Roboter befinde sich im Punkt (1,1) und kann sich nur orthogonal, also in vier Richtungen, bewegen. Ziel sei (3,3).

Jetzt gehst Du her und sagt: ok, im ersten Schritt habe ich vier mögliche Nachbarn, die alle in Frage kommen. Egal, welchen Nachbar ich wähle, der Roboter muss einen Schritt machen. Die vier Felder sind also zunächst alle gleichwertig.

Also trägst Du für die Felder (0,1), (1,0), (2,1) und (1,2) (Bewegung nach links, oben, rechts, unten) einen Schritt und das Vorgängerfeld (1,1) ein.

  0 1 2 3
 +-------
0|. 1 . .
 |  v
1|1>0<1 .
 |  ^
2|. 1 . .
 |
3|. . . .

Erste Runde erledigt, als nächstes untersuchst Du alle Möglichkeiten für alle Felder, die eine 1 eingetragen haben. Dabei ist darauf zu achten, dass keine Felder mehrfach besucht werden dürfen.

a) (0,1) hat zwei Möglichkeiten (0,0) und (0,2). (-1,0) gibt es nicht und das Feld (1,1) ist das Vorgängerfeld, wurde also bereits besucht. Für die beiden möglichen Felder trägst Du nun 2 ein, weil Du vom Ausgangsfeld zwei Schritte weit gegangen bist. Außerdem das Vorgängerfeld (0,1)

b) (1,0) hat theoretisch ebenfalls zwei Möglichkeiten: (2,0) und (0,0). Die (0,0) wurde aber gerade eben schon besucht. Fällt also flach. Bleibt die (2,0) übrig. Dort wieder die 2 Schritte und das Vorgängerfeld (1,0) eintragen.

c) (2,1) hätte theoretisch vier Möglichkeiten (1,1), (3,1), (2,0) und (2,2). Die Felder (1,1) und (2,0) sind bereits besucht, scheiden damit aus. Bleiben (3,1) und (2,2) übrig. Dort wieder 2 Schritte und das Vorgängerfeld (2,1) eintragen.

d) (1,2) hätte theoretisch vier Möglichkeiten: (0,2), (2,2), (1,1) und (1,3). Die Felder (0,2), (1,1) und (2,2) wurden bereits besucht. Bleibt nur noch (1,3) übrig. Dort 2 Schritte und Vorgängerfeld (1,2) eintragen.

  0 1 2 3
 +-------
0|2 1<2 . 
 |v v
1|1>0<1<2 
 |^ ^ ^
2|2 1 2 .
 |  ^
3|. 2 . .

Zweie Runde wäre geschafft. Jetzt kommen alle Felder dran, die 2 Schritte eingetragen haben:

a) (0,0) -> keine Möglichkeit
b) (0,2) hat nur (0,3) als möglichen Nachbarn. Dort 3 und Vorgänger (0,2) eintragen.
c) (2,0) hat nur (3,0) als möglichen Nachbarn. Dort 3 und Vorgänger (2,0) eintragen.
d) (3,1) hat nur (3,2) als möglichen Nachbarn. Dort 3 und Vorgänger (3,1) eintragen.
e) (2,2) hat nur (2,3) als möglichen Nachbarn. Dort 3 und Vorgänger (2,2) eintragen.
f) (1,3) hat nur (0,3) als möglichen Nachbarn. Dort 3 und Vorgänger (1,3) eintragen.

  0 1 2 3
 +-------
0|2 1<2<3 
 |v v
1|1>0<1<2
 |^ ^ ^ ^
2|2 1 2 3
 |^ ^ ^ ^
3|3 2 3 .

Und dritte Runde: alle Felder, die 3 Schritte eingetragen haben:
a) (0,3) -> keine Möglichkeit
b) (3,0) -> keine Möglichkeit
b) (0,3) -> keine Möglichkeit
c) (3,2) hat nur (3,3) als möglichen Nachbarn. Dort 4 und Vorgänger (3,2) eintragen.

Ziel erreicht:

  0 1 2 3
 +-------
0|2 1<2<3 
 |v v
1|1>0<1<2
 |^ ^ ^ ^
2|2 1 2 3
 |^ ^ ^ ^
3|3 2 3 4

Jetzt kannst Du vom Ziel die Vorgänger zurückgehen und hast den kürzesten Weg: (3,3), (3,2), (3,1), (2,1), (1,1) -> umgekehrt also (1,1), (2,1), (3,1), (3,2) und (3,3).

So, das ist die "Billigvariante". Die Idee von A* ist nun, dass man einerseits alle möglichen Wege berücksichtigt, wobei der kürzeste bevorzugt wird und damit der Suchraum eingeschränkt wird.

Statt einfach immer einen Schritt weiter zu zählen, wird zusätzlich die kürzeste Entfernung zum Ziel addiert (Luftlinie bzw. hier Manhatten-Metrik). Außerdem wird immer der Knoten mit der geringsten eingetragenen Entfernung verwendet.

Damit bekommt am Anfang das Feld (0,1) den Wert 1 (tatsächliche Schritte) plus 5 (Entfernung von 1,0 zu 3,3 nach Manhatten-Metrik) also 6 eingetragen. Das Feld (1,0) den Wert 1 plus 5, also ebenfalls 6. Das Feld (2,1) dagegen 1 plus 3, also 4. Das Feld (1,2) somit 1 + 3, also 4.

Jetzt gibt es zwei Felder mit der Entfernung 4: (2,1) und (1,2). Da pickt man sich nun eines heraus verfolgt den Weg so lange, bis die Schrittzahl über dem eines anderen Feldes liegt:

(2,1) hat die Möglichkeit (2,0). Das wären 2 echte Schritte vom Ausgangsfeld plus 4, also 6. Außerdem die Möglichkeit (3,1), das wären 2 echte Schritte plus 2 Luftlinienschritte, also 4. Dann noch (2,2) -> 2 + 2, also 4. Passt.

(2,2) hat die Möglichkeiten (1,2), (3,2) und (2,3). Die letzten beiden kommen wieder auf 4. Nimmt man wieder eines, z. B. (2,3) -> (3,3) fertig.

Würde man z. B. auf ein Hindernis stoßen, dann würde sich der Weg verlängern und man würde bei einem Feld weitermachen, für das weniger Schritte eingetragen sind.

 

[kelekcibo]

Erstmal danke für die Antwort! Ungefähr habe ich es verstanden, jedoch mit den Hindernissen: Falls der Weg komplett abgeschottet ist, also Hindernisse nicht vorbei lassen, und man keine Blöcke vom Hindernis nehmen kann, da man auf Feld -1 steht, muss der Pingu nach einer Position suchen mit Wert > -1, damit er platzieren oder nehmen kann. Wie kann ich sowas berücksichtigen?

 

[mihe7]

Das geht automatisch: Du schaust ja nach, welche Nachbarfelder in Frage kommen - Hindernisse gehören da einfach nicht dazu

 

[kelekcibo]

Ich werd jetzt mal versuchen, das umzusetzen