A programozásban a backtracking technika alatt a
megoldástér szisztematikus bejárását
értjük.
A megoldás keresésekor elindulunk egy
irányba, feltételezve, hogy az a jó irány.
Ha valahol "zsákutcába" jutottunk, akkor
visszalépegetünk addig a legközelebbi pontig, ahol
tudunk más utat is választani és itt
a rákövetkező (másik) úton megyünk
tovább. A megvalósítás technikája
általában rekurzió.
7.2 Néhány backtrackinggel megoldható feladat
Nyolc vezér probléma:
Helyezzünk el egy 8x8-as
sakktáblán 8 vezért úgy, hogy azok ne
üssék egymást! (Tehát helyezzük el a
vezéreket úgy, hogy se egy sorban, se egy oszlopban, se
átlósan ne legyen egy vonalban kettő.)
Hányféleképpen lehetséges így
elhelyezni a vezéreket?
Labirintus:
Adva van egy M*N-es labirintus, (1,1) a
bejárat, (M,N) a kijárat. Keressünk egy utat a
bejárattól a kijáratig.
Sakk-huszár:
Keressünk egy olyan
huszárugrás-sorozatot, amely minden egyes pontot
érint a sakktáblán pontosan egyszer, és
ugyan oda tér vissza, ahonnan indult.
7.3
Nyolc vezér probléma
A feladatunk tehát a következő: helyezzünk
el egy
8x8-as sakktáblán 8 vezért úgy, hogy azok
ne üssék egymást (tehát
helyezzük el a vezéreket úgy, hogy se egy sorban, se
egy oszlopban,
se átlósan ne legyen egy vonalban kettő)! Általánosítva a feladatot: helyezzünk
el egy NxN-es sakktáblán N vezért úgy, hogy azok
ne üssék egymást!
Az egyszerűség kedvéért mi most a 4x4-es
sakktáblán fogjuk szemlélteni a megoldás
megtalálásának a menetét.
Az biztos, hogy minden oszlopban csak egy vezért
helyezhetünk el, mivel egyébként a két
vezér ütné egymást. Ezért
megpróbáljuk mindegyik oszlopoban egymás
után elhelyezni a vezéreket:
Az első vezért letesszük az első oszlop első sorába.
Majd a második oszlopba megpróbáljuk
elhelyezni a vezért az első sortól haladva a negyedik
sorig úgy, hogy az ne üsse az első oszlopban levő
vezért. Ha sikerült, megyünk tovább a harmadik
oszlopba; ha nem sikerült, akkor visszamegyünk az első
oszlophoz és ott a vezért eggyel lejjebb tesszük.
Így haladunk tovább, amíg nem sikerül a negyedik oszlopba is lerakni a vezért.
A
feladat megoldása 4x4-es sakktáblán
szemléltetve tehát lépésenként a
következő:
Az első oszlopban letesszük az első helyre (1. sorba) a vezért, feltételezve, hogy ez a jó hely:
Majd megpróbáljuk a következő vezért lerakni a második oszlopba...
A második oszlop
1. és 2. sorába nem tehetünk vezért, mivel
akkor ütné a már fent levőt (ábrán
pirossal jelölve). A 3. sorba le lehet rakni a vezért,
ezért letesszük oda, feltételezve hogy ez is a
jó helyre került:
Majd megpróbáljuk a következő vezért lerakni a harmadik oszlopba...
A harmadik oszlopban
sem az 1., 2., 3., sem a 4. helyre nem tehetünk vezért,
mivel mindegyik helyen ütné valamelyik már eddig
fent levő vezért:
Mivel így a harmadik oszlopba nem tudunk vezért tenni, ezért visszalépünk a második oszlopba
és ott a vezért eggyel lejjebb tesszük (tehát
a következő még nem kipróbált helyre):
Ezek után ismét megpróbáljuk lerani a vezért a harmadik oszlopba...
Most a harmadik oszlopban
az 1. sorba nem tehetünk vezért (mivel ütné az
első oszlopban levőt), de a 2. sorba már tehetünk,
ezért kitesszük oda:
Majd megpróbáljuk a következő vezért lerakni a negyedik oszlopba...
A negyedik oszlopban nem tudunk az 1., 2., 3., de a 4. helyre sem tenni vezért, mivel ütné valamelyik már fent levőt:
Ezért visszalépünk a harmadik oszlopba
és megpróbáljuk ott máshová (a sorra
következő helyekre, tehát a 3., 4. sorba) tenni a
vezért. Azonban itt sem tehetjük a vezért sem a 3.,
sem a 4. sorba, mivel akkor ütné az első két
oszlopban levőket:
Ezért visszamegyünk a második oszlopba.
Mivel itt már kipróbáltuk mind a négy
helyet, ezért semmi mást nem tehetünk, mint hogy
visszamegyünk egészen az első oszlopba és ott tesszük a vezért eggyel lejjebb:
Majd megpróbáljuk a következő vezért ismét lerakni a második oszlopba...
Most a második oszlop
1., 2., 3. sorába nem rakhatjuk le a vezért, mivel akkor
ütné az első oszlopban levőt. A 4. sorba azonban
lerakhatjuk:
Majd megpróbáljuk a harmadik vezért lerakni a harmadik oszlopba...
A harmadik oszlop 1. sorába letehetünk vezért, ezért lerakjuk oda:
Majd megpróbáljuk a következő vezért lerakni a negyedik oszlopba...
A negyedik oszlop 1., 2. sorába nem tehetünk vezért, de a 3. sorba lerakhatjuk:
Mivel sikerült a negyedik oszlopban is leraknunk a vezért,
ezért megtaláltuk a feladat egyik
megoldását, így befejeződhet az algoritmus. :-)
Ha az összes megoldást meg szeretnénk
találni, akkor a megtalált megoldás után
csak megjegyeznénk (esetleg kiírnánk) azt
és
mennénk tovább a keresésben. Tehát a fenti
példában a negyedik oszlop 4. sorával
folytatnánk a keresést, majd ismét
visszalépnénk a harmadik oszlopoz. Hasonlóan
folytatnánk mindaddig, amíg ki nem
próbáltuk az összes lehetőséget.
A backtracking technika előnye az, hogy ha
például már a harmadik vagy a negyedik oszlopban
nem tudunk továbblépni, akkor az utánnuk
következő oszlopokban nem is próbáljuk lerakni a
vezéreket. Így a programnak sokkal kisebb az időigénye,
sokkal hamarabb lefut, tehát sokkal hamarabb eljutunk a
megoldáshoz, mint ha kipróbáltuk volna négy
egymásba ágyazott ciklus segítségével az összes
lehetséges kombinációt (tehát ebben a
példában a 4*4*4*4 kombinációt).
NxN-es sakktáblán egy megoldás
megkeresésének menetét backtracking technikával az alábbi program
szemlélteti:
Írjunk egy programot, amely backtracking segítségével megkeresi az útvonalat a
bejárattól a kijáratig az alábbi labirintusban:
Mielőtt nekiállnánk, gondoljuk át, hogy milyen adatszerkezet segítségével
tudnánk ezt a labirintust ábrázolni a számítógépben. Jó megoldás lehet egy
kétdimenziós tömb használata, mely a következő képpen nézne ki:
A mi esetünkben egy 10x10-es tömböt használnánk, melyben az egyes elemek
értéke:
0
jelöli a még nem bejárt útvonalakat (tehát ahová
léphetünk),
9 jelöli a falat (tehát ahová nem léphetünk),
5 jelöli a célt (ha ide értünk, akkor megvan a megoldás).
Ezeken
kívül a feladat megoldása közben még két értéket vehetnek fel a tömb elemei:
1, amely az adott pontig bejárt, helyesnek tűnő útvonalat fogja
jelölni,
2, amely a mát bejárt, de zsákutcát (tehát nem a kijárathoz vezető)
útvonalat fogja jelölni.
A
megoldás keresése a következő lesz:
Elindulunk a bejáratnál (10.sor, 2. mező) és ezt
megjelöljük 1-essel.
Megnézzük, hogy mehetünk-e felfele (az adott hely feletti mező értéke 0
vagy 5). Ha mehetünk, akkor oda lépünk (tehát azt is bejelöljük 1-essel),
majd innen próbálunk tovább lépni. Ha nem mehetünk, akkor hasonlóan
megnézzük a jobbra, majd a balra, majd a lefele irányt és abba az irányba
megyünk, ahol szabad az útvonal (tehát ahol a tömbben 0 vagy 5
van).
Ha
valamelyik ponttól egyik irányban sem tudunk tovább lépni, akkor ezt a
pontot bejelöljük 2-essel (zsákutca), majd visszalépünk az előző
pontra, ahonnan próbálunk más irányba továbbmenni (vagy innen is visszalépni,
ha nem vezet sehova).
A
megoldás menetének keresését az alábbi animáció szemlélteti:
Az animációban az 1-es (zöld) jelöli a bejárt és helyes útvonalat, a 2-es (piros)
pedig azokat a mezőket, amelyeken keresztül próbáltuk megkeresni a helyes
útvonalat, de zsákutcába jutottunk (tehát ezekről vissza kellett lépnünk).
Végül nézzük meg a pascalban megírt programot, mely
megkeresi a fenti labirintusban a helyes útvonalat az említett algoritmus
szerint:
program
Pelda26;
uses crt;
var lab:array [1..10,1..10] of byte
= ((9,9,9,9,9,9,9,9,9,9),
(9,0,0,9,0,9,0,9,0,5),
(9,0,9,9,0,9,0,9,0,9),
(9,0,0,0,0,9,0,0,0,9),
(9,9,0,9,9,9,9,9,0,9),
(9,0,0,0,0,0,0,9,0,9),
(9,0,9,9,9,0,9,0,0,9),
(9,0,0,0,9,0,0,0,9,9),
(9,0,9,0,9,0,9,0,0,9),
(9,0,9,9,9,9,9,9,9,9));
procedure kiiras;
var i,j:integer;
begin
for i:=1 to 10 do
begin
for j:=1 to 10 do
case lab[i,j] of
9: begin
{fal}
textcolor(lightgray);
write(#219);
{ #219 = befestett negyzet karakter }
end;
0,5: write(' ');
{ ures vagy celpont }
1: begin
{ helyes utvonal }
textcolor(lightgreen);
write('X');
end;
2: begin
{ bejart, de rossz utvonal }
textcolor(red);
write('O');
end;
end;
writeln;
end;
writeln;
end;
procedure lepes(x,y:integer);
begin { nem ertunk be
a celba? }
if lab[x,y]<>5 then
begin { lepes
elore... }
lab[x,y]:=1; { van
felfele bejaratlan utvonal (ures vagy celpont)? }
if (x>1) and (lab[x-1,y] in [0,5]) then lepes(x-1,y); { van
jobbra bejaratlan utvonal (ures vagy celpont)? }
if (y<10) and (lab[x,y+1] in [0,5]) then lepes(x,y+1); { van
balra bejaratlan utvonal (ures vagy celpont)? }
if (y>1) and (lab[x,y-1] in [0,5]) then lepes(x,y-1); { van
lefele bejaratlan utvonal (ures vagy celpont)? }
if (x<10) and (lab[x+1,y] in [0,5]) then lepes(x+1,y); { lepes
vissza...
megjeloles bejart, de rossz utvonalnak }
lab[x,y]:=2;
end
else
begin { celba
ertunk, utolso lepes elore... }
lab[x,y]:=1; {
megtalalt utvonal kirajzolasa }
kiiras;
{ utolso lepes vissza } lab[x,y]:=2;
end;
end;
Az
programban megfigyelhettük, hogy miután megtaláltuk a labirintusból kivezető
útvonalat, kiírtuk azt a képernyőre, majd tovább folytatódott a keresés. Így
tehát, amennyiben a labirintusnak több kijárata is lenne (a tömbben 5-ös számmal
jelölve), megtalálnánk mindegyik kijárathoz a kivezető útvonalat.