Bactrack – gyakorlat
vázlat

 

Szlávi Péter

 

2003

 


Tartalom

A. Emlékeztető 3

A1. A megoldás madártávlatból 3

A2. Fogalmak …... 3

A3. A megoldás algoritmusa 4

A4. Kódolás …... 5

B. Labirintusos feladat 7

B1. A feladat 7

B2. Útban a megoldás felé – Problémák 7

B3. Algoritmus 8

B4. További problémák, kérdések 9

C. Dominós feladat 10

C1. A feladat 10

C2. Útban a megoldás felé – Problémák 10

C3. Algoritmus 10

D. Szakasz-lefedéses feladat 12

D1. A feladat 12

D2. Útban a megoldás felé – Problémák 12

D3. Algoritmus 12

Függelék 14

A. Emlékeztető

Az alábbiakban emlékeztetőként meggondoljuk a backtrack (-es keresés) algoritmusának lényegét, valamint értelmezzük a specifikáció néhány kellékét.§ Két konkrét feladaton ke­resztül vizsgálódunk: a jól ismert N-vezér és a munkavállalós problémán keresztül. (Az utóbbira kétféle megoldást is körvonalazunk.)

A1. A megoldás madártávlatból

… a szisztematikus előrehaladás és visszalépés bemutatása a két feladaton keresztül …

A2. Fogalmak…

Mindenek elé maga az absztrakt specifikáció.

Be:    NÎN , MÎN*                                             – N elemszámú méretsorozat,
         Yi
ÎHi* (iÎ[1..N])                                       mi elemszámú lehetőségsorozatok,
         fk:
N i®L                                           lehetőségek összeférése (indexeikkel megadva),
         ft:
N 2®L                                                   (az önmagában) kiválaszthatóság

Ki:     VanÎL , XÎN*                                                         az összeférő lehetőségek indexeinek sorozata

Ef:     N=Hossz(M)  Ù  N³2  Ù
         "iÎ[1..N]: ( Mj=Hossz(Yj)  Ù  HalmazFölsorolás(Yj) )  Ù
        
"jÎ[1..N], "iÎ[1..j]: fk(n1,…nj) Þ fk(n1,…ni)

Uf:    Van º $ZÎ[1..m1]´[1..m2]´...´[1..mN]: ( "iÎ[1..N]: ft(i,zi)  Ù  fk(Z) )  Ù
         Van
Þ ("iÎ[1..N]: xiÎ[1..mi]  Ù  ft(i,xi))  Ù  fk(x1,..xN)

Nézzük a fenti fogalmak miként testesülnek meg a konkrét feladatokban!

N-vezér probléma

N munka – N munkavállaló

Mi az eredmény?

N vezérhez tartozó

a.      sakktábla-mező koordináta (N2)
Þ (N2)N

b.      sakktábla oszlop vagy sor-index (N)
Þ (N)N

N munkavállalóhoz tartozó munka (Munka)
Þ MunkaN

Megjegyzés: a Munka halmaz egy absztrakt halmaz (elemei előre nem ismertek), de helyettesíthető N rész­halmazával, ui.: soroljuk föl elemeit egy tömbben, és egy elemre eztán indexével hivatkozhatunk.

Mi a bemenet?

N vezérhez tartozó

a.      összes sakktábla-mező koordináta (N2)
Þ (N2)N×N

b.      összes sakktábla oszlop (sor)-index (N)
Þ (N)N

Mindez persze csak „virtuálisan”, a tételhez való megfeleltetés kedvéért.

N munkavállalóhoz tartozó

a.      vállalható munkák felsorolása: Munka*
(persze a Db és a munkasorozat megadásával)
Þ (Munka*)N,

b.      összes (M) munka vállalhatósága: LM,
(ott igaz, amelyiket elvállalhatja)
Þ (LM)N = (L)N×M

Mi az fk függvény?

Általában (jelentése és tulajdonsága)
és konkrétan …

nincs ütésben = páronként nem ütik egymást

nincs kiadva még a munka = (páronként el­lenőrizve) még senkié sem a munka

Mi az ft függvény?

Általában (jelentése és tulajdonsága)
és konkrétan …

Æ

a.    Æ

b.    választható-e a munka az adott munka­vállalóhoz? Vállalhatja-e a munkavállaló sajátmaga miatt?

Mi az uf?

Van = …
Van Þ

Van = …
Van Þ

A3. A megoldás algoritmusa

A specifikáció értelmezése után térjünk át az algoritmus részleteire!

A legfelsőbb szint:

Típus
 
 TKeresett=Rekord(van:Logikai, melyik:Egész)

Változó
  i:Egész
  ker:TKeresett

i:=1; X(1..N):=0 [az i. kezdőszeletnél tartunk]
Ciklus amíg i
³1 és i£N
  ker:=JóElem(i)
  Ha ker.van akkor  X(i):=ker.melyik; i:+1
           különben X(i):=0; i:-1
Ciklus vége
Van:=i
³1
[
X-ben található a megoldás, ha létezik]

A JóElem függvény finomítása:

Függvény JóElem(i:Egész): TKeresett
  [
i.-ben választható-e jó komponens?
   M(1..N) tartalmazza az egyes bemeneti sorozatok elemszámát]
  Változó
    j:Egész

  j:=X(i)+1
  Ciklus amíg j
£M(i) és (nem ft(i,j) vagy nem Lehetséges(i,j))
    j:+1
  Ciklus vége
  JóElem.van:=j
£M(i)
  Ha JóElem.van akkor JóElem.melyik:=j
Függvény vége.

Függvény Lehetséges(Konstans i,j:Egész):Logikai
  [
az i. komponensként a j választása összefér-e az eddigiekkel?]
  Lehetséges:=fk(X(1),...,X(i-1),j)
Függvény vége.

Ez gyakorta (=páron­kénti ellenőrzés esete) egy eldöntés tételt jelent.

 

Végül az van csak hátra, hogy a konkrét feladatokhoz tartozó algoritmusokat elkészítsük.

Mi az algoritmus?

A4. Kódolás…

Az N-vezér probléma kódolásához egy keretprogramot biztosítunk, amit alább részletezünk. Letöltheti: VEZKERET.PAS, egy hozzá szükséges kellékkel együtt: VEZERAJZ.PAS, amivel a sakktábla rajta a vezérekkel „vizualizálható”. Az utóbbihoz tartozó használati tudnivalókat az eljárások fejsorai megadják:

Procedure Inicializalas(Var n: Index);

Procedure Varakozas(meddig: Integer);

Procedure MezoRajz(x,y: Integer; szin: Integer);

Procedure Letesz(i,j: Index);

Procedure Folvesz(i,j: Index);

Procedure TablaKi(n: Index);

A JóElem függvény összetett értéktípusa nem minden programozási nyelv számára kivitelez­hető, ezért másként paraméterezzük. E függvényből lett eljárásnak a neve legyen: VanJóEset! (Innentől kezdve igazodunk a mikrológiában szereplő jelölésekhez.) Az alábbiakban lásd a keret kódját, amelyben kékkel szedtük a megalkotandó részeket.

 


Program N_Vezer_Keret;
  Uses
     Newdelay, Crt;

  Const
     MaxN  = 10; VarakozasHossz = 500;

  Type
     Index = 0..MaxN+1;
     Hol   = Array [1..MaxN] of Index;

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

 

  {$i VEZERAJZ.PAS}

 

  Procedure VanMegoldas(n: Index);
    Var
      i,j: Index;
  Begin
    Window(1,1, 80,25); TextColor(White); TextBackGround(Black); ClrScr;

    Write('Az N-vezérproblémának N=',n,' esetre van megoldása, mégpedig
           az alábbi:');
    TablaKi(n);
    Varakozas(0);
  End;

 

  Procedure NincsMegoldas(n: Index);
  Begin
    Window(1,1, 80,25); TextColor(White); TextBackGround(Black); ClrScr;
    Write('Az N-vezérproblémának N=',n,' esetre nincs megoldása.');
    Varakozas(0);
  End;

 

  Function Uti(vx1,vy1, vx2,vy2: Index): Boolean;
  Begin
    {Uti:=Mikor üti?}
  End; {Uti}

 

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

  Begin
    {RosszEset:=Mikor rossz az eset?}
  End;

 

  Procedure VanJoEset(i: Index; Var talan: Boolean; Var ide: Index);
  Begin
    {ide:=Hova?;
     talan:=Van jó eset?}
  End;

 

Begin
  Inicializalas(N);
  {A backtrack lényegi algoritmusa.}
  If i>0 then VanMegoldas(N)
         else NincsMegoldas(N);
End.


A fenti megoldását a Függelék tartalmazza.

A további feladatokat e feladatsorból vettük: http:/people.inf.elte.hu/szlavi/PrM1felev/Backtrack/BacktrackFeladatok.pdf

B. Labirintusos feladat

B1. A feladat

Egy éhes egérnek egy labirintusban elhelyeznek egy darab sajtot. Írjunk programot, amely segít az egérnek megkeresni a sajthoz vezető utat!

B2. Útban a megoldás felé – Problémák

1.            Mi az eredmény?

Szövegdoboz: Ki ÛVálasz: egy „útvonal-megadás” (lépésirányok: Irány=(Bal,Fel,Jobb,Le)), ami egy előre nem látható hosszúságú (azaz az alap algoritmusbeli N nem fix) labirintusbeli  hely-, vagy iránysorozat: Hely(0..MaxHossz:Hol), vagy MerreTovább(0..Max­Hossz:Irány) tömb, ahol MaxHossz a labirintusbeli utak összhossza, a 0. elem a kezdő helyzet. (A Hol miben léte eddig még kérdéses, bár világos.) Döntsünk az Irány-ra alapozott mellett!

2.            Mik a bemeneti sorozatok?

Szövegdoboz: Be ÛVálasz: a négy irány halmazából éppen annyi, amennyi lépés kell a megoldáshoz. De természetesen ez nem valódi programbemenet, csak a tétel egyik bemeneti kellékének konkretizációja.

3.            Szövegdoboz: Általában, a feladat be-menete (nem függ össze a backtrack algoritmussal)Hogyan ábrázolandó a labirintus?

Pl. egy „térképpel” (Labirintus(Hol:Elem) tömbbel[1]), amelyben háromféle érték for­dulhat elő: fal, út és sajt (Elem). A Hol „logikusan” lehet síkbeli pontok koor­dinátapárja: (1..N,1..M). Így tehát: Labirintus(1..N,1..M: Elem) –most már tud­juk, hogy– mátrix. Ekkor viszont az Irány-beli értékek elmozdulás-megfelelői már adódnak: Bal®(1,0), Fel®(0,1), Jobb®(-1,0), Le®(0,-1).

4.            Ebben az esetben mi az fk (kielégíthetőségi) és az ft függvény?

Válasz: fk legyen olyan, hogy ha Helyi az útvonal i. lépése utáni hely; és az i. lépés után meglépendő ir irány esetén teljesüljön: fk(Hely0,...,Helyi-1,ir)=Igaz akkor, ha a Helyi-1+ir= HelyiÏ{Hely0,...Helyi-1}, azaz itt még nem járt az egér; az ft: Labirintus(Helyi-1+ir)¹fal, azaz az úton marad. (A + művelet a vektor-összeadás.)

5.            Meddig tart a keresés?

Válasz: N-re nem építhetünk (ez most a labirintus egyik mérete, s nem az eredmény sorozat hossza, azaz a szükséges lépések száma), így merészen és logikusan így döntünk: addig tart a keresés, amíg a sajtra nem találtunk, vagy a RajtHely-től indulva már minden lehetséges irányt kipróbáltunk, és nem tudtunk a sajtig jutni. Ekkor a szegény egér éhes marad.

B3. Algoritmus

A megvalósítás során tárolnunk célszerű (miért is?) az utat (Hely tömb), a(z ál)bemeneti sorozatokból (Irány sorozatokból) választott indexeket (LépésIrányIndex tömb). A konstans Irány tömb indexkonvenciója: 1 a Balhoz, azaz az (1,0)-hoz, a 2 a Felhez, azaz a (0,1)-hez éít., a 0 –szokás szerint– a még „ki nem választottat” jelenti. (Vagyis: Irány: Tömb(0..4:Hol).) A megoldás tehát: a LépésIrányIndex tömb és a tényleges hossza (az utóbbit a LépésSzám tartalmazza), és persze a megoldhatóságot kifejező VanÚt logikai vál­tozó.

A program valódi paraméterei: Labirintus, RajtHely. (A továbbiakban nem foglalkozunk a deklarációkkal.)

Program SajtKeresés:

Szövegdoboz: X
i³N
  
   Hely(0):=RajtHely [ahonnan indul az egér, pl. (1,1)]
   i:=1; LépésIrányIndex(1..MaxHossz):=0

   Ciklus amíg i≥1 és Labirintus(Hely(i-1))¹Sajt
      VanJóEset(i, van, j)
      Ha van akkor
    
   LépésIrányIndex(i):=j
        Hely(i):=Hely(i-1)+Irány(j) [+: vektorösszeadás]
        i:+1
      különben
        LépésIrányIndex(i):=0
        i:-1
      Elágazás vége
   Ciklus vége
   VanÚt:=i≥1
   Ha VanÚt akkor LépésSzám:=i-1
Eljárás vége.

 

Eljárás VanJóEset(Konstans i:Egész, Változó van:Logikai, j:Egész):

   j:=LépésIrányIndex(i)+1

   Ciklus amíg j£4 és (RosszEset(i,j) vagy
         Labirintus(Hely(i-1)+Irány(j))=Fal
         [a Labirintusmátrix Hely(i-1)+Irány(j)
          koordinátájú pontja Fal értékű-e]

      j:+1

   Ciklus vége

   van:=j£4

Eljárás vége.

 

Függvény RosszEset(Konstans i,j:Egész): Logikai
   k:=0
   Ciklus amíg k<i és Hely(k)
¹Hely(i-1)+Irány(j)
      k:+1
   Ciklus vége
   RosszEset:=k<i
Függvény vége.

B4. További problémák, kérdések

6.            Ha a Labirintus-beli értékként megengedünk egy „JártÚt” értéket, annak jelölésére, hogy arra már járt az egér, akkor lényegesen egyszerűsíthető az algoritmus. Hogyan? (A RosszEset-ben nincs szükség az eldöntés tétel alkalmazására.)

7.            Milyen tulajdonsággal rendelkezik az egér útja, ha csak 1-szélességű folyosók vannak? (Nem biztos, hogy a legrövidebb, de fölösleges „hurkokat” nem tartalmaz.)

8.            ... és ha lehetnek 2-, vagy több szélességű folyosók? Mi lehet a szerepe a „szűk” folyosóknak? (Tartalmazhat az egér útja olyan szakaszokat, amelyeken oda is és vissza is megy a fal mellett, s nem veszi észre, hogy járt már e folyosón. Az 1-szélességűnél képes levágni e hurkokat.)

9.            Mit lehetne tenni az előző pontban említett probléma intelligens megoldására? (A folyo­só teljes szélességében figyelni, hogy volt-e már ott; s ha igen, akkor levágni a hurkot; és természetesen ugyanígy figyeli a sajtot is.)

C. Dominós feladat

C1. A feladat

Tegyük le az összes dominót úgy, hogy csak az egyik irányba tehetünk, és a dominókon az összes lehetséges párosítás ((0:0),(0:1),...,(0:9),(1:1),...,(9:9)) előfordul!

C2. Útban a megoldás felé – Problémák

1.                  Eredmény...: dominósorozat (a fordított dominót nem tároljuk ? darabszám=10+9+... +1=55).

2.                  Bemeneti sorozatok: dominók „halmaza”.

3.                  Ábrázolás...: a dominók = Dominó(1..55[melyik],1..2 [oldal]:0..9 [hány pötty]). (Persze az egyes dominók „olcsóbban” is kódolhatók: egy-egy kétjegyű, decimális számmal.)

4.                  fk,ft...: eddig még nem tettük le; s az (eddigi) utolsóhoz  illeszthető-e. (Szorosan véve az ft értelmezését –„csak önmagában, saját maga miatt, az eddigi választásainktól függetlenül megfelelő”– „gyenge” kapcsolatot vehetünk észre az utolsóként válasz­tottal!)

5.                  Meddig...: amíg az összest le nem tettük.

C3. Algoritmus

Szövegdoboz: XProgram Dominó:
   … [most N=55]
   i:=1; DominóSor(1..N):=0
   Ciklus amíg i
³1 és i£N
      VanJóEset(i, van, j)
      Ha van akkor  DominóSor(i):=j; i:+1
           különben DominóSor(i):=0; i:-1
   Ciklus vége
   Letehető:=i>N
   Ha Letehető akkor … DominóSor(1..N) a letevés …
  
Program vége.

 

Szövegdoboz: ØftEljárás VanJóEset(Konstans i:Egész, Változó van:Logikai, j:Egész):
   j:=DominóSor(i)+1
   Ciklus amíg j
£N és ( RosszEset(i,j) vagy
               nem UtolsóhozIllik(i,j) )
      j:+1
   Ciklus vége
   van:=j
£N
   Ha van és Dominó(DominóSor(i-1),2)
¹Dominó(j,1)
         akkor Csere(Dominó(j,2),Dominó(j,1))
Eljárás vége.

 

Függvény RosszEset(Konstans i,j:Egész): Logikai
   k:=1
   Ciklus amíg k<i és DominóSor(k)
¹j
      k:+1
   Ciklus vége
   RosszEset:=k<i
Függvény vége.

 

Függvény UtolsóhozIllik(Konstans i,j:Egész): Logikai
  UtolsóhozIllik:=i=1 vagy
                  Dominó(DominóSor(i-1),2)=Dominó(j,1) vagy
                  Dominó(DominóSor(i-1),2)=Dominó(j,2)
Függvény vége.

 

D. Szakasz-lefedéses feladat

D1. A feladat

Lefedhető-e egy adott hosszúságú szakasz egyszeresen a H1,...,HN hosszúságú kisebb szaka­szokkal?

D2. Útban a megoldás felé – Problémák

1.                  Eredmény…: szakasz-sorozat (legfeljebb N darab), pontosabban szakaszindex (SzI(1..???)).

2.                  Bemeneti sorozatok: a szakaszok „halmaza”.

3.                  Ábrázolás…: szakaszok hossza (H(1..N)).

4.                  fk,ft…: az eddig még nem kiválasztott szakasz; az eddig lefedett szakasz összhossza  (=pillanatnyi hossz) lefedendő szakasz hossza (=szakaszHossz); itt is „implicit” kapcsolat van a korábbiakkal.

5.                  Meddig…: a lefedett összhossz (=pillanatnyi hossz) ¹ lefedendő szakasz hossza (szakaszHossz); és persze még nem használtuk föl az összes szakaszt.

Utóbbi csak akkor következhet be, ha a szakaszok összhossza kisebb, mint a lefedendő szakaszé. Ez könnyen ellenőrizhető, így elkerülhető a backtrack-es algoritmus effajta „elvi” kudarca.

D3. Algoritmus

Tegyük föl, hogy elvileg akár létezhet megoldás, azaz Hi³H.

Érdemes észre venni, hogy amikor majd az fk kiszámolást végző VanJóEset eljárást írjuk minduntalan ki kell számolnunk az eddig letett szakaszok összhosszát, amit könnyen elkerülhetnénk úgy, hogy „göngyölítjük” azt egy segédváltozóban. Ez legyen a pillHossz.

Ha így teszünk, akkor ennek módosulását nyomon kell követni a legfelsőbb szinten: ha „VanJóEset”, akkor pillHossz-növelés, ha „NincsJóEset”, akkor levonni a pillHossz-ból az utolsó, elfogadott választást. Ez egy problémás helyzet, hiszen ha egyáltalán nincs megol­dás, visszalépünk –mint jól ismert– a „nem létező” 0. választáshoz, ami azt jelenti, hogy a hozzátartozó „hosszt” akarjuk a pillHossz-ból levonni. ... „Legkönnyedebb” megoldás: H(0..N:Valós) és SzI(0..N:Egész).

Szövegdoboz: X

i³N
Program Lefedés:
   pillHossz:=0; H(0):=0; SzI(0):=0
   i:=1; SzI(1..N):=0
   Ciklus amíg i
³1 és pillHossz¹szakaszHossz
      VanJóEset(i, van, j)
      Ha van akkor  SzI(i):=j; pillHossz:+H(j);        i:+1
           különben SzI(i):=0; pillHossz:-H(SzI(i-1)); i:-1
   Ciklus vége
   Lefedhető:=pillHossz=szakaszHossz
Program vége.

 

Szövegdoboz: ØftEljárás VanJóEset(Konstans i:Egész, Változó van:Logikai, j:Egész):
   j:=
SzI(i)+1
   Ciklus amíg j
£N és (RosszEset(i,j) vagy
                       pillHossz+H(j)>szakaszHossz)
      j:+1
   Ciklus vége
   van:=j
£N
Eljárás vége.

 

Függvény RosszEset(Konstans i,j:Egész): Logikai
   k:=1
   Ciklus amíg k<i és
SzI(k)¹j
      k:+1
   Ciklus vége
   RosszEset:=k<i
Függvény vége.

 

 

Függelék

Az N-vezéres feladat végeleges megoldása, amiben a pirossal szedett újdonságra koncentrál­tunk csak:

Program N_Vezer;

 

  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;

 

Begin
  Inicializalas(N);
  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
      Letesz(i,hova);
      Inc(i); Vezer[i]:=hova;
    End
      else
    Begin
      If i>1 then Folvesz(i-1,Vezer[i-1]);
      Vezer[i]:=0; Dec(i);
    End;
    Varakozas(50);
  End;

  If i>0 then VanMegoldas(N)
         else NincsMegoldas(N);
End.

 



§ Erősen építünk az előadás jelöléseire, koncepciójára.
(Lásd pl.: http://people.inf.elte.hu/szlavi/PrM1felev/Pdf/PrMea6.pdf).

[1] Ne akadjunk fel azon, ha egyik-másik programozási nyelv ilyen típust indexként nem fogad el, hanem értsük: mit akar kifejezni!