Tartalom
B2.
Útban a megoldás felé – Problémák
B4.
További problémák, kérdések
C2.
Útban a megoldás felé – Problémák
D2.
Útban a megoldás felé – Problémák
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) b.
sakktábla oszlop vagy sor-index (N)
|
N
munkavállalóhoz tartozó munka (Munka) 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) b. összes sakktábla oszlop (sor)-index (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* b. összes (M) munka vállalhatósága: LM, |
Mi az fk
függvény? Általában (jelentése
és tulajdonsága) |
|
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) |
|
Æ |
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 = … |
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 |
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.
Mi az
algoritmus? |
|
… |
… |
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.
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
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[1]), 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:
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.
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.
§ 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!