Aufgabe zu Tiefen- oder Breitensuche

[Terence86]

Komplette Aufgabenstellung : http://www2.inf.fh-rhein-sieg.de/~pbecke2m/graphentheorie/u4.pdf

Hätte hierzu jemand eine Idee (Ansatz) ?
Eine Testmap wäre zb. sowas :

public static boolean[][] testmap0 = {
    { false, false, false, false, false, false, false, false, false, false},
    { false, false, false, false, false, false, false, false, false, false},
    { false, false, false, false, false, false, false, false,  true, false},
    { false, false, false, false, false, false,  true,  true, false, false},
    { false, false, false, false, false, false, false, false, false, false},
    { false, false, false, false, false, false, false, false, false, false},
    {  true, false, false, false, false, false, false, false,  true, false},
    { false, false, false, false, false, false, false, false,  true, false},
    { false, false, false, false, false, false, false, false, false, false},
    { false, false, false, false, false,  true, false, false, false, false}
    };
    /* testmap0
    +----------+
    |          |
    |          |
    |        X |
    |      XX  |
    |          |
    |          |
    |X       X |
    |        X |
    |          |
    |     X    |
    +----------+
    */

Mir ist es persönlich egal ob ihr lieber Bfs oder Tfs anwendet, hätte dazu gerne ein Ansatz.

 

[Flown]

Was verstehst du denn nicht?

 

[Terence86]

Hi schön erstmal das sich jemand meldet.
Ja das Problem verstehe ich im Grunde, nur weiß ich nicht wie ich mit einer boolean "matrix" arbeitete.
Ich soll das ganze nicht in eine Adjazenzlistendarstellung bringen, mal abgesehen wie ich das mache, könnte ich damit wenigstens ne alte Klasse zur Hand nehmen die mir dann die Wege ausgibt.
Im Grunde Starte ich ja bei [0][0] und will einen Weg finden zu [n-1][n-1] wobei n die Länge bzw. Größe der Karte ist.
[0][0] ist immer "false" das es ja mein Startpunkt darstellt. "True" sind die schwarzen Felder auf die ich nicht kann. -> Knoten die Isoliert sind, alle anderen sind ja miteinander verbunden und besitzen somit einen Weg. Jetzt müsste ich auf einen Algorithmus schreiben der eine Suche mit Hilfe von dfs oder bfs und mir die Wege absucht, bis er am Ziel ist und mir diesen dann zurück gibt. Dabei soll er nicht aus der Map gehen -> Overflow und nicht auf die True Felder gehen // wären ja irgendwelche if Formulierungen.
Müsste ja irgendwie eine Priorität erstellen, gehe rechts -> wenn es nicht mehr geht, dann runter,usw. ?
Also was ich meine der "Roboter" brauch ja irgendwie Anweisungen was der machen soll.
Ich habe echt Schwierigkeiten das zu Implementieren.. deswegen war ja meine Frage ob jemand einen Ansatz wüsste. Und ja weil das true und fales sind krieg ich einen Anfall da ich sonst Zahlen(integer) vorliegen hatte.. Und ja wenn mich jemand fragen würde, würde ich sagen irgendwie mit eine Rekursion vielleicht? Also die Methode Search() solange wiederholen lassen bis ich am Ziel bin und dann Ausgabe nehmen und die also String darstellen!? Mit ist klar das mir paar Vorkenntnisse dazu fehlen aber ich hoffe das ich das mit euch hier schaffe
+ Zusatz: Bei der Abarbeitung muss ja der (oder die Vorgänger) beachtet werden das diese nicht nochmal angelaufen werden. Wie funktioniert das den?

 

[LeopoldStotch]

Du könntest dir eine Klasse "Knoten" erstellen, in der du deine aktuelle Position speicherst und eine Referenz auf den "Knoten" von dem du gekommen bist.

Dann arbeitest du mit 2 Listen z.B. ArrayList<Knoten> openList und
ArrayList<Knoten> closedList.

Du startest mit der Position (0,0) und erstellst ein Objekt vom Typ Knoten und packst es auf die openList.

So lange die openList nicht leer ist und du dein Ziel noch nicht erreicht hast nimmst du das untere Objekt von der openList und packst es in die closedList.
Anschließend schaust du in alle Richtungen von dem Knoten aus, den du zuvor in die closedList geseteckt hast, und prüfst ob du in diese Richtungen gehen kannst.
Für jeden gültigen Weg erstellst du ein neues Objekt mit den Koordinaten und dem Vorgänger.
Dann jedes Objekt in die openList ein, aber nur wenn es noch nicht in der closedList enthalten ist.

Wie du neue Objekte in die Liste einfügst hängt davon ab ob du Breitensuche oder Tiefensuche benutzen willst. Fügst du die neuen Knoten immer an das Ende der Liste realisiert das die Breitensuche, fügst du sie am Anfang ein realisierst du die Tiefensuche.

 

[Terence86]

Klingt gut, aber ich denke ich lasse es. Mir fehlen die Vorkenntnisse wohl die man haben müsste.

 

[Meniskusschaden]

Mir fehlen die Vorkenntnisse wohl die man haben müsste.

In welchem Bereich fehlen dir denn die Vorkenntnisse?
Man kann es auch mit einem relativ naiven Ansatz ohne Objekte machen, indem man einfach ausgehend von der Startposition rekursiv für alle Nachbarpositionen eine Methode aufruft, der man die aktuelle Position, die Richtung, den bisher gefundenen Pfad und die Map übergibt. In der Methode macht man folgendes:

1. Neue Position berechnen.
2. Prüfen, ob die Position nicht zur Lösung gehört (Felsen, ausserhalb der Map, bereits besucht) und mit return null heraus springen.
   
3. Prüfen, ob das Ziel erreicht wurde und ggf. mit return path+directionheraus springen.
4. Aktuelle Position als "besucht" markieren
5. Die Methode mit path+directionfür die Nachbarpositionen aufrufen.
6. Falls für alle Nachbarpositionen null zurückgegeben wurde, mit return null heraus springen.
7. Falls für eine Nachbarposition ein String != null zurück gegeben wurde, ist das eine Lösung, die zurück gegeben werden kann.

Man benötigt allerdings eine Hilfsstruktur für die bereits besuchten Positionen. Das könnte beispielsweise ein zweites boolean-Array mit denselben Dimensionen wie map sein.

 

[Terence86]

Meniskusschaden klingt super. An eine wiederholende Methode habe ich auch gedacht, aber wie ich das ganze in Java ausdrücke... Keine Ahnung. Array ja mal gehört und auch nachgeforscht bringt mich aber beim Problem nicht weiter. Ich fange bei map[0][0] an und will zu map [n-1][n-1] wie laufe ich den das ganze ab wie sieht das aus (im Code)? Wie stell ich den Weg da den ich grade gehe auch wenn ich nicht ans Ziel komme, und wenn es nicht weiter geht soll er ja zurück an den Punkt [][] wo es weiter gehen kann etc. bis ich am Ziel bin. Mir fehlt nicht das Verständnis an der Aufgabe sondert wie das ganze mit Java funktionieren soll. Ja und weil ich das nicht kann und Stunden damit verbringe in den Monitor zu starren und im Internet zu suchen zu forschen über Arrays dfs bfs etc. und ich kein konkretes Beispiel finde, wie das auf mein Problem bezogen angewendet wird. Wollte ich das in den Sand setzten.

 

[Terence86]

1. Neue Position berechnen : also map[0][0] fang ich an.
-> Habe 2 Nachbarn map[1][0] und map[0][1], da "oben" und "links" ich sonst aus der Map falle.
Also index davon sollte immer größer 0 sein, und rechter Rand und unterer wäre durch: darf nicht größe als n von map.length sein.
return path + direction -> was sind die beiden?
Wie speicher ich wo ich schon war? "besucht"
usw. Weiß was du meinst aber nicht wie das in Java aussieht.

 

[Meniskusschaden]

Die search-Methode könnte so aussehen:

public static String search(boolean[][] map) {
    boolean[][] visited = new boolean[map.length][map[0].length];
    String result = findPath(0, 0, 'd', "", map, visited);
    if (result == null) {
      result = findPath(0, 0, 'r', "", map, visited);
    }
    return result;
}

Die Hauptarbeit verrichtet dann die Methode findPath, die gemäß meinem vorigen Posting nach folgendem Prinzip arbeiten könnte:

private static String findPath(int line, int column, char direction, String path, boolean[][] map, boolean[][] visited) {
    1. neue Werte für line und column mit Hilfe von direction bestimmen.

    2. if (gewisseBedingungenErfuellt) return null;
 
    3. if (ZielpositionErreicht) return path+direction;

    4. visited[line][column] = true;

    5. findPath für die vier Richtungen aufrufen (Rueckgabe geeignet auswerten):
             loesung = findPath(line, column, 'd', path+direction, map, visited);
             loesung = findPath(line, column, 'u', path+direction, map, visited);
             loesung = findPath(line, column, 'l', path+direction, map, visited);
             loesung = findPath(line, column, 'r', path+direction, map, visited);

    6. Falls keiner der Aufrufe aus 5. erfolgreich war: return null;

    7. Falls ein Aufruf aus 5. erfolgreich war: return loesung;
}

Das geht bestimmt eleganter und findet nicht unbedingt den kürzesten Weg (ist ja auch nicht gefordert), aber es müsste funktionieren.

return path + direction -> was sind die beiden?

Der bisher gefundene Pfad und die letzte Richtungsangabe. Dadurch wird der Pfad also um die aktuelle Position erweitert.

Wie speicher ich wo ich schon war? "besucht"

Bei diesem Ansatz im Array boolean[][] visited. Man kann aber ebenso gut andere Datenstrukturen nutzen.

Wie stell ich den Weg da den ich grade gehe auch wenn ich nicht ans Ziel komme, und wenn es nicht weiter geht soll er ja zurück an den Punkt [][] wo es weiter gehen kann etc. bis ich am Ziel bin.

Das Schöne an rekursiven Lösungen ist, dass man sich um den Rückweg nicht kümmern muß, denn nach Beendigung der rekursiven Aufrufe ist man ja automatisch wieder am Ausgangspunkt und kann dort weiter machen, beispielsweise indem man findPath() für eine andere Richtung aufruft.

 

[Terence86]

Wow spitze. Meinst du mit String line und column, die Linien bzw. Spalten? Sowas wie :

        if (direction == 'r') {
            line = line + 1;
        }
        if (direction == 'l') {
            line = line -1;
        }
        if (direction == 'u') {
            column = column - 1;
        }
        if (direction == 'd') {
            column = column +1;

(aus Hinweise
r: map[x][y+1],
l: map[x][y-1],
u: map[x-1][y] und
d: map[x+1][y].)

 

[Terence86]

Zu Punkt 2. Sind da die Bedingungen gemeint die zutreffen wenn ich aus der Karte bzw. auf einen Felsen treffe?

 

[Meniskusschaden]

Zu Punkt 2. Sind da die Bedingungen gemeint die zutreffen wenn ich aus der Karte bzw. auf einen Felsen treffe?

Ja. Ausserdem auch der Fall, dass eine Position bereits besucht wurde und der Fall, dass die Startposition erreicht wurde. Die ist nämlich noch nicht als besucht gekennzeichnet (einer der Punkte, die man besser machen könnte).

Wow spitze. Meinst du mit String line und column, die Linien bzw. Spalten? Sowas wie :

if (direction == 'r') {
            line = line + 1;
        }
        if (direction == 'l') {
            line = line -1;
        }
        if (direction == 'u') {
            column = column - 1;
        }
        if (direction == 'd') {
            column = column +1;

Ja. Ich habe aber nicht beachtet, dass in der Aufgabenstellung die Namen x und y benutzt werden (fällt mir erst jetzt auf) und habe stattdessen line und column verwendet. Mit line meint ja normalerweise die y-Dimension und mit column die x-Dimension. Ich würde an deiner Stelle dann auch lieber x und y verwenden, weil dein aktueller Code sonst so aussieht, als würdest du beispielsweise mit 'r' nach unten gehen.

 

[LeopoldStotch]

@Meniskusschaden
Das Problem, welches ich bei eine Rekursiven Suche sehe ist, dass man keine Breitensuche damit durchführen kann. Oder mache ich da gerade einen Denkfehler? Zumindest müsste man einiges an der Implementierung ändern, denke ich.

 

[Meniskusschaden]

Das Problem, welches ich bei eine Rekursiven Suche sehe ist, dass man keine Breitensuche damit durchführen kann.

Ich finde, die Frage ist falsch herum gestellt. Ich würde mir nicht überlegen, ob ich rekursiv oder iterativ suchen möchte, sondern die Frage, ob ich eine Breiten- oder Tiefensuche durchführen will. Im ersten Fall ist es iterativ einfacher, im zweiten Fall rekursiv. Dieses Argument:

Das Schöne an rekursiven Lösungen ist, dass man sich um den Rückweg nicht kümmern muß, denn nach Beendigung der rekursiven Aufrufe ist man ja automatisch wieder am Ausgangspunkt

ist für die iterative Breitensuche ja nicht relevant, weil man dort gar nicht zum Ausgangspunkt zurück kehren muß, denn sobald man an einem Knoten ankommt, sind alle darüber liegenden Knoten ja bereits abgearbeitet worden.
Für die Breitensuche benötigt man eben zusätzlich eine Queue (siehe Vorschlag von @LeopoldStotch), bei der Tiefensuche kann man darauf verzichten, benötigt jedoch etwas Verständnis über Rekursion, was ja nicht immer so anschaulich ist.