Rekursive Funktion abbrechen

früchtemüsli

Hallo alle miteinander, ich probier grade an einem Problem rum, das ich irgendwie nicht lösen kann.
Das hier war meine ursprüngliche Aufruffunktion:

for (i = 0; i < control.iSize; i++)
     {
      control.iBoard[0] = i;
      calc(&control,1);
     }

und die ruft diese Funktion hier auf, um etwas zu berechnen:

int calc(struct queen *control,int iRow)
{
int i;

  if (iRow == control->iSize)
  {
   control->iSolutions++;
   return;
  }

  for (i = 0; i < control->iSize; i++)
  {
   control->iBoard[iRow] = i;
     if (isbeating(control,iRow) == 0)
     {
      calc(control,iRow+1);
     }
  }
}

So, das das ja eine rekursive Funktion ist, läuft die hier bis ganz ans Ende und zählt die Lösungen, die gefunden wurden. Z.B bei control->iSize = 8 sind es 92 Lösungen.
Nun wollte ich die Funktion abbrechen lassen, sobald die erste Lösung gefunden wurde und bei erneutem Aufruf wieder bis zur nächsten Lösung tuckern lassen.

Habs erstmal so probiert, hat aber nichts gebracht!
Der Aufruf:

do
     {
      control.iBoard[0] = i;
      calc(&control,1);
     }while(calc(&control,1) == 1);

Und die Funktion:

int calc(struct queen *control,int iRow)
{
int i;

  if (iRow == control->iSize)
  {
   [b]if(control->eMode==man)
   {
    control->iSolutions++;
    return 1;
   }
   else
   {[/b]
    control->iSolutions++;
    return 0;
  [b]}[/b]
  }

  for (i = 0; i < control->iSize; i++)
  {
   control->iBoard[iRow] = i;
     if (isbeating(control,iRow) == 0)
     {
      calc(control,iRow+1);
     }
  }
}

Aber leider will das nicht so rech gehen. Warum?

Danke für die Mühe

hi !
du müsstest die eins, die du retörnst, in der for-schleife abfragen und dann aus dieser raushüpfen

CStoll

Zum Abbrechen müsstest du auf jeder Aufrufebene den Rückgabewert der rekursiven Aufrufe abfragen und entsprechend selber weitergeben ("if(calc(...) return 1;").

Ein Wiedereinstieg an der selben Stelle ist leider nicht trivial, weil beim Beenden der rekursiven Funktion auch alle Hilfsdaten (hier v.a. die Zählerstände von i) wieder vom Stack geworfen werden und du beim nächsten Durchgang wieder von vorne anfangen mußt mit der Zählung. (eine Lösung wäre es, die Zählerstände nicht in der Funktion zu speichern, sondern im Hauptprogramm)

früchtemüsli

@bonus abfrage:
Also aus FOR Schleifen rauszuhüpfen ist leider bei uns strengstens verboten, hatte auch schon an so was gedacht!

@CStolle:
Ich hatte auch schonmal iRow in der Struct, in der auch iBoard usw. ist. Nur leider hatte das das Programm seltsamerweise nicht mehr funktioniert. Hatte an globale Variable gedacht, darf ich leider aber auch nicht verwenden!
Vielleicht hatte ich ja nur was total dummes vergessen, als ich's im Struct hatte

CStoll

früchtemüsli schrieb:

@bonus abfrage:
Also aus FOR Schleifen rauszuhüpfen ist leider bei uns strengstens verboten, hatte auch schon an so was gedacht!

Dann mußt du die Schleife halt auf klassische Weise verlassen

int ret = 0;
...
for(i=0;ret==0 && i<control->iSize;++i)
{
  ...
  if(calc(control,iRow+1)==1)
  {
    ret = 1;
  }
}
return ret;

@CStolle:
Ich hatte auch schonmal iRow in der Struct, in der auch iBoard usw. ist. Nur leider hatte das das Programm seltsamerweise nicht mehr funktioniert. Hatte an globale Variable gedacht, darf ich leider aber auch nicht verwenden!
Vielleicht hatte ich ja nur was total dummes vergessen, als ich's im Struct hatte

Ja, wenn du die Daten in den struct auslagerst, müsstest du selber dafür sorgen, daß die Zähler an der richtigen Stelle zurückgesetzt werden.

Ein alternativer Ansatz wäre es, die Rekursion nicht abzubrechen, sondern im Inneren der Funktion die nötigen Hilfsarbeiten zu erledigen (entweder direkt oder auch über eine Callback-Funktion).

mcr

Du kannst ja auch mal in die folgende Richtung überlegen:
- Das Problem iterativ und nicht rekursiv zu lösen.

Dann ist es um einiges einfacher, an einer bestimmten Stelle
zu unterbrechen und dort auch wieder einzusetzen.

Ein Tip vielleicht:
- Totalle Enumeration mit gut gewählten Abbruch-kriterien
(Branch and Cut)

Vielleicht hilft dir das ja.

Gruß mcr

früchtemüsli

Ahhh, iterativ hieße also, dass ich calc(..) nicht in calc(..) aufrufe, oder? Nur hab ich leider absolut keine Ahnung, wie ich das abändern müsste, um das hinzubekommen!

CStoll

Was genau willst du denn erreichen? (der Code erinnert etwas an das n-Damen-Problem)

Wenn meine Vermutung stimmt: Du könntest ausgehen von einem Array, das mit 1..n gefüllt wird und daraus per next_permutation() alle möglichen Lösungen des "n-Türme-Problems" bestimmen lassen - und dann jeweils kontrollieren, ob die Lösung auch für Damen tauglich ist (Vergleich der Diagonalen).

früchtemüsli

Ja, in der Tat, das ist für das N-Damen Problem. Ich muss halt einmal einstellen können, ob ich nur die Anzahl der Lösungen (bei 8x8 Feld sind das 92 Lösungen) oder im Einzelschrittmodus bin, d.h. einmal eine Taste drücken liefert das erste Ergebnis, das er gefunden hat, erneutes drücken liefert das zweite Ergebnis usw.

mcr

Das kannst du dann ja sogar rekursiv machen:

du brauchst dafür doch lediglich an der Stelle, wo du den Zähler
für den ersten Fall hochzählst, das Ergebnis ausgeben und auf die
Eingabe einer Taste warten, ohne aus der Rekursion heraus zu springen.

EDIT:

...
   if (valid) {
       switch (modus) {
       case 0: num++; break;
       case 1: print(); pause; break;
       default: error;
       }
   }
   ...

So ähnlich sollte das dann aussehen (hier Pseudocode).

Gruß mcr

CStoll

Ja, alte Ideen aufzuwärmen macht sich immer gut, um sie wieder in Erinnerung zu rufen

CStoll schrieb:

Ein alternativer Ansatz wäre es, die Rekursion nicht abzubrechen, sondern im Inneren der Funktion die nötigen Hilfsarbeiten zu erledigen (entweder direkt oder auch über eine Callback-Funktion).

mcr

CStoll schrieb:

Ja, alte Ideen aufzuwärmen macht sich immer gut, um sie wieder in Erinnerung zu rufen

CStoll schrieb:

Ein alternativer Ansatz wäre es, die Rekursion nicht abzubrechen, sondern im Inneren der Funktion die nötigen Hilfsarbeiten zu erledigen (entweder direkt oder auch über eine Callback-Funktion).

Stimmt, hätte mir auffallen können. Aber leider hat früchtemüsli deinen
Wink nicht verstanden, so dass dies vielleicht ein wenig deutlicher ist.