Backtracking Problem

[sra]

Hallo

Ich habe ein Problem mit Backtracking. Ein ähnliches Problem habe ich schon gestern ins C# Board geschrieben, und mein Code ist auch in C#. Allerdings bekomme ich da kaum Rückmeldung.

Darum (und weil es sowieso nichts sprachspezifisches ist, sondern der Algorithmu entscheidend ist) versuche ich es noch hier.

Also... Ich versuche per Backtracking jeden Weg aus einem Labyrinth zu finden. Die Zahlen, spielen dabei zunächst nur eine zweitrangige Rolle, und müssen auch gar nicht beachtet werden.

Mein Problem ist, dass ich - einmal in einer Sackgasse angekommen - nciht mehr rauskomme, und das Programm frühzeitig beendet.

Hier der Code (lasst euch nicht einschüchtern, das meiste ist nur die switch/case anweisung):

using System;

namespace sonja
{
	class SOI_BackTrack
	{
		[STAThread]

		public static void Main(string[] args)
		{
			int actTime = 0;
			findBestPath('x', actTime);
			Console.WriteLine(bestTime);
			Console.ReadLine();
			Console.ReadLine();
		}

		static int r=0, s=0, bestTime=32000; // r=Reihe s=Spalte
		/*static char[,] Lab = {{'A','1','4','7','X'},
				{'1','9','5','X','2'},
				{'X','4','6','7','9'},
				{'1','X','9','1','1'},
				{'7','9','3','7','E'}};*/
				
		static char[,] Lab = {{'A','X','X','X','X'},
				{'1','X','5','X','2'},
				{'5','X','6','7','9'},
				{'1','X','X','X','X'},
				{'7','9','3','7','E'}};

		public static bool findBestPath(char compass, int actTime)
		{
			switch(compass)
			{
				case 'x': break;

				case 'r': 
					if((s+1 <= 4) && (Lab[r,s+1] != 'X'))  
					{ 
						Lab[r,s] = 'X';
						s++;
						if ((Lab[r,s] != 'E') && (Lab[r,s] != 'A')) 
						{
							actTime += Convert.ToInt32(Lab[r,s].ToString());
						}
					} else {
						return (false);
					} break;

				case 'u': 
					if((r+1 <= 4) && (Lab[r+1,s] != 'X')) 
					{ 
						Lab[r,s] = 'X'; 
						r++; 
						if ((Lab[r,s] != 'E') && (Lab[r,s] != 'A')) 
						{
							actTime += Convert.ToInt32(Lab[r,s].ToString());
						}
					} else { 
						return (false); 
					} break;

				case 'l': 
					if((s-1 >= 0) && (Lab[r,s-1] != 'X')) 
					{ 
						Lab[r,s] = 'X';
						s--;
						if ((Lab[r,s] != 'E') && (Lab[r,s] != 'A')) 
						{
							actTime += Convert.ToInt32(Lab[r,s].ToString());
						}
					} else {
						return (false);
					} break;

				case 'o': 
					if((r-1 >= 0) && (Lab[r-1,s] != 'X'))
					{
						Lab[r,s] = 'X';
						r--;
						if ((Lab[r,s] != 'E') && (Lab[r,s] != 'A')) 
						{
							actTime += Convert.ToInt32(Lab[r,s].ToString());
						}
					} else {
						return (false);
					} break;

				default: return (false);
			}
			
			Console.Write(Lab[r,s]);
			Console.WriteLine(" - " + actTime);

			if(Lab[r,s] == 'E')
			{
				if(actTime < bestTime)
				{
					bestTime = actTime;
				}
				Console.Write("we are the Best");
				return (false);
			}

			if(findBestPath('r', actTime)){ }
			if(findBestPath('u', actTime)){ }
			if(findBestPath('l', actTime)){ }
			if(findBestPath('o', actTime)){ }
			return (false);
		}
	}
}

Eigentlich sollte er, wenn er in eine Sackgasse kommt, und alle wege versperrt sind false zurückgeben, und die aktion also gar nicht machen:

if(findBestPath('r', actTime)){ }
if(findBestPath('u', actTime)){ }
if(findBestPath('l', actTime)){ }
if(findBestPath('o', actTime)){ }
return (false);

Da es doch ganz schön kompliziert ist (wie ich finde), habe ich euch schnell ein Bild erstellt.

Bei Schritt 2 schaut er zuerst rechts. -> ist nicht gespert, also rein da.
In Schritt 3 sieht schaut er rechts -> false, unten -> false, links -> false, oben -> false, also gibt die funktion (if(findBestPath()) { }) false zurück.
Er hat also schritt 2 zu 3 (nach rechts) gar nie gemacht, und versuchts nun neu in schritt 2 unten, wo er fündig wird.

Hoffe ihr wiss was ich meine

 

[Kachelator]

Da es doch ganz schön kompliziert ist (wie ich finde)

Stimmt, ist es. Mir ist aufgefallen, dass findBestPath() nie ein true zurückgibt. Ist das Absicht?

 

[sra]

Ja das ist Absicht.
Enweder er kann noch weiter (in irgendeine Richtung), und dann macht er das, oder er gibt false zurück, wenn es nicht mehr weitergeht.

Die Idee ist ja, dass der Funktionaufruf in der if Anweisung steht, und sobald es irgndwo nicht geht, dann macht er es auch nicht

Auch wenn er schon viel weiter im weg ist, und dann auf eine sackgasse trifft, wird solange false zurückgegeben, bis er wieder an einer "verzweigung" ist, und einen anderen Weg einschalgen kann.

 

[Kachelator]

Du solltest vielleicht die aktuelle Position als Parameter an die Funktion übergeben. Bei jedem rekursiven Aufruf werden die quasi globalen Koordinaten r und s überschrieben. Das kann nicht gut gehen. Für Backtracking muss in irgendeiner Weise Buch geführt werden über vorhergehende Zustände der Suche. Beim rekursiven Aufruf wäre das eventuell gewährleistet, wenn du die Postion übergibst - vorhergehende Zustände liegen dann auf dem Stack. Das ist kompliziert zu erklären, sorry.

 

[sra]

Du meinst, dass wenn ich die Variablen r und s während eines Aufrufes ändere, dann weiss das Programm nicht mehr, wie es vorher war?

Ist es aber nicht so, dass, da der Funktionsaufruf ja im if drinn ist, die Variablen im Endeffekt gar nicht mal berührt werden, da die Funktion ja schlussendlich sowieso false zurückgibt?

Du hast recht. es ist schwer das irgendwie zu formulieren

 

[sra]

also...

in gewisser weise hast du recht. So geht es schon besser.
Es funktioniert zwar immer noch nicht ganz.

Sobald ich den Fehler lokalisiert habe, werde ich mich melden

//edit: Funktioniert nun perfekt! Danke dir Kachelator