4. 2 Rekursionen und eine Frage

2 Rekursionen und eine Frage

  • A

    Hallo alle zusammen!

    Ich werkel seit einiger Zeit an den Aufgaben von "Project Euler" herum. Das Problem 15 kann zB. durch eine Rekursion gelöst werden.

    Mein Backtracking-Algo benötigte ca 5 min:

    unsigned long long backtrack(unsigned i, unsigned j){

	if (i==0||j==0)
		return 1;	
	else
		return backtrack(i-1,j)+backtrack(i,j-1);
}

    So ähnlich hatte es jemand in Ruby gemacht:

    unsigned long long routes=0;
unsigned long long backtrack(unsigned i, unsigned j){

	if (j>0)
		return routes+=backtrack(i,j-1);
	if (i>0)
		return routes+=backtrack(i-1,j);
	if (i==0 && j==0)
		return routes+=1;
}

    Wieso ist zweiterer unter eine Sekunde fertig? Meine Gedanken gehen gerade in Richtung Rekursionsverschachtelung... Also woran liegt es genau?

    Vielen dank! 🙂

    0
  • N

    Dein Algorithmus berechnet viel doppelt.
    Rekursionsbaum für deinen Algorithmus:

    Backtrack(n, n)->Backtrack(n, n-1)->Backtrack(n, n-2)
                                  ->Backtrack(n-1, n-1)
               ->Backtrack(n-1, n)->Backtrack(n-1, n-1)
                                  ->Backtrack(n-2, n)

    Wie du siehst berechnet er Backtrack(n-1, n-1) doppelt. Er berechnet Backtrack(n-x, n-x) 2^x mal, und 2^20 sind schon 1048576, einmal hätte genügt.
    (von den noch viel häufigeren doppelten Backtrack(n-x, n-y); x!=y mal abgesehen)

    0
  • A

    Hm sollte das denn nicht so sein?

    Also das Problem ist ja die Summe aller Möglichkeiten um in einem Grid von der linken oberen Ecke in die untere Rechte zu kommen.
    Im Grunde alle möglichen Kombinationen aus 20xRechts und 20xUnten. (40 über 20)

    Wenn ich doch einmal Rechts->Unten ausführe und dann Unten->Rechts sind es doch zwei verschiedene Wege deswegen muss doch Backtrack(n-1,n-1) auch doppelt gezählt werden!

    Das habe ich übrigens noch vergessen: Ich habe die Funktionen jeweils mit den Parametern (20,20) aufgerufen.

    Danke für deinen Beitrag!

    0
  • S

    du kannst den Algorithmus behalten aber du könntest dir eine Art Cache (z.b. mit Hashes) bauen, bei dem du abguckst, ob die backtrack(x,y) bereits ausgeführt hast (sprich, du speicherst du x, y und backtrack(x,y)).

    0
  • A

    Ich versteh garnicht was ihr mir sagen wollt.

    Angenommen ich nehme die doppelten raus, dann würde die erste Rekursion doch eine kleinere Zahl ausgeben. Die Ausgabe des Algo ist aber korrekt und beide Algos haben übrigens die gleiche Ausgabe.

    Wenn ich jetzt alles doppelt zähle, dann tut der zweite Algorithmus es doch ebenso.

    0
  • G

    Es geht aber darum dass du alles doppelt berechnest.
    Wenn du z.B. Backtrack(2, 3) schonmal berechnet hast, berechnest dus nochmal.
    Nehmen wir an, Backtrack(2, 3) = 12. Dann könntest du dir einen Cache baun, in dem du z.B. das so speicherst: cache[2][3] = 12. Der cache muss vorinitialisiert sein mit ungültigen Werten, z.B. -1. Dann kannst du, wenn dein Algorithmus irgendwann nochmal das Ergebnis von Backtrack(2, 3) braucht, nachschaun ob du es schon in der Tabelle hast, und das Ergebnis dann direkt verwenden ohne es rekursiv neu berechnen zu müssen.

    Es geht also nicht um das doppelte Zählen, sondern um das doppelte Berechnen, was du vermeiden solltest.

    0
  • A

    Achsooooo!

    Na klar, ich berechne immer da wo sich mehrere Wege kreuzen bestimmte Punkte immer wieder neu.

    Cache macht sinn 💡

    Besser ist es anscheinend, sich bei der Rekursion geschickter anzustellen. In diesem Fall hätte ich wohl aufpassen müssen, nicht zwei Rekursionen zu addieren die die gleichen Kombinationen in bestimmten Fällen ausgeben können.

    Danke, jetzt habe ich was neues gelernt 🙂

    0
Anmelden zum Antworten