V. A visszalépéses keresés (Backtrack)

Hagyomány, hogy a visszalépéses keresés algoritmusát a nyolc királynõ feladványon keresztül mutatják be. Én is ezt teszem, majd általánosítom a problémát. Helyezzünk el 8 királynõt a sakktáblán úgy, hogy ne üssék egymást (8-nál többet nyilván nem lehet). Keressünk megfelelõ adatszerkezetet a feladathoz: mivel a királynõk biztosan különbözõ oszlopokban lesznek, elég megadni, hogy az egyes oszlopokban hányadik sorban van a bábu. Erre szolgál a T[1..8] tömb, ahol T[i] az i. oszlopban lévõ királynõ sora (1 és 8 közötti egész szám).

Ha nyers erõvel fogunk a feladat megoldásához, oszloponként 8 lehetõség, T tömb állapotára pedig 88 lehetõség adódik. Mindegyik lehetõséget meg kell vizsgálni abból a szempontból, hogy ütik-e egymást a bábuk. Az i. és j. oszlopban lévõ királynõk akkor ütik egymást, ha azonos sorban vannak, vagy azonos átlóban (vagyis egy négyzet átellenes sarkaiban, sorszámuk és oszlopszámuk különbsége megegyezik).

Function Uti(i,j:integer):boolean;
 Begin
  Uti:=(T[i]=T[j]) or (abs(i-j)=abs(T[i]-T[j]));
 End;

Elõ kell tehát állítani az összes lehetõséget, majd megvizsgálni, hogy az egyes királynõk ütik-e az utánuk következõket (mivel Uti(i,j)=Uti(j,i), azért ha pl. megvizsgáljuk Uti(3,6)-ot, fölösleges megvizsgálni Uti(6,3)-at). Az összes lehetõség kb. 16 millió, az ütések vizsgálata lehetõségenként 28 vizsgálat, Uti függvény tehát kb. 470 milliószor kerül meghívásra. Ráadásul minden újabb királynõ hozzávétele nagyságrenddel növeli a számításigényt. Más módszer után kell néznünk.

Rakjuk föl a következõ bábut (kezdetben az elsõt) az elsõ sorba. Ha üti valamelyik elõzõ, akkor toljuk egy sorral feljebb, egészen addig, amíg egy sem üti. Ha nem találunk neki jó sort, vegyük le, és az elõzõ bábut toljuk feljebb (visszalépés, azaz backtrack). Ha találtunk jó sort, folytassuk a következõ bábuval. Látható, hogy ez a folyamat kétféleképpen érhet véget: a nyolcadik bábunak is találtunk jó sort (van megoldás), vagy a legelsõ bábuhoz léptünk vissza úgy, hogy az már a nyolcadik sorban áll (nincs megoldás). A módszer azt is garantálja, hogy nem hagyunk ki egy jó lehetõséget sem.

Miért gyorsabb ez az elõzõ módszernél? Ha pl. a T[1]=1, T[2]=2 esetrõl kiderül, hogy nem jó, és T[2]-t továbbléptetjük, soha többé nem áll elõ olyan sorozat, amely 1,2-vel kezdõdik. Így tehát egy vizsgálattal kizártuk az összes, így kezdõdõ sorozatot.

Nézzük most a konkrét programot:

Function Jo(i:integer):boolean; {T[i] üti-e az elõzõeket}
 var j:integer;
 Begin
  j:=1;
  while (not uti(i,j)) and (j<i) do j:=j+1;
  Jo:=(j=i);
{végigmentünk ütés nélkül az elõzõeken}
 End;

var i:integer;
BEGIN
 for i:=1 to 8 do T[i]:=0;
 i:=1;
{az i. bábut vizsgáljuk}
 while (i>0) and (i<9) do begin
    T[i]:=T[i]+1;
{eggyel elõretoljuk az i. bábut}
    if T[i]>8 then begin
       T[i]:=0;
{ha nincs több lehetõség, visszalépés}
       i:=i-1;
    end else
       if Jo(i) then i:=i+1;
{továbblépés a következõre}
 end;
 if i>8 then for i:=1 to 8 do writeln(T[i])
        else writeln('Nincs megoldás.');
END.

A program kétféleképpen érhet véget: ha i=9, az azt jelenti, hogy az utolsó oszlopra is találtunk az elõzõeket nem ütõ megoldást, ezért továbbléptünk, és a ciklusnak vége, a megoldást ki lehet írni. Ha i=0, az azt jelenti, hogy már az elsõ oszlopra sincs több lehetõség, tehát nincs megoldás.

1. feladat: módosítsd a fenti programot úgy, hogy az összes megoldást írja ki! Tipp: jó megoldás kiírása után eggyel vissza kell lépni, az olyan, mintha nem fogadtuk volna el a megoldást, és a program elkezdi keresni a következõt.

A backtrack algoritmus általános megfogalmazása: keresünk egy véges sorozatot (legfeljebb N elemût). A sorozat minden eleme véges értéket vehet csak fel. Célszerû bevezetni egy alapértéket, amelynek a rákövetkezõje az elsõ lehetséges érték (a példában ez a 0 volt). Így az általános algoritmus:

Kezdõérték (T minden eleme felveszi az alapértéket)
i:=1
Ciklus amíg i>0 és i<N+1
   T[i]:=következõ érték
   Ha nincs több lehetséges érték, akkor
      T[i]:=alapérték, i:=i-1
   különben
      ha a sorozat T[1..i] része jó, akkor i:=i+1
Ciklus vége
Ha i>N akkor a megoldás kiírása

Az 1. feladat értelmében az algoritmus módosítható, hogy az összes jó megoldást kiírja. Célszerû az ilyen feladatokat úgy átalakítani, hogy a sorozat elemei 1 és x közötti egész számok lehessenek, ekkor az alapérték 0, a következõ érték pedig eggyel megnövelés (mint a példában). A backtrack-kel megoldható feladatoknál tehát az egyik probléma, hogy a feladatot véges sorozatra fogalmazzuk át. A másik megoldandó probléma a részsorozat jóságának eldöntése.

2. feladat: írj programot, mely megszámolja az összes 10-elemû szigorúan növekvõ sorozatot, melynek minden eleme 1 és 15 közötti egész szám!

3. feladat: írj programot, mely megadja az összes 6-elemû sorozatot, melynek tagjai 1 és 4 közötti egész számok, és minden szám legfeljebb 2-szer fordulhat elõ benne! Hogyan lehetne gyorsítani az elõzõ tagokkal való összehasonlításon?

Megjegyezzük, hogy a backtrack algoritmusnál a végeredményt tartalmazó tömböt veremként használtuk, mindig csak a legfelsõ elemével végeztünk mûveletet. (A sorozat jósága megállapításánál ez nem mindig igaz, a 8 királynõnél és a 3. feladatnál az összes elemet végig kellett vizsgálni, a 2. feladatnál csak az elõzõ elemet, tehát tömb helyett veremmel csak a 2. feladatot tudnánk megoldani.)

Nézzünk egy nehezebb feladatot, melyet már nem egyszerû backtrack-formára átalakítani. A sakktáblán kijelölünk két négyzetet, a cél pedig lóugrással eljutni az egyiktõl a másikig. A sorozat elemei lehetnek a sakktábla egyes mezõi. De egy mezõt sor-oszlop koordinátákkal azonosítunk, a sorozat elemei pedig egész számok! Beszá mozzuk tehát a mezõket 1-tõl 64-ig, és megírjuk azokat az eljárásokat, melyek ebbõl az értékbõl elõállítják a sor- oszlop koordinátákat, és viszont. Így pl. az 1. sor 1. oszlop az 1, a 8. sor 8. oszlop a 64 értéket kapja (a (sor- 1)·8+oszlop mûvelet például jó).

4. feladat: írd meg azt az eljárást, mely a mezõ sorszámából elõállítja a sor- és oszlop-értéket! Procedure Szam2koord(c:integer; var s,o:integer)

5. feladat: írd meg a Function Lo(s1,o1,s2,o2):boolean függvényt, amely megadja, hogy (s1,o1) mezõrõl (s2,o2) lóugrásnyira van-e.

Tehát olyan sorozatot keresünk, melynek hossza legfeljebb 64 (ennyi lépésben ugyanis bejárhattuk az egész táblát ismétlõdés nélkül), és elemei 1 és 64 között vannak. Az egymást követõ értékek jelentik a lóugrás-sorozat egymást követõ állomásait. A sorozat jó, ha minden eleme az elõzõbõl lóugrással elérhetõ, és nincs benne ismétlõdés (ezt azért kell kikötnünk, mert különben végtelen körbe kerülhetnénk, illetve elõállhatnának 64 lépésnél hosszabb megoldások is).

6. feladat: írj programot, mely bekéri a kiinduló és cél-mezõt, majd megad a kettõ között egy lóugrás-sorozatot! Figyelj arra, hogy a sorozat elsõ eleme már adott, a backtrack a 2. elemtõl indul! Valamint a leállás feltétele nem csak az, ha már a 65. elemnél tartunk, hanem az is, ha az i. elem megegyezik a cél-mezõvel. Ugyanis a megoldás egyáltalán nem biztos, hogy 64 lépésbõl áll (inkább rövidebb).

Látható, hogy a backtrack algoritmusa a célnak megfelelõen az alapötlet megtartásával átszabható (például akkor, ha a sorozat lehet N-nél rövidebb is). Az 5. feladat könnyen módosítható úgy, hogy megadja az összes jó sorozatot. Ekkor viszont meghatározható a legrövidebb út is (pl. az új sorozatot csak akkor írjuk ki, ha az elõzõnél rövidebb).

7. feladat: módosítsd az elõzõ programot: határozd meg a kiinduló és cél-mezõ közti legrövidebb utat!

A program nagyon sokáig fut, és mûködése során az is látszik, hogy miért: ha egyszer már talált egy 10- hosszúságú utat, teljesen feleslegesen megvizsgálja az annál hosszabbakat is. A ciklusmagot át kell írni, mégpedig úgy, hogy akkor is lépjen vissza, ha elértük az eddig talált legrövidebb út hosszát. Így a keresést leszûkítjük az eddig talált legrövidebb útnál rövidebb sorozatokra, és a program sokkal gyorsabb lesz.

8. feladat: módosítsd a programot ennek megfelelõen!

A backtrack egyszerû, hasznos módszer, melyre nagyon sokszor van szükség. Példák: adott síkidomokkal fedjünk le egy másik síkidomot. Gráfban két pont között keressünk utat.

Következõ fejezet
Elõzõ fejezet
Tartalomjegyzék
Honlap