Backtrack

Feladat: A ‘Backtrack’ rekurzív átiratának elkészítése.

Alábbiakban a backtrack iskolapéldáját demonstráló program egy jellemző részletét adjuk meg iteratívan. Mielőtt elemezné, lássa működés közben: VEZERDEMO.EXE.

Program N_Vezer{Iteratív backtrack};

  Const MaxN  = 10;

  Type  MIndex= -1..MaxN+1;

        Hol   = Array [1..MaxN] of Index;

  Var   Vezer:Hol;     i:MIndex;     N,j,hova:Index;     lehet:Boolean;

  {$I Vezer.inc}

  Function Uti(vx1,vy1, vx2,vy2: Index): Boolean;

  Begin

    Uti:=(vy1=vy2) or (Abs(vy1-vy2)=vx1-vx2)

  End; {Uti}

  Function RosszEset(x,y: Index): Boolean;

    Var  j: Index;

  Begin

    j:=1;

    While (j<=x-1) and not uti(x,y, j,Vezer[j]) do Inc(j);

    RosszEset:=j<=x-1

  End;

  Procedure VanJoEset(i: Index;  Var talan: Boolean; Var ide: Index);

  Begin

    ide:=Vezer[i]+1;

    While (ide<=N) and RosszEset(i,ide) do Inc(ide);

    talan:=ide<=N;

  End;

  Procedure BackTrack;

  Begin

    i:=1;

    For j:=1 to N do Vezer[j]:=0;

    While i in [1..N] do

    Begin

      VanJoEset(i,lehet,hova);

      If lehet then

      Begin

        Vezer[i]:=hova; Inc(i);
      End

        else

      Begin

        Vezer[i]:=0; Dec(i);

      End;

    End;

    If i>0 then VanMegoldas(N)

           else NincsMegoldas(N);

  End;

Begin

  Inicializalas(N);

  BackTrack;

End.

 

 

Az unos-untig használt sablon a következő (’Keresés’) tétel átalakítása alapján könnyen megért­hető:

Iteratív

Rekurzív

Eljárás Keres(Konstans x:TSorozat;
      Változó Van:Logikai,melyik:Egész):
  Változó i:Egész

  i:=1
  Ciklus amíg i£N és nem T(x,i)
    i:+1
  Ciklus vége
  Van:=i£N
  Ha Van akkor melyik:=i
Eljárás vége.

A ciklust jobbrekurzióvá alakíthatjuk, miután kü­lönválasztottuk (egy önálló eljárásba) az „előké­től” és az „utókától”. Az eredeti eljárás paramé­terei közül elegendő azokat „átvinni” a rekurzív eljárás paraméterei közé, amelyektől a ciklus valójában függ. Gondoskodni kell arról, hogy az utóka is a megfelelő információt megkapja. Erre sok mód lehet. Most a legkézenfekvőbbet választ­juk: legyen a rekurzív tevékenység egy index ér­tékű függvény.

Eljárás Keres(Konstans x:TSorozat;
     Változó Van:Logikai,melyik:Egész):
  Változó i:Egész

  i:=1
  i:=KeresR(i,x)
  Van:=i£N
  Ha Van akkor melyik:=i[1]
Eljárás vége.

A ciklus jobbrekurzívvá alakítása:

Függvény KeresR(Konstans i:Egész,
                    x:TSorozat):Egész
  Elágazás
    i>N  esetén
           KeresR:=i
    nem T(x,i) esetén
           KeresR:=KeresR(i+1,x)
    egyéb  esetben
           KeresR:=i
  Elágazás vége
Függvény vége.

 


[1] Mindez sokkal egyszerűbben is írható:  melyik:=KeresR(1,x); Van:=melyik£N