Ein Zufallsweg bzw. Weg in einer 2dim Matrix finden.

[23]

Hallo,

ganz einfach:

Ich habe eine 2dim int Matrix, bei der alle Felder erstmal 0 sind. Ziel ist es von einem Punkt A zu einem Punkt B zugelangen. Ein gültiger Schritt in einem Weg wird durch den Wert 1 innerhalb eines Indexes repräsentiert, also z.B. auf (6,6) = 1.

Bestimmte Felder werden mit -1 belegt, -1 bedeutet hier darf kein Schritt vollführt werden, d.h. also hier kann keine 1 gesetzt werden.

Ein Feld der Matrix hat im idealen Fall 9 Nachbarfelder und diese dürfen als nächster Schritt erhalten.
*EDIT*
Nur 4 Nachbarn, digonal ist uninteressant!

Also wenn ich von (0,0) starte setz ich 1 in (0,0) und dann z.B. 1 in (0,1) danach 1 in (0,2) und wenn bei (0,3) das Ziel ist wäre ich da und ein Weg wäre gefunden.

Ich möchte nun von einem Punkt (5,5) zu (56,87) kommen. Wie implementiert man sowas?

Ich hoffe hier versteht was ich möchte, ich habe noch nichts implementiert...

package matrix;

public class Matrix {

	/** 4 rows and 7 columns **/
	private int [][] matrix = {
			{0,0,0,0,-1,0,0},
			{0,-1,0,0,0,0,0},	
			{0,-1,0,0,0,-1,0},	
			{0,0,-1,0,0,0,0},	
	};
	
	private int startRow;
	private int startColumn;
	
	private int targetRow;
	private int targetColumn;
	
	public Matrix() {
		
		startRow = 0;
		startColumn = 0;
		
		targetRow = 3;
		targetColumn = 6;
		
	}
	
	public static void main(String[] args) {
		

	}

}

 

[andiv]

Für das Finden von kürzesten Wegen in Graphen gibt es den Algorithmus von Dijkstra und den A*-Algorithmus. Beide werden ausführlich in der Wikipedia beschrieben. Für einen zufälligen Weg kenn ich jetzt keinen fertigen Algorithmus, aber eventuell lässt sich einer der genannten leicht modifizieren um ein Zufallselement mit reinzubringen.

 

[23]

Hi,

kenne diesen Algo und der bringt hier nichts. Es geht nicht um den kürzesten Weg sondern um irgendein Weg.

Das ganze ist ähnlich einem Labyrinth und rekursives Backtracking scheint die Lösung zu sein.

Kann mir jemand helfen?

 

[andiv]

Und was spricht dagegen die Algorithmen so zu modifizieren, dass nicht der kürzeste Weg weiterverfolgt wird sondern ein zufälliger? Und wenn du dir sicher bist dass du das ganze mit rekursivem Backtracking machen willst, warum machst du es dann nicht? Wo ist das Problem, woran hängst du?

 

[23]

Ich hab diese Technik noch nicht drauf und weis keinen Anfang

 

[Samuel72]

Ungefähr so:

void geheFeld(int x, int y) {
  if ((x==56) && (y==87)
    // fertig
  if (matrix[x][y]==-1)
    return;
  matrix[x][y] = -1;
  geheFeld(x-1,y);
  geheFeld(x+1,y);
  geheFeld(x,y-1);
  geheFeld(x,y+1);
  matrix[x][y] = 0;
}

Du musst allerdings noch verhindern, dass er über den Rand hinausläuft.
(Also entweder den ganzen Rand mit -1 besetzen oder die Werte abprüfen).

 

[23]

Ich hab etwas...

package matrix;

public class Matrix {

	/** 4 rows and 7 columns **/
	private int [][] matrix = {
			{0,0,0,0,-1,0,0},
			{0,-1,0,0,0,0,0},	
			{0,-1,0,0,0,-1,0},	
			{0,0,-1,0,0,0,0},	
	};
	
	private int startRow;
	private int startColumn;
	
	private int targetRow;
	private int targetColumn;
	
	private int row = matrix.length;
	private int column = matrix[0].length;
	
	public Matrix() {
		
		startRow = 0;
		startColumn = 0;
		
		targetRow = 3;
		targetColumn = 6;
		
		back(startRow, startColumn);
		
	}
	
	private void back(int nextRow, int nextColumn) {
		
		System.out.println(nextRow + " " + nextColumn);
		
		if(nextRow == targetRow && nextColumn == targetColumn) {
			System.out.println("done");
			return;
		}
		
		if(canGo(nextRow-1, nextColumn)) {
					
			//N
			matrix[nextRow][nextColumn] = 1;
			back(nextRow-1, nextColumn);
			
		} else if(canGo(nextRow, nextColumn+1)) {
			
			//O
			matrix[nextRow][nextColumn] = 1;
			back(nextRow, nextColumn+1);
			
		} else if(canGo(nextRow+1, nextColumn)) {
			
			//S
			matrix[nextRow][nextColumn] = 1;
			back(nextRow+1, nextColumn);
			
		} else if(canGo(nextRow, nextColumn-1)) {
			
			//W
			matrix[nextRow][nextColumn] = 1;
			back(nextRow, nextColumn-1);
			
		} else {
			
			return;
			
		}
						
	}
	
	private boolean canGo(int nextRow, int nextColumn) {
		
		if(nextRow < 0 || nextRow >= row)
			return false;
		
		if(nextColumn < 0 || nextColumn >= column)
			return false;
		
		if(matrix[nextRow][nextColumn] == -1 || matrix[nextRow][nextColumn] == 1)
			return false;
		
		return true;
		
	}
	
	public static void main(String[] args) {
		
		new Matrix();

	}

}

Wie bekomme ich nun Backtracking rein? Also wenn er an einer Stelle nicht mehr weiterkommt?

*Edit*
Solangsam kommts

 

[23]

@Wie soll der Dijkstra mir bei der gegebenen Matrix helfen? Das ist ja keine Adjazenzmatrix... ich wüßte auch nicht wie ich das umtransformieren sollte?

Kannst du mir das evtl. erklären?

 

[Marco13]

Dijkstra auf so einer Matrix wäre etwas fummelig, und das brauchst du ja auch nicht. Samuel72 hat's doch schon engedeutet?! Mit

void geheFeld(int x, int y) {
    if (x<0 || x >= w) return;
    if (y<0 || y >= h) return;
    ...

werden die Abfragen auch einfacher.

 

[23]

So gehts...

	private boolean backtracker(int nextRow, int nextColumn) {
		
		if((nextRow < 0 || nextRow >= row || nextColumn < 0 || nextColumn >= column) 
				|| (matrix[nextRow][nextColumn] == 1 || matrix[nextRow][nextColumn] == -1))
			return false;
		
		if(nextRow == targetRow && nextColumn == targetColumn) {
			System.out.println("--done--");
			matrix[nextRow][nextColumn] = 2;
			return true;
		}
		
		matrix[nextRow][nextColumn] = 1;
		
		return (backtracker(nextRow-1, nextColumn) ||
				backtracker(nextRow, nextColumn+1) ||
				backtracker(nextRow+1, nextColumn) ||
				backtracker(nextRow, nextColumn-1));
		
	}

*Edit*

ich habe mich geirrt der kürzeste Weg wäre doch optimal... Wie kann ich dies erreichen?

*Edit2*
Mit meiner neuen Methode backtracker() komme ich durch das Labyrinth und er geht auch Sackgassen zurück (Backtracking) allerdings hätte ich nun gerne eine Liste mit den Feldern, welche direkt also ohne Sackgasse zum Ziel führen... mir fällt grade kein guter Weg ein dies noch zu implementieren... hat jemand eine Idee? Das sollte ja nicht so schwer sein...

Das diese Methode nicht den schnellsten Weg findet ist erstmal egal...

--------------------
0 0 0 0 -1 0 0
0 -1 0 0 0 0 0
0 -1 0 0 0 -1 -1
0 0 -1 0 0 0 0
--done--
true
--------------------
1 1 1 1 -1 1 1
1 -1 0 1 1 1 1
1 -1 0 0 1 -1 -1
1 0 -1 0 1 1 2

Dies fetten 1er werden auch durchlaufen jedoch sind diese für mich eigentlich uninteressant. Wie kann ich diese "filtern"? Ich brauche den Weg ohne Sackgassen...

*Edit3*
So sollte es klappen odeR?

	private boolean backtracker(int nextRow, int nextColumn, LinkedHashMap<String,I> hash) {
		
		if((nextRow < 0 || nextRow >= row || nextColumn < 0 || nextColumn >= column) 
				|| (matrix[nextRow][nextColumn] == 1 || matrix[nextRow][nextColumn] == -1))
			return false;
		
		if(nextRow == targetRow && nextColumn == targetColumn) {
			System.out.println("--done--");
			matrix[nextRow][nextColumn] = 2;
			return true;
		}
		
		matrix[nextRow][nextColumn] = 1;
		
		if(!hash.containsKey(nextRow + "" + nextColumn))
			hash.put(nextRow + "" + nextColumn, new I(nextRow, nextColumn));
		
		boolean moveOn = (backtracker(nextRow-1, nextColumn, hash) ||
						backtracker(nextRow, nextColumn+1, hash) ||
						backtracker(nextRow+1, nextColumn, hash) ||
						backtracker(nextRow, nextColumn-1, hash));
		
		if(moveOn)
			return true;
				
		hash.remove(nextRow + "" + nextColumn);
		
		return false;
			
	}

 

[Tomate_Salat]

habe mir das nicht komplett durchgeschaut, aber ich habe zuhause spaßeshalber auch mit soetwas begonnen. Jeder Wegpunkt ist dabei ein Objekt, welches sich merkt, ob es schonmal betreten worden ist + ob es noch unbetretene Abzweigungen davon gibt. In einer Liste speichere ich mir die History und wenn ich in einer Sackgasse lande, gehe ich solange zurück, bis ich einen Wegpunkt finde, der noch unbetretene abbiegungen besitzt. Mein nächster Schritt ist der kürzeste Weg, auch für den habe ich bereits eine Idee:
Wenn ich am ziel bin, gehe ich trotzdem wieder zurück und teste neue Wege, speichere mir diese Historie aber in einer separaten liste und halte mir nur die, mit den wenigstens Wegpunkten. Das ist wohl nicht der schnellste weg, aber es ist einer ^^

 

[s4ke]

Wenn es ohnehin egal ist, welcher Weg genommen wird, warum dann nicht gleich Dijkstra?

EDIT: Dann doch ohne Dijkstra.

/**
 * Klasse GraphMatrix
 * Klasse f�r einen ungerichteten, gewichteten Graphen
 * Als Datenstruktur wird eine Adjazenzmatrix verwendet
 * @author U.Freiberger 
 * @version 1.0
 * geaendert von Robert Kraus
 * geaendert von Martin Braun
 */

public void wegeSuchen(String startKnoten, String zielKnoten)
     {
        int startNummer = knotenNummer(startKnoten);
        int zielNummer  = knotenNummer(zielKnoten);
        
        if ((startNummer != -1) && (zielNummer != -1) && (startNummer != zielNummer))
        {
            for (int i=0 ; i<anzahlKnoten; i++)
                besucht[i]=false;
            ablaufen2(startNummer, zielNummer, startKnoten, 0);
        }
    }


private void ablaufen2(int knotenNummer, int zielKnotenNummer, String pfad, int laenge)
     {
    	 besucht[knotenNummer] = true;
    	 if(zielKnotenNummer == knotenNummer)
    	 {
    		 System.out.println("Weg gefunden " + pfad + " mit der Länge " + laenge);
    	 }
	     for(int i = 0; i < anzahlKnoten; i ++)
	     {
	    	if((!besucht[i]) && (matrix[knotenNummer][i] > 0))
	    	{
	    		ablaufen2(i,zielKnotenNummer, pfad + "/" + knoten[i].bezeichnungGeben(), laenge + matrix[knotenNummer][i]);
	    	}
	     }
	     besucht[knotenNummer] = false;    	 
     }

Das ist jetzt eine Version, die auf dem basiert, was wir in der Schule behandelt haben. Und sucht dir alle möglichen Wege raus und gibt nur funktionierende zurück. Sollte eigentlich relativ einfach abzuändern sein für deine Zwecke.

War im Grunde für mich Wiederholung fürs Abitur. Danke dafür . Und die deutschen Bezeichnungen sind bitte zu übersehen, das komplette Programm wurde in Deutsch verfasst.

EDIT:

Oder gehts hier gar nicht um Graphen, wenn nicht dann sry :shock:

EDIT2: Okay, das ist jetzt peinlich... Stand sogar vorher im Text, dass es keine Adjazentmatrix ist... :autsch:

 

[Samuel72]

Mit meiner oben genannten Methode bekommst du den kürzesten Weg, wenn du bei [c]//fertig[/c] nicht abbrichst, sondern den gerade gefundenen Weg mit dem ggf. schon gefundenen vergleichst und den kürzeren der beiden speicherst.
Dazu musst du halt irgendwie den jeweiligen Weg (und v.a. seine Länge) speichern.

 

[Samuel72]

Mir ist noch eine etwas performantere Methode eingefallen, mit Wellen:
Markiere das Ausgangsfeld mit 1.
Nun markiere alle unmarkierten Nachbarn von 1-er-Feldern mit 2,
dann alle unmarkierten Nachbarn von 2-er-Feldern mit 3, usw,
bis du beim Ziel bist.
Den kürzesten Weg bekommst du durch Rückwärtsgehen - jeweils auf das um 1 niedrigere Feld.

 

[Illuvatar]

Bevor du dich noch 3 mal umentscheidest ob du den kürzesten Weg brauchst oder nicht, nimm doch einfach A*.
Der ist einfach, es gibt ne Menge Beispielcode, ist schnell (und Laufzeit scheint hier eh nicht soo wichtig zu sein) - und auch wenn du nicht unbedingt den kürzesten Weg bräuchtest, auf jeden Fall hast du damit einen Weg (der eben zufälligerweise tatsächlich der kürzeste ist und damit gehst du auch nicht in Sackgassen oder im Viereck...)

 

[23]

Wie kann ich den A* auf dieses einfache Beispiel anwenden?

Hier mal den ganzen Code:

package matrix;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Stack;

public class Matrix {

	/** 6 rows and 7 columns **/
	/*private int [][] matrix = {
			{-1,0,-1,0,0,0,0},
			{0,-1,0,-1,-1,0,0},	
			{0,-1,0,-1,-1,0,0},	
			{0,0,0,0,-1,0,-1},	
			{0,-1,0,-1,-1,0,0},
			{0,-1,0,0,0,0,0},
	};*/
	
	private int [][] matrix = {
			{0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0},	
			{0,0,0,0,0,0,0},	
			{0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0},
	};
	
	private int startRow;
	private int startColumn;
	
	private int targetRow;
	private int targetColumn;
		
	private int row = matrix.length;
	private int column = matrix[0].length;
		
	private Stack<I> test = new Stack<I>();
	
	public Matrix() {
		
		startRow = 5;
		startColumn = 0;
		
		targetRow = 5;
		targetColumn = 2;
		
		printMatrix();
		System.out.println(backtracker(startRow,startColumn,test));
		printMatrix();
			
	}
	
	private void printMatrix() {
		
		System.out.println("--------------------");
		
		System.out.print("\t");
		
		for(int j = 0; j < column; j++)
			System.out.print(j + "\t");
		
		System.out.println("");
			
		for(int i = 0; i < row; i++) {
			
			System.out.print(i+"\t");
			
			for(int j = 0; j < column; j++) {
				
				System.out.print(matrix[i][j] + "\t");
				
			}
			
			System.out.println("");
			
		}
		
	}
	
	private boolean backtracker(int nextRow, int nextColumn, Stack<I> hash) {
		
		if((nextRow < 0 || nextRow >= row || nextColumn < 0 || nextColumn >= column) 
				|| (matrix[nextRow][nextColumn] == 1 || matrix[nextRow][nextColumn] == -1))
			return false;
		
		if(nextRow == targetRow && nextColumn == targetColumn) {
			matrix[nextRow][nextColumn] = 2;
			return true;
		}
		
		matrix[nextRow][nextColumn] = 1;
				
		hash.push(new I(nextRow, nextColumn));
		
		boolean moveOn = (backtracker(nextRow-1, nextColumn, hash) ||
						backtracker(nextRow, nextColumn+1, hash) ||
						backtracker(nextRow+1, nextColumn, hash) ||
						backtracker(nextRow, nextColumn-1, hash));
		
		if(moveOn)
			return true;
				
		hash.pop();
		
		return false;
		
	}
		
	public static void main(String[] args) {
		
		new Matrix();

	}
	
	public class I {
		
		public int x;
		public int y;
		
		public I(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
	}

}

Dieser Algo ist doch nicht das richtige da er zu lange Wege geht... In meiner Matrix kommt es höhsten 1-2 mal vor das ein Hinterniss also -1 auftritt...

Ich würde gerne was lernen, kann mir also jemand bitte mit etwas Code helfen? Ziel ist es von Start nach Target zu kommen mit einem schnell Weg und dem umgehn von Hinternissen, falls welche auftauchen...

Danke

*Edit*
Was evtl. helfen würde, wäre wenn er versucht einen direkt Weg über 2 knicke zu gehn also z.B. erst solange rechts bis x von start = x von ziel und dann nach oben versuchen.

 

[Illuvatar]

Let me google that for you

 

[23]

Warum kann hier keine mal seine Lösung zeigen und etwas dazu erklären?
Hier sind doch gute Leute... in den anderen Foren wird dies doch auch gemacht...

 

[Tomate_Salat]

-Weil vllt nicht jeder gerade eine fertige Lösung parat hat
-Weil nicht jeder Lust hat deine Arbeit zu erledigen (dafür gibts die Jobbörse hier)
-Weil manche Lösungen nur indirekt zu deiner passen
-Weil das dein Problem ist und du dich um eine Lösung bemühen sollst
-Weil wir zum Helfen und nicht zum Lösen da sind?

waren das genug Gründe?

 

[23]

Das ist wirklich schade...

 

[Tomate_Salat]

nein Schade ist, dass du Google als Hilfe ablehnst und dich noch darüber beschwerst, obwohl dort genau das zu finden ist, was du dir wünscht. Die Eigeninitiative reicht wohl nicht mehr aus, um sich mal die Ergebnisse anzusehen, die der Link von Illuvatar bringt. Mind. eines der Ergebnisse bringt dich zu einer Seite, wo du ein komplettes Beispiel herunterladen kannst.

 

[23]

Hab mich für astar entschieden und auch selbst implementiert

Nun gibts neue Probleme ;-)
http://www.java-forum.org/allgemeine-java-themen/118008-astar-heuristik.html#post760492