Backtracking - kennt Java keine Rücksprungmarken?

[ayrton89]

Hallo,
ich möchte mit dem Backtracking-Algorithmus Wege durch ein Labyrinth finden. Das Prinzip ist klar, es ist ein rekursiver Algorithmus den man jeweils mit der erweiterten Teillösung aufruft und der returnt, wenn das Ende erreicht ist bzw. wenn er in einer Sackgasse landet. Ich übergebe der Funktion konkret eine ArrayList mit allen Feldern die zu dem Weg gehören. Nur dummerweise verwendet der Interpreter scheinbar nach dem returnen nicht den Wert vom Rücksprungkeller, sondern nimmt immer den aktuellsten, sodass er auch wenn das Zielfeld schon erreicht ist immer noch Felder hintendranhängt.

Ich denke mal das hat irgendwas damit zu tun dass Objekte per Referenz übergeben werden, kann man das also irgendwie ändern bzw. umgehen?

Danke

 

[ARadauer]

ja referenzen.... hilft dir das...

   public static void main(String[] args) {
      ArrayList<String> list = new ArrayList<String>();
      list.add("Test");
      System.out.println("Size: "+list.size());
      cleerList(list);
      System.out.println("Müsste 0 sein, die die Referenz übergeben wurde: "+list.size());
      
      list.add("Nochmal");
      cleerList((ArrayList<String>)list.clone());
      System.out.println("Müsste 1 sein da eine Kopie übergeben wurde: "+list.size());
   }
   
   public static void cleerList(ArrayList<String> list){
      list.clear();      
   }

 

[SchonWiederFred]

Ich denke mal das hat irgendwas damit zu tun dass Objekte per Referenz übergeben werden, kann man das also irgendwie ändern bzw. umgehen?

Vorsicht, in Java werden keine Objekte übergeben, und es wird auch nichts per Referenz übergeben -- sowohl primitive Typen als auch Referenztypen werden per Wert übergeben.

Wenn Du die Übergabe von Objekten per Wert simulieren willst, musst Du Objekte klonen. Statt
funktion(meineListe); musst Du also
funktion(new ArrayList(meineListe)); oder sowas schreiben.

 

[ayrton89]

Nein das hilft leider auch nicht. Ich will ja nur dass er beim Herauswinden aus der Rekursion die in dem Rekursionsschritt hinzugefügten Felder wieder „vergisst” (also ein korrektes Backtracking mit richtigem pulsierenden Speicher). Einen Klon der Liste zu übergeben ändert leider gar nichts.

 

[Marco13]

Was meinst du denn genau? Sowas wie

list.add(newPosition);
recursion(list);
list.remove(list.size()-1);

!?

 

[ayrton89]

Ich seh schon, es wird Zeit den Code zu posten.

private void findPath( ArrayList<Field> wayPart ) {
		Field f = wayPart.get( wayPart.size()-1 );
		if( f.equals( END_FIELD ) ) {
			finishWays.add( (ArrayList<Field>) wayPart.clone() );
			return;
		} else {
			for( Field g : getTouchedFields( f ) ) {
				if( !g.isBlocked() && !wayPart.contains(g) ) {
					wayPart.add(g);
					findPath( wayPart );
				}
			}
		}
	}

Ganz klassisches Backtracking, nur dummerweise werden Objekte augenscheinlich per Referenz übergeben. Jedenfalls wird nach dem Ende einer Funktionsinstanz nicht der Wert der als letztes auf dem Rücksprungmarkenkeller liegt genommen, sondern der vollständige Weg behalten. Stichwort pulsierender Speicher

 

[0x7F800000]

"Design graphs, not algorithms" (S. Skiena)
:autsch:
Was auch immer du da anstellst: am ende ist es doch sowieso ein wegsuchalgorithmus auf irgendeinem Graphen, und die lassen sich alle wunderbar in java implementieren... ???:L

 

[ayrton89]

"Design graphs, not algorithms" (S. Skiena)
:autsch:
Was auch immer du da anstellst: am ende ist es doch sowieso ein wegsuchalgorithmus auf irgendeinem Graphen, und die lassen sich alle wunderbar in java implementieren... ???:L

Danke für die Antwort. Könntest du das etwas konkretisieren? Wie soll ich es denn implementieren?

 

[Marco13]

list.add(newPosition);
recursion(list);
list.remove(list.size()-1);

->

wayPart.add(g);
findPath( wayPart );
wayPart.remove(wayPart.size()-1);

!?!?!?

 

[ayrton89]

list.add(newPosition);
recursion(list);
list.remove(list.size()-1);

->

wayPart.add(g);
findPath( wayPart );
wayPart.remove(wayPart.size()-1);

!?!?!?

Ja leider funktioniert das auch nicht, er hängt sich da irgendwie in einer Endlosschleife auf.

 

[ayrton89]

"Design graphs, not algorithms" (S. Skiena)
:autsch:
Was auch immer du da anstellst: am ende ist es doch sowieso ein wegsuchalgorithmus auf irgendeinem Graphen, und die lassen sich alle wunderbar in java implementieren... ???:L

Also tut mir leid aber das ist einfach Unsinn. Der Backtracking-Algorithmus ist wie geschaffen für genau solche Probleme, denn er täte wunderbar einfach und schnell genau das was ich von ihm will, wenn die Java-eigenen Konzepte mir nicht einen Strich durch die Rechnung machen würden.

 

[André Uhres]

Ich bin nicht sicher, ob das hilft, aber ich hatte sowas mal mit einem Stack gelöst, etwa so:

while(visitedCells < totalCells && currentCell != finishPoint){
    nextCell = nextNonvisitedNeighborCell(currentCell);
    if(nextCell == null){
        currentCell.backtrack = true;
        currentCell = stack.pop();
    }else{
        stack.push(currentCell);
        currentCell = nextCell;
        visitedCells++;
    }
}

Gruß,
André

 

[0x7F800000]

Könntest du das etwas konkretisieren? Wie soll ich es denn implementieren?

Das weiß ich nicht, da mir von der Struktur deines Programms nichts bekannt ist. Da du von "Feldern" sprichst, glaube ich nicht, dass du dir die Mühe gegeben hättest, aus vielen Kästchen einen kleinen einfachen expliziten Graphen zu extrahieren (das ist schon eine menge Programmieraufwand. Ich weiß jetzt nicht, ob das wirklich so gemacht wird, aber imho wäre es eine tolle idee, die gesammte begehbare Fläche in sternförmige, oder gar konvexe, Gebiete zu unterteilen, und die Zentren dieser Gebiete zu Knoten eines Graphen zu machen, und diese einfach durch direkte Kanten zu verbinden. Dann hätte man einen ziemlich kleinen explizit gegebenen Graphen, und könnte darauf sofort die bekannten Wegsuchalgos a'la Dijkstra loslassen.)

Könntest du also vielleicht erläutern, in welcher Form du die Umgebung speicherst? ???:L

Also tut mir leid aber das ist einfach Unsinn. Der Backtracking-Algorithmus ist wie geschaffen für genau solche Probleme, denn er täte wunderbar einfach und schnell genau das was ich von ihm will, wenn die Java-eigenen Konzepte mir nicht einen Strich durch die Rechnung machen würden.

Ähm, what? Was ist denn "Backtracking" deiner meinung nach? Stinknormale Tiefensuche auf Graphen ist auch "Backtracking", kannst es doch nennen wie du willst, ändert nichts an der Funktionsweise..

 

[Marco13]

Ein Versuch - hingehackt - wenn's "anders ist als bei dir" gibt's da ne ganz einfache Lösung dafür...

import java.util.*;


class Field
{
    private String name;
    List<Field> touched = new ArrayList<Field>();

    public Field(String name)
    {
        this.name = name;
    }

    public boolean isBlocked()
    {
        return false;
    }

    public String toString()
    {
        return name;
    }

}


class BacktrackingTest
{

    public static void main(String args[])
    {
        new BacktrackingTest();
    }

    Field END_FIELD;
    ArrayList<List<Field>> finishWays = new ArrayList<List<Field>>();


    public BacktrackingTest()
    {
        Field f = new Field("f");
        Field f0 = new Field("f0");
        Field f1 = new Field("f1");
        Field f2 = new Field("f2");
        f.touched.add(f0);
        f.touched.add(f1);
        f.touched.add(f2);

        Field f10 = new Field("f10");
        Field f11 = new Field("f11");
        Field f12 = new Field("f12");
        f1.touched.add(f10);
        f1.touched.add(f11);
        f1.touched.add(f12);


        Field end = new Field("end");

        f10.touched.add(f);
        f11.touched.add(end);

        END_FIELD = end;

        ArrayList<Field> wayPart = new ArrayList<Field>();
        wayPart.add(f);
        findPath(wayPart);
        System.out.println(finishWays);
    }




    private List<Field> getTouchedFields(Field f)
    {
        return f.touched;
    }



    private void findPath(ArrayList<Field> wayPart)
    {
        Field f = wayPart.get(wayPart.size() - 1);
        if (f.equals(END_FIELD))
        {
            finishWays.add((ArrayList<Field>) wayPart.clone());
            return;
        }
        else
        {
            for (Field g : getTouchedFields(f))
            {
                if (!g.isBlocked() && !wayPart.contains(g))
                {
                    wayPart.add(g);
                    findPath(wayPart);
                    wayPart.remove(wayPart.size()-1);
                }
            }
        }
    }
}

 

[ayrton89]

Mein Programm ist so strukturiert, dass ich eine Labyrinth-Klasse habe, deren Konstruktor die Breit und Höhe (also jeweils Anzahl der Felder) entgegennimmt. Felder selbst sind Objekte vom Typ Field, diese haben eine x- und eine y-Koordinate und eine boolean-Eigenschaft, ob sie ein Hindernis enthalten oder nicht (isBlocked). Ein Labyrinth hat wie gesagt im Wesentlichen eine Breite und eine Höhe, und eine beliebige Anzahl an Hindernissen (blockierten Feldern). Außerdem gibt es die Methode getTouchedFields(Field f), die alle Nachbarfeldern, sofern vorhanden, eines Feldes zurückgibt.

Und richtig, Backtracking ist im Prinzip systematische Tiefensuche auf einem Graphen. Dieser „Graph” ist in meinem Fall das Labyrinth, bzw. dessen nicht blockierte Felder.

Dijkstra ist in dem Fall zwar prinzipiell möglich (wenn auch sehr aufwändig), allerdings gibt dieser die Wege zu allen Feldern, ich will aber nur den Weg zu genau einem Feld, nämlich dem END_FIELD.

 

[0x7F800000]

Ookay...
Meinst du sowas?
[highlight=Java]
import java.util.*;

public class Labyrinth{

String mapData=
"########################################"+
"# ## ## ## ####### #"+
"# ### ## ######## ## ##### ###### ### #"+
"# ## ## #### ### # ## ### ## #"+
"## ## ### ##### ###### ### ## ##"+
"## ######### ### ###### ###### ### ## #"+
"## #### ### #### #### ### #"+
"### ### ## ### #### ######## ## #"+
"### # ####### ## ## ## ##"+
"# # # ####### ## ## ###### ## ## ## #"+
"# ### # ## ## # ## ## ### #"+
"# ########## ## ### # ######### ## #"+
"# ############ ## # ## ## ##"+
"# ### ## ### ## ######## ###### #"+
"# ######## ## ### ## # ### # ## #"+
"# #### ## ## #### # # #"+
"#### # ### ############ ## # # ####"+
"# # ###### ## ## ## # ### ####"+
"# ## ### ### ## ## # #"+
"######### ######## ## ############# ##"+
"#################### ## ## ## #"+
"# ## ## ## ## ## ## ####### ##"+
"# ### ## ######## ## ## ## ## ####### ##"+
"# ## ## #### ### ## ## ## ## ####### ##"+
"## ## ### # # ## ####### ##"+
"## ######### ### ## ## ############## ##"+
"## #### ### # ##### ##"+
"### ### ## ### #### ##### ### ##"+
"### # ####### ## ## ### ##"+
"########################################";
int w=40, h=30;

public static class Point{
int x,y;
Point(int _x, int _y){ x=_x; y=_y; }

List<Point> getNeighbors(boolean[][] map){
int w=map.length;
int h=map[0].length;

List<Point> neighbors=new LinkedList<Point>();
for(int i:new int[]{x-1,x+1}){
if(i<0 || i>=w) continue;
if(map[y]){
neighbors.add(new Point(i,y));
}
}
for(int i:new int[]{y-1,y+1}){
if(i<0 || i>=h) continue;
if(map[x]){
neighbors.add(new Point(x,i));
}
}
return neighbors;
}
@Override
public String toString(){ return "("+x+"|"+y+")"; }
@Override
public boolean equals(Object other){
return other instanceof Point
&& ((Point)other).x == this.x
&& ((Point)other).y == this.y;
}
}

boolean[][] map=new boolean[w][h];
{
for(int x=0; x<w; x++){
for(int y=0; y<h; y++){
map[x][y]=mapData.charAt(y*w+x)==' ';
}
}
}

//######################################################################### IRGENDEINEN WEG SUCHEN

public List<Point> deepFirstSearch(Point from, Point to){
return deepFirstSearch(from,to,new boolean[w][h]);
}

private LinkedList<Point> deepFirstSearch(Point from, Point to, boolean[][] visited){
//diesen punkt als besucht markieren
visited[from.x][from.y]=true;

//wenn ziel erreicht: rekursionsende
if(from.equals(to)){
LinkedList<Point> path=new LinkedList<Point>();
path.add(to);
return path;
}

//guggen, ob von einem nachbar das ziel erreichbar ist
for(Point p:from.getNeighbors(map)){
//nachbar muss unbesucht und begehbar sein
if(!visited[p.x][p.y] && map[p.x][p.y]){
LinkedList<Point> path=deepFirstSearch(p,to,visited);
if(path!=null){
path.addFirst(from);
return path;
}
}
}

//kein weg gefunden
return null;
}


public String toString(Point... markedPoints){
StringBuilder b=new StringBuilder();
for(int y=0; y<h; y++){
for(int x=0; x<w; x++){
if(Arrays.asList(markedPoints).contains(new Point(x,y))){
b.append("* ");
}else{
b.append(map[x][y]?" ":"||");//(char)0+""+(char)0);
}
}
b.append('\n');
}
return b.toString();
}

public static void main(String..._){
Labyrinth lab=new Labyrinth();

Point startPoint, target=new Point(1,1);


while(true){

startPoint=target;
target=null;
Random rand=new Random();
while(target==null){
int x=rand.nextInt(lab.w);
int y=rand.nextInt(lab.h);
if(lab.map[x][y]){
target=new Point(x,y);
}
}


Collection<Point> path=lab.deepFirstSearch(startPoint,target);

if(path!=null){
for(Point path){
for(int i=0; i<40; i++) System.out.println();
System.out.println(lab.toString(p,target));
try{
Thread.sleep(200);
}catch(Exception e){}
}
}else{
continue;
}

for(int i=0; i<40; i++) System.out.println();
System.out.println(lab.toString(path.toArray(new Point[path.size()])));
try{
Thread.sleep(1500);
}catch(Exception e){}

}
}
}
[/highlight]

(beim asuführen bitte die Konsole etwas in die höhe ziehen, hatte keine lust eine ordentliche animation zu basteln^^)

Bringt's dich weiter?

bemerkung: es ist besser, solche informationen wie "visited j/n" direkt in den Zellen unterzubringen, wie du es getan hast, ich habe mir hier nicht so doll viele gedanken gemacht, deswegen ist das etwas plump mit zwei arrays gelöst worden, ist eigentlich nicht so schön.