Backtracking und Rekursion

[Vani_x]

Guten Abend,

ich hatte mir selber eine Aufgabe gestellt. Und zwar wollte ich eine Zahl N nehmen. Also beispielsweise N = 3, dann wird ein Array der Größe 2*N kreiert. Und in diesem Feld wird per Rekursion und Backtracking eine Lösung gesucht.

Also, wenn N = 3 ist, dann werden die Zahlen 1, 2 und 3 in das Feld so reingelegt, sodass der Abstand immer um die Zahl selber ist. Also z.B. wenn im ersten Feld eine 3 ist, dann muss nach drei Feldern wieder eine 3 stehen. Die Zahlen 1,2,3 müssen doppelt vorkommen, sonst macht das garkeinen Sinn.

Eine Lösung für N=3 wäre:






Ich weiß ungefähr, wie ich das realisieren möchte, aber es zu codieren, ist für mich fast unmöglich.

Bin für jeden Tipp sehr dankbar.

 

[Oneixee5]

Was finden nur immer alle an der Rekursion? Rekursion hat gewichtige Nachteile. Ich gehe sogar soweit und behaupte: Rekursion ist kein guter Stil - Rekursive Programme haben in der Regel keine gute Performance. Durch die wiederholten Funktionsaufrufe (Inkarnationen) wird immer wieder derselbe Methodeneintrittscode bearbeitet und bei jeder Inkarnation der Kontext gesichert, was zu zusätzlichem Programmcode und höherem Arbeitsspeicherverbrauch führt. Alle rekursiven Algorithmen lassen sich jedoch auch durch iterative Programmierung implementieren und umgekehrt.

 

[Vani_x]

Ich will jetzt nicht unhöflich klingen, aber wäre eher lieber über ein Tipp erfreulich, der mir dabei hilft, das Problem zu lösen. Trotzdem danke ich dir für die Antwort.

Ich bin auch kein Fan von Rekursion, aber muss das üben für den Kurs, den ich besuche.

 

[httpdigest]

Zuersteinmal brauchst du eine Strategie, was denn genau ein rekursiver Aufruf repräsentiert. Ich würde vorschlagen, dass ein rekursiver Aufruf das zweimalige Setzen, Prüfen bzw. Weitermachen und wieder "Entfernen" einer der drei Zahlen (in deinem Beispiel mit N=3) in dem Array repräsentiert.
Ich würde also eine Methode schreiben, die per Schleife über alle sinnvollen im Array verfügbaren Stellen geht, und versucht, an den aktuell zwei möglichen Stellen (also i und i+k+1) die aktuelle Zahl `k` zu setzen und dann mit der nächsten Zahl `k+1` weitermacht. Wenn `k == N+1` ist, dann wird das aktuelle Ergebnis bzw. der aktuelle Zustand ausgegeben.

Dass Rekursion (in Java) zu meist im Vergleich zu iterativen Lösungen ineffizienteren Lösungen führt, ist nur dem relativ dummen JIT Compiler geschuldet und der Tatsache, dass die JVM keine effiziente tail-recursion unterstützt. In rekursiven Algorithmen denken zu können, ist eine unbedingt zu erlernende Grundfertigkeit, die einem auch in anderen eher puren funktionalen Programmiersprachen (ohne Schleifen) zugutekommt und generell das abstrakte Denken fördert.

 

[LimDul]

Idee:

- Array anlegen
- Hilfs-Methode schreiben, die überprüfen kann ob eine Array-Belegung (die auch noch nicht vollständig sein muss) bisher gültig ist.
- Dann deine rekursive Methode. Als erstes wird an Stelle 1 eine 1 gesetzt
- Hilfsmethode aufrufen. Wenn ja, ruft die Methode sich selber auf und macht an Stelle 2 weiter
- Wenn nein, die 1 durch die 2 austauschen und wie oben
usw.

 

[httpdigest]

@LimDul Eine explizite Gültigkeitsprüfung brauchst du nicht, da man von vornherein gleich nur gültige Belegungen generieren kann (so es denn der Schleifenindex zulässt).

 

[Vani_x]

Bin jetzt soweit gekommen, aber kriege das irgendwie nicht ganz hin. Wo ist mein Denkfehler?

[CODE lang="java" title="Aufgabe1"]public class Aufgabe1 {

static int[] funktion;
static int zaehler = 0;

public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
funktion = new int[2 * N];
solve(N);
}

public static void solve(int N) {

if (N <= 0)
return;

for (int i = 0; i < funktion.length; i++) {
if (i < funktion.length - 1) {
if (funktion == 0) {
funktion = N;
if (funktion[i + N + 1] != N + 1 && funktion[i + N + 1] == 0) {
funktion[i + N + 1 ] = N;
} else {
funktion = 0;
funktion[i + 1] = N;
funktion[i + N + 2 ] = N;
}
solve(N - 1);
}
} else {
solve(N + 1);
}
}
}
}

[/CODE]

 

[httpdigest]

funktion[i + N + 1] ist falsch. Die zwei Zahlen sind ja nicht immer im Abstand von N voneinander entfernt. Der Abstand hängt von der Zahl selber ab.
Bzw. du solltest klären, was N bei dir eigentlich ist.
Ich würde generell vorschlagen, dass du erstmal versuchst, ohne globalen Zustand (static Variablen) auszukommen. Versuche mal, den Algorithmus rein funktional zu formulieren. Hierzu brauchst du natürlich eine Hilfsmethode, die entsprechend mehr als nur einen Parameter bekommt.

 

[Vani_x]

Naja, hatte es versucht zu machen, dass N immer die Zahl ist, die gerade eingesetzt wird, wenn die Funktion solve aufgerufen wird. Bei solve(3) wäre in dem Fall mein N = 3.

 

[httpdigest]

Ja, aber du brauchst dann ja auch noch eine Zahl (ich nannte sie `k`), die repräsentiert, welche Zahl denn nun gerade dran ist (von 1 angefangen).

 

[Vani_x]

Das ist glaube ich alles zu hoch für mich. 🙁

Wie genau soll ich mir das überlegen? Ich muss ja alle Möglichkeiten durchgehen, aber das ist so kompliziert und kompakt.

 

[httpdigest]

Du hast dir aber auch nun wirklich nicht die einfachste Rekursionsübung herausgesucht. 🙂
Immer weiter probieren, nachdenken und weiterprobieren.

Bedenke: Die Aufgabe eines Rekursionsaufrufes sollte es sein (meiner Meinung nach), die zwei Stellen im Array mit der aktuellen Zahl `k` zu belegen, rekursiv abzusteigen, und dann die Zahlen wieder zu löschen (das Löschen, damit mit den nächsten Stellen im Array weiterprobiert werden kann).

 

[Vani_x]

Hmm, danke dir! Ich versuchs einfach solange, bis ich am Stuhl einschlafe und morgen sage ich bescheid, ob ich es geschafft habe.

 

[httpdigest]

Okay, und denke nicht zu kompliziert. Sobald deine rekursive Methode zuuu kompliziert aussieht, ist sie vermutlich falsch. 🙂
Die rekursive Methode kann man zumindest innerhalb von 9 Zeilen schreiben (also: jeweils gefundene Lösungen ausgeben und neue Lösungen generieren).

 

[Vani_x]

Ich habs leider nicht geschafft. Hast du noch paar Tipps für mich?

 

[httpdigest]

Was ein Rekursionsaufruf machen (sollte):
1. Prüfen, ob wir schon fertig sind, also eine Lösung gefunden haben (`k == N-1`) und diese dann ausgeben
2. Sonst: Für alle möglichen Arraystellen prüfen, ob die für `k` zu setzenden zwei Stellen im Array noch frei sind, falls eine (neue) Stelle gefunden, dann:
2.1: Stellen mit `k` belegen
2.2: rekursiv absteigen mit k+1
2.3: Stellen im Array wieder löschen (auf 0 setzen)