Rekursive Funktion mit jedem Durchlauf ändern / Labyrinth durchlaufen

Stiefel2000

Hallo,
da ich letztens wieder Lust zum Programmieren hatte und nichts sinnvolleres finden konnte, habe ich mich an eine Aufgabe gesetzt, die mir vor einiger Zeit mal als Übungsaufgabe diente.
Es geht darum, ein sich in einer Textdatei befindliches Labyrinth zu durchlaufen - es gibt einen Start- und einen Endpunkt.

Nachdem ich mein Programm nun stolz zum Laufen bekommen habe, gibt es noch ein paar Schwierigkeiten. Eine davon wäre:

Ich benutze eine rekursive Funktion, die dazu dient, sich im Labyrinth "fortzubewegen". Diese Funktion besteht im Wesentlichen aus 4 if-Abfragen (es wird geschaut, ob oben, rechts, unten oder links der Weg frei ist). Nun habe ich mich gefragt, ob ich die Reihenfolge dieser Abfragen irgendwie variieren kann? So dass dass Programm also bei jedem Durchlauf einen neuen Weg wählt (auch die Funktion soll bei jedem Aufruf die Abarbeitungsreihenfolge ändern).

Eine weitere Schwierigkeit habe ich damit, den optimalen Weg zu finden. Ich hatte eine Weile mit dem Rechenaufwand zu kämpfen, konnte das Problem allerdings beseitigen. Nun ist es nur noch ziemlich unschön, dass das Programm immer IRGENDeinen Weg nimmt, praktisch aber nie den kürzesten. Daran zerbreche ich mir schon eine Weile den Kopf - falls also jemand Rat weiß, wäre ich dankbar.

EDIT: Gerade fällt mir noch was weiteres ein: Im Laufe des Programms werden ein paar Tastaturbefehle abgefragt - ich nutze aktuell

char * Puffer = malloc(100 * sizeof(char));
scanf( "%s" , Puffer);

allerdings scheint der scanf-Befehl "überzulaufen", wenn ein Whitespace-Character folgt. Kann ich das irgendwie umgehen? Bei mehreren aufeinanderfolgenden Abfragen kommt es sonst nämlich dazu, dass eine Eingabe gleich mehrere der Abfragen füllt. Ich habe schon mit anderen Befehlen rumexperimentiert, aber zu getc z.B. gibt mir mein eclipse eine Warnung aus, dass die Funktion gefährlich sei.

knivil

Nun habe ich mich gefragt, ob ich die Reihenfolge dieser Abfragen irgendwie variieren kann?

Ja, im einfachsten Fall mit mehr if-Abfragen.

Eine weitere Schwierigkeit habe ich damit, den optimalen Weg zu finden.

Google hilft, ansonsten A*.

Stiefel2000

Soll ich dazu jetzt irgendwas sagen?

Ich habe (inspiriert durch einen der anderen kürzlich hier eröffneten Threads) jetzt folgende Methode gewählt, die momentan allerdings noch ein Problem aufweist:

short Funktion(...)
{	short Counter[4] = {0 , 0 , 0 , 0};
	int x = 155;   //hier sollte nur erstmal irgendein Wert stehen

	beginning:
	srand ( x );
	x = ( rand() % 100 + 1);
	//printf("%i, " , x);  //zur Kontrolle der Werte

	if( Counter[0] == 1 &&  Counter[1] == 1 && Counter[2] == 1 && Counter[3] == 1)
		goto end;
	if( x < 26 && x > 0)
		goto up;
	if( x < 51 && x >= 26)
		goto right;
	if( x < 76 && x >= 51)
		goto down;
	if( x <= 100 && x >= 76)
		goto left;
	else
		goto beginning;

	up:
	Counter[0] = 1;
	if( Bed1 )
	{   Block1;
	}
	goto beginning;

	right:
	Counter[1] = 1;
	if( Bed2 )
	{   Block2;
	}
	goto beginning;

	down:
	Counter[2] = 1;
	if( Bed3 )
	{   Block3;
	}
	goto beginning;

	left:
	Counter[3] = 1;
	if( Bed4 )
	{   Block4;
	}
	goto beginning;

	end:
	return(0);
}

Ich weiß ja, dass goto nicht gern gesehen wird (habe es auch noch nie benutzt und habe es nicht wieder vor), aber zur Erfüllung meiner Zwecke scheint es doch ganz nützlich.
Das große Problem im Moment ist, dass mir rand() keine Zufallswerte liefert. srand scheint stets den gleichen seed auszugeben, wenn die Eingabe identisch ist, rand tut daraufhin auch nicht mehr. Somit kann ich schon vor Programmstart vorhersagen, welche Zahlen in welcher Reihenfolge auftreten.
Ich habe es auch mit srand( time(NULL)) versucht, allerdings ist das ebenfalls untauglich, da die Zeit scheinbar nur einmal pro Sekunde aktualisiert wird, das Programm jedoch im Schnitt eine Laufzeit von unter einer Sekunde haben sollte. Ansonsten wird praktisch jede Bedingung eine ganze Sekunde lang geprüft, für ein rekursives Programm ist das äußerst schlecht.

Ich habe auch schon überlegt, wie ich einen einfachen Zufallsgenerator schreiben könnte, bin jedoch ziemlich einfallslos.

EDIT: google rät mir in diesem Fall stets zu srand und rand, allerdings benötige ich viele Zufallszahlen pro Sekunde. Sogar mein Taschenrechner hat sowas wie eine Zufallstaste - so schwer kann doch sowas nicht sein, oder?

knivil

Man initialisiert den Zufallszahlengenerator nur einmal mit srand().

Ach ja: Das kommt dabei heraus, wenn man irgendwelche Ideen wie "goto ist gar nicht schlimm" vertritt. Eine einfache Schleife haette es auch gebracht.

Stiefel2000

Du wirfst ja geradezu mit Freundlichkeiten und Verbesserungsvorschlägen um dich! Ich bin dir beinahe dafür dankbar!

Aber im Ernst: Ich habe keine Möglichkeit gesehen, mein Problem mit einer while-Schleife zu lösen, die Rekursion ist die einzige Möglichkeit, die sich wirklich den Weg durchs Labyrinth sucht und sich hinterher problemlos daran "erinnert", wo sie lang gelaufen ist. Vielleicht geht das wirklich anders, aber ich vermute mal, dass der Aufwand hoch wäre.

Ob ich von goto etwas halte oder nicht, habe ich doch nirgendwo behauptet. Ich bin der Meinung, dass der Quelltext in zweiter Linie lesbar und in erster (!) Linie funktional sein sollte. Ich habe bisher jegliches goto vermieden, gestern hier gefragt, wie ich ein Zufallselement in mein Programm bauen könnte und leider hat mir niemand einen Tipp gegeben. Der einzige Weg, den ich sah, war das goto. Und noch etwas: Bei einer recht kurzen Funktion die gotos nicht einfach aus Faulheit, sondern aus Zweckmäßigkeit zu nutzen (wie gesagt, ich bin für Vorschläge offen), sehe ich keinesfalls als problematisch an.

Was die Zufallswerte angeht: Ich habe noch immer nicht rausgefunden, wie ich wenigstens einigermaßen zufällige Werte erhalte. Ich probiere es als nächtes mal aus, das srand außerhalb des sich wiederholenden Programmteils einzubauen.

knivil

Was die Zufallswerte angeht: Ich habe noch immer nicht rausgefunden, wie ich wenigstens einigermaßen zufällige Werte erhalte.

srand() aus der Funktion nehmen und nur einmal am Anfang des Programms aufrufen. am besten so:

int main()
{
  srand( ... );

  ... do what you want.

  return 0;
}

Die obige Funktion kann leicht mittels while if/elseif bzw. switch umgeschrieben werden. Probiere es einfach mal selbst. (Manche ignorieren Programme mit goto ganz, da spielt es keine Rolle, was du von goto haelst, einzig und allein zaehlt, dass du es benutzt.)

Vorschlag ohne goto:

short Funktion(...)
{    short Counter[4] = {0 , 0 , 0 , 0};
    int x = 155;   //hier sollte nur erstmal irgendein Wert stehen

	 for(;;)
	 {
	    x = ( rand() % 4);

        //srand ( x ); stattdessen srand ( time(NULL) ); zu Beginn von main

        if( Counter[0] == 1 &&  Counter[1] == 1 && Counter[2] == 1 && Counter[3] == 1)
            return 0;

        counter[x] = 1;

        switch (x)
        {
            case 0:
                 if(Bed1) 
                 {
                    Block1;
                 }
                 break;

            case 1:
                 if(Bed2) 
                 {
                    Block2;
                 }
                 break;

            ...
        }

}

Stiefel2000

Das mit srand hat funktioniert, zumindest habe ich jetzt schon ein paar verschiedene Durchläufe gesehen :). Also nochmal danke für den Tipp ;).

@ Belli: Das mit dem switch ist ganz gut - warum nimmst du anstatt der for-Schleife keine while-Schleife?
Wo ich gerade den switch-Befehl sehe: Kann ich damit auch "Bereiche" abfragen, also etwas wie:

switch(x)
{     case(<7):
        Code;
      case(<19):
        Code;
}

Ich habe damit letztens ein wenig rumprobiert, fand allerdings keine funktionierende Methode. Wobei ich diese hier noch gar nicht probiert habe :).

EDIT: Ich habe jetzt auf die switch-Methode umgebaut, es scheint alles gut zu funktionieren. Danke nochmal für eure Hilfe - auch dafür, dass ich weiterhin behaupten kann, in keinem meiner Programme kommt ein goto vor ;).

Noch ein EDIT: Mir fällt gerade ein, dass die nächste Programmstufe nach dem kürzesten Weg suchen können sollte. Dazu müsste ich die Rekursionstiefe bestimmen und am Ende alle Werte von Rekursionen vergleichen, die das Ziel erreicht haben. Währenddessen sollten allerdings alle Rekursionen offen gehalten werden, damit nur die mit dem wirklich kürzesten Weg am Ende einen Erfolg meldet und alle anderen (trotz erfolgreicher Suche) einfach "absterben". Hat dazu vielleicht jemand eine grobe Idee? Ich habe schon einiges probiert, allerdings alles ziemlich erfolglos. Zumindest wirkt das Programm durch das Zufallselement jetzt nicht mehr ganz so blöde...

Stiefel2000 schrieb:

@ Belli: Das mit dem switch ist ganz gut - warum nimmst du anstatt der for-Schleife keine while-Schleife?

Ich dachte, wenn ich eine while - Schleife nehme, fragst Du mich, warum ich keine for-Schleife nehme.
Ne, im Ernst, ist egal, kannst die for-instruktion auch durch while(1) ersetzen.

Stiefel2000 schrieb:

Wo ich gerade den switch-Befehl sehe: Kann ich damit auch "Bereiche" abfragen, also etwas wie:
switch(x)
{     case(<7):
        Code;
      case(<19):
        Code;
}

Nein, da gibt es dann nur:

switch(x)
{     case 1:
      case 2:
      case 3:
        ...
      case 6:
        Code;
        break;
      case 7:
      case 8:
        ...
      case 18:
        Code;
        break;
}

Stiefel2000 schrieb:

Noch ein EDIT: Mir fällt gerade ein, dass die nächste Programmstufe nach dem kürzesten Weg suchen können sollte. Dazu müsste ich die Rekursionstiefe bestimmen und am Ende alle Werte von Rekursionen vergleichen, die das Ziel erreicht haben.

Nein, Du brauchst immer nur die bisher kürzeste gefundene. Also die zweite gefundene Lösung vergleichst Du auf Grund der Rekursionstiefe mit der ersten, und verwirfst die längere gleich.
Die nächste gefundene Lösung vergleichst Du mit der, die Du noch hast, und verwirfst wieder die längere, usw.

Stiefel2000

Belli schrieb:

Stiefel2000 schrieb:

@ Belli: Das mit dem switch ist ganz gut - warum nimmst du anstatt der for-Schleife keine while-Schleife?

Ich dachte, wenn ich eine while - Schleife nehme, fragst Du mich, warum ich keine for-Schleife nehme.

:p
Ich habe nicht "while(1)", sondern die erste if-Abfrage des Anweisungsblocks als Abbruchbedingung genommen.

Belli schrieb:

Nein, Du brauchst immer nur die bisher kürzeste gefundene. Also die zweite gefundene Lösung vergleichst Du auf Grund der Rekursionstiefe mit der ersten, und verwirfst die längere gleich.
Die nächste gefundene Lösung vergleichst Du mit der, die Du noch hast, und verwirfst wieder die längere, usw.

Ok, das hätte ich wahrscheinlich schnell gemerkt ;). Aber ich weiß eben noch nicht, wie ich das gut umsetze. Die Rekursion kann ich scheinbar nicht offen halten, außerdem könnte es eine ganze Reihe von erfolgreichen Wegen geben. Somit hätte ich am Ende des Suchalgorithmus eine Zahl, die mir den vermeintlich kürzesten Weg angibt (dazu müsste ich noch dutzende Arrays erstellen...) und müsste das Programm praktisch nochmal laufen lassen, damit der entsprechende Weg auch genutzt wird. Das klingt alles nach ziemlich viel Aufwand für das kleine Programm - ich bin ja schon froh, dass es mittlerweile schnell läuft und nicht mehr wie anfangs einige Warteminuten bietet.

Stiefel2000 schrieb:

Belli schrieb:

Stiefel2000 schrieb:

@ Belli: Das mit dem switch ist ganz gut - warum nimmst du anstatt der for-Schleife keine while-Schleife?

Ich dachte, wenn ich eine while - Schleife nehme, fragst Du mich, warum ich keine for-Schleife nehme.

:p
Ich habe nicht "while(1)", sondern die erste if-Abfrage des Anweisungsblocks als Abbruchbedingung genommen.

Das ist auch viel besser. Damit sparst Du das return in der Schleife. Ich wollte mit meinem Vorschlag so nah wie möglich bei Deinem Ansatz bleiben. Es gibt möglicherweise noch Wege, den switch einzusparen, wenn man Funktionszeiger einsetzt, aber das hängt auch ein bißchen von dem Rest ab.

Stiefel2000 schrieb:

Belli schrieb:

Nein, Du brauchst immer nur die bisher kürzeste gefundene. Also die zweite gefundene Lösung vergleichst Du auf Grund der Rekursionstiefe mit der ersten, und verwirfst die längere gleich.
Die nächste gefundene Lösung vergleichst Du mit der, die Du noch hast, und verwirfst wieder die längere, usw.

Ok, das hätte ich wahrscheinlich schnell gemerkt ;). Aber ich weiß eben noch nicht, wie ich das gut umsetze.

Wie gesagt, wenn Du einen Weg gefunden hast, mußt Du Dir den merken, bevor der Rückweg durch die Rekursion angetreten wird, denn dann sind die Ergebnisse ja weg. Und diesen gemerkten Weg ersetzt Du dann, wenn Du einen kürzeren findest. Am Ende, wenn alle Möglichkeiten durch sind, führst Du dann den gemerkten Weg aus.