Java Backtracking Irrgarten Lösung kürzester Weg

Zerstoerer · 22. November 2011

Hallo zusammen,

hab hier grad ein Problem. Ich muss hier eine Lösung für einen Irrgarten finden. Dabei muss das Programm eben Backtracking sein. Bisjetzt hab ich folgendes:

Code:

private boolean suche(int x, int y) {
    boolean gefunden = false;
    if(y!=ziely&&x!=zielx){

      feld[x][y] = '*';
      if(gefunden != true && feld[x][y+1]!='*' && feld[x][y+1]!='#' ){
         suche(x,y+1);
      }
      else if(gefunden != true && feld[x][y-1]!='*' && feld[x][y-1]!='#' ){
         suche(x,y-1);
      }
      else if(gefunden != true && feld[x+1][y]!='*' && feld[x+1][y]!='#' ){
        suche(x+1,y);
      }
      else if(gefunden != true && x>0 && feld[x-1][y]!='*' && feld[x-1][y]!='#'){
        suche(x-1,y);
      } else {
           feld[x][y] =' ';
        }
     } else {
       gefunden = true;
     }
     return gefunden;
  }

Es wird zurückgegeben werden, ob ein Weg gefunden wurde oder nicht. Auch muss der kürzeste Weg jeweils mit einem '*' besetzt werden, da er später grün als richtiger Weg markiert wird. Die Wände sind jeweils mit einem '#' markiert. "feld[][]" ist ein zweidimensionales Feld. "startx" und "starty" sind die Startkoordinaten, "zielx" und "ziely" die Zielkoordinaten. Doch irgendwie klappt das noch nicht so ganz.
Muss ich da noch etwas ändern oder ergänzen?

Wäre dankbar für ein paar Ratschläge.

Darlis · 22. November 2011

Du rufst die Funktion rekursiv auf, gibst das Ergebnis des Aufrufs aber nie zurück.

Zerstoerer · 22. November 2011

Hast du einen Tipp wie ich das jetzt machen könnte?

T3rm1 · 22. November 2011

Erstmal musst du Rekursion verstehen.

Zerstoerer · 22. November 2011

Ich geb kein Ergebnis zurück? Warum steht da bitte ein return?
Und an T3rm1: Ich habe hier ganz normal gefragt, da musst du nicht gleich so einen Ton anschlagen. Guck dir das Programm lieber noch mal an.
Wegen dem kürzesten Weg weiß ich das ich da noch etwas hinzufügen müsste. Erstmal will ich auch schaffen, dass überhaupt ein möglicher Weg gefunden wird.

Darlis · 22. November 2011

Zerstoerer schrieb:
Ich geb kein Ergebnis zurück? Warum steht da bitte ein return?

Das return gibt aber immer false zurück, es sei denn deine Startposition entspricht dem Ziel.

Gehe einfach mal einen Aufruf der Funktion gedanklich (oder mit dem Debugger) durch, ohne in die Rekursion zu gehen, dann sieht du das Problem.

Zerstoerer · 22. November 2011

Stimmt. Das Programm soll doch nur weitersuchen, solange es den Weg noch nicht gefunden hat. Oder geht es immer weiter? Was sollte es denn am besten zurückgeben?

Darlis · 22. November 2011

Zerstoerer schrieb:
Was sollte es denn am besten zurückgeben?

Ich würde sagen true, wenn ein Weg gefunden wurde, oder? Der Weg steht dann in feld[][].
Wie gesagt, gibt dein Programm bisher immer (bis auf den einen Fall) false zurück.

Dein Programm scheint auch nur einen Weg abzusuchen: Gabelt sich der Weg, wird nur in eine Richtung gesucht, je nachdem welche If-Bedingung zu erst greift.

Zerstoerer · 22. November 2011

Stimmt, aber die if-Fragen werden doch nacheinander abgefragt, sollte kein richtiger Weg gefunden worden sein.

T3rm1 · 22. November 2011

Zerstoerer schrieb:
Ich geb kein Ergebnis zurück? Warum steht da bitte ein return?
Und an T3rm1: Ich habe hier ganz normal gefragt, da musst du nicht gleich so einen Ton anschlagen. Guck dir das Programm lieber noch mal an.
Wegen dem kürzesten Weg weiß ich das ich da noch etwas hinzufügen müsste. Erstmal will ich auch schaffen, dass überhaupt ein möglicher Weg gefunden wird.

Wenn du Rekursion nicht verstehst, wie willst du das Problem lösen?

Überleg dir auch mal, welchen Sinn es hat in den IF Abfragen "gefunden" abzufragen, wenn es eh immer false ist.

Zerstoerer · 22. November 2011

Immer? Wenn startx==zielx usw. ist, dann ist ja der Weg gefunden und es muss nicht mehr weitergesucht werden, aber solange der Weg nicht gefunden wurde muss ja noch weitergesucht werden.

Darlis · 22. November 2011

Mal angenommen, das Ziel liegt direkt neben dem Start, bei (x,y+1). Beim ersten Aufruf von suche(x,y) kommst du also in die erste If-Bedingung und rufst erstmals suche(x,y+1) rekursiv auf. Da dies da Ziel ist (Abbruchbedingung) , liefert der Aufruf true zurück. Was machst du dann mit diesem Ergebnis?

Zerstoerer · 22. November 2011

Dann sollte das Programm doch abbrechen? Auch sollte der Weg - obwohl es keinen richtigen gibt - grün markiert worden sein, da in jedem Feld ein '*' gelegt wurde, oder?

Darlis · 22. November 2011

Es wird auch abbrechen aber es dir niemals true liefern. Wenn du meine letzte Frage beantworten kannst, weist du warum.

Zerstoerer · 22. November 2011

Ok du hast Recht.Doch was muss ich nun ändern, damit es funktioniert?

Darlis · 22. November 2011

Öhm, das Ergebnis verwerten vielleicht? Wenn das Programm einen Weg gefunden hat, willst du das doch weitergeben und nicht verwerfen.

Zerstoerer · 22. November 2011

Also das einzigste was passieren muss, ist ja dass der richtige Weg mit einem '*' markiert wird, sodass eine andere Methode den Weg grün färben kann.

dcobra · 22. November 2011

Warum wirfst du jetzt nicht den Debugger an? Bei Rekursion zugegebenermaßen etwas unübersichtlich, aber dann hättest du dir die Frage trotzdem schon selbst beantwortet in der Zeit

Darlis · 22. November 2011

Der Aufrufer will doch wissen, ob ein Ziel gefunden wurde, oder? Oder warum liefert die Methode einen boolean zurück?

Dein Programm zeichnet definitiv einen Weg ein, nämlich den zur erstbesten Sackgasse oder zum Ziel. Der Aufrufer bekommt aber in beiden Fällen false geliefert.

Zerstoerer · 22. November 2011

Sagen wir, das Programm ist in eine Sackgasse geraten. Dann müsste doch die erste if-Schleife beendet werden und die zweite aufgerufen werden, bis alle durch sind und dann schließlich in die methode davor gagangen wird und dort dann die restlichen if-Schleifen abgearbeitet werden usw. Solange bis ein weiterer Weg gefunden wird?

Java Backtracking Irrgarten Lösung kürzester Weg

Lieutenant

Commodore

Lieutenant

Lieutenant

Lieutenant

Commodore

Lieutenant

Commodore

Lieutenant

Lieutenant

Lieutenant

Commodore

Lieutenant

Commodore

Lieutenant

Commodore

Lieutenant

Lt. Junior Grade

Commodore

Lieutenant

Ähnliche Themen