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
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 keresztü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.)
… a szisztematikus előrehaladás és visszalépés bemutatása a
két feladaton keresztül …
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észhalmazá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 ellenő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 munkavállalóhoz?
Vállalhatja-e a munkavállaló sajátmaga miatt?
|
|
Mi az uf?
|
|
Van = …
Van Þ
…
|
Van = …
Van Þ
…
|
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áronké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.
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 kivitelezhető,
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.
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
Egy éhes egérnek egy labirintusban elhelyeznek egy darab
sajtot. Írjunk programot, amely segít az egérnek megkeresni a sajthoz vezető
utat!
1.
Mi az eredmény?
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..MaxHossz: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?
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.
Hogyan ábrázolandó a labirintus?
Pl. egy „térképpel” (Labirintus(Hol:Elem)
tömbbel),
amelyben háromféle érték fordulhat elő: fal, út
és sajt (Elem). A Hol „logikusan” lehet síkbeli pontok
koordinátapárja: (1..N,1..M).
Így tehát: Labirintus(1..N,1..M:
Elem) –most már tudjuk, 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.
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áltozó.
A program valódi paraméterei: Labirintus, RajtHely. (A továbbiakban nem foglalkozunk a
deklarációkkal.)
Program SajtKeresés:
…
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.
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 folyosó 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.)
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!
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álasztottal!)
5.
Meddig...:
amíg az összest le nem tettük.
Program 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.
Eljá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.
Lefedhető-e egy adott hosszúságú szakasz egyszeresen a H1,...,HN
hosszúságú kisebb szakaszokkal?
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.
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 megoldá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).
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.
Eljá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áltunk 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.