ProgramozásMódszertan
6. előadás’2004
(vázlat)

További Keresési tételek

1. Általános keresés

Induljunk ki a lineáris keresés már megismert algoritmusából, és hántsunk le róla minden konkrétat, adjuk meg a „leglényegét”!

Mik azok, amik túl konkrétak az adott algoritmusban?

· a sorozat éppen N elemű

· a sorozat „bejárása” (elemeinek sorravétele) éppen növekvő indexek irányába halad (persze nem lenne jobb a fordított sorrendű sem)

· a sorozat tömb(szerű) struktúrában tárolódik

Absztrakció:

Vezessük be az alábbi fogalmakat:

· LÎH^* *lehetségesek* sorozata	az eredeti X egy alkalmasan választott (algoritmus meghatározta) rész-sorozata (LÍX)
· ║.║: H^® N hossz*	a sorozat hossza (elemszáma)
· s: H^® H^ *szűkítés*	LÎH^*: (xÎs(L) Þ xÎL) Ù ║s(L)║<║L║ – azaz a s L-ből elhagy valahány elemet
· e: H^® N elemkijelölés*	LÎH^*: e(L)Î[1..║L║] – azaz e L egy lehetséges elemének indexét adja

A s és az e persze egymással szorosan összefüggnek. Ezt fejezi az alábbi állítás:

x_e(L)ÎL Ù x_e(L)Ïs(L).

Azaz a szűkítés során legalább az elemkijelölő függvény által meghatározott elemmel „rövidül meg” a sorozat.

Megjegyzés:

Sok esetben ennél több is teljesül: s(L)ÌL. Ekkor nyilvánvalóan teljesül a fenti, azaz s(L)ÌL Þ ((xÎs(L) Þ xÎL) Ù ║s(L)║<║L║).

Az absztrakt keresés tétel algoritmusa

Ezen fogalmakkal az általános keresés tétel algoritmusa az alábbi lesz:

1) L:=X
2) Ciklus amíg ║L║>0 és nem T(X(e(L)))
3) L:=s(L)
4) Ciklus vége
5) Van:=║L║>0
6) Ha Van akkor Sorsz:=e(L)

Ellenőrzésképp, valamint hogy jobban megértsük a fenti kulcsfontosságú függvények hatását, kövessük működés közben az algoritmust! Alkalmazzuk egy X=(x₁,x₂,…x_N) sorozatra, amelynek –tegyük föl– nincs T-tulajdonságú eleme:

*az algoritmus éppen végrehajtott utasítása*	L	a ciklusfeltétel kiértékelése
1) L:=X	(x₁,x₂,…x_N)
2) Ciklus amíg ║L║>0 és nem T(X(e(L)))		║(x₁,x₂,…x_N)║=N>0 [ºIgaz] nem T(X(e((x₁,x₂,…x_N))))= nem T(x_i1) [ºIgaz]
3) L:=s(L)	(x₁,…x_i1-1,x_i1+1,…x_N)
2) Ciklus amíg ║L║>0 és nem T(X(e(L)))		║(x₁,…x_i1-1,x_i1+1,…x_N)║=N-1>0 [ºIgaz] nem T(X(e((x₁,…x_i1-1,x_i1+1,…x_N))))= nem T(x_i2) [ºIgaz]
3) L:=s(L)	L: x_i1,x_i2ÏL
…
3) L:=s(L)	L: x_i1,…x_iN-1ÏL
2) Ciklus amíg ║L║>0 és nem T(X(e(L)))		║(x_iN)║=1>0 [ºIgaz] nem T(X(e((x_iN))))= nem T(x_iN) [ºIgaz]
3) L:=s(L)	L: x_i1,…x_iNÏL=()
2) Ciklus amíg ║L║>0 és nem T(X(e(L)))		║()║=0>0 [ºHamis]
5) Van:=║L║>0
6) Ha Van akkor Sorsz:=e(L)

A lineáris keresés tétel

Nézzük a lineáris keresés tétel újrafogalmazását az általános keresés algoritmusa alapján!

· L

L:=(x_i,…x_N) i: ahol tartunk az algoritmusban (i=1..N+1)

L egyértelműen jellemezhető, sőt helyettesíthető az algoritmus végrehajtásakor éppen érvényes első elemének indexével: L:=L(i)®i

Azaz minden L-re vonatkozó műveletben i-vel operál(hat)unk.

· s

s(L):=s(x_i,…x_N) Í (x_i+1,…x_N) – i eggyel növelését jelenti

Vagyis s(L)=s(L(i))=s(i)®i+1

· e

e(L):=i – a „mindenkori” vizsgált elem: L(i)-beli első elem indexe

Azaz e(L)=e(L(i))=e(i)®i

Ekkor ║L║=║L(i)║:=N-i+1, s az algoritmus maga:

*Az absztrakt keresés*	*A lineáris keresés*
L:=X	i:=1 [X 1. eleménél kezdődik a keresés]
Ciklus amíg ║L║>0	Ciklus amíg N-i+1>0 [1] [van még hol keresni]
és nem T(X(e(L)))	és nem T(X(i)) [az i. olyan-e]
L:=s(L)	i:+i [a következőnél kezdődik a sorozat]
Ciklus vége	Ciklus vége
Van:=║L║>0	Van:=N-i+1>0
Ha Van akkor Sorsz:=e(L)	Ha Van akkor Sorsz:=i [a keresett]

Hatékonyság (N>0):

Hasonlításszám	*Min*	*Átlag*	*Max*
Van keresett	1	N/2	N	O(N)
Nincs keresett	N	N	N	Q(N)

„Szokásos” s/e-függvénydefiníciók

A közismert keresésekben az alábbi értelmezésű függvényeket szoktuk párban használni:

e	s
e_e((x₁,...x_N)):=1 – első	s_e((x₁,...x_N)):=(x₂,...x_N) – első elem nélkül
e_u((x₁,...x_N)):=N – utolsó	s_u((x₁,...x_N)):=(x₁,...x_N-1) – utolsó elem nélkül
e_k((x₁,...x_k,…x_N)):=k, ahol k=(1+N) Div 2 – középső	s_<k((x₁,...x_N)):=(x₁,...x_k), ahol k=((1+N) Div 2)-1 – középső elem előttiek (világos, hogy (x₁,...x_k)Ì(x₁,...x_N) teljesül) s_>k((x₁,...x_N)):=(x_k,...x_N), ahol k=((1+N) Div 2)+1 – középső elem utániak (világos, hogy (x_k,...x_N)Ì(x₁,...x_N) teljesül)
e_e((x₁,...x_N)):=1 – első	s_<((x₁,...x_N)):=(x'₁,...x'_k), ahol "iÎ[l..k]: x'_iÎX Ù x'_i<x₁– elsőnél kisebbek (világos, hogy (x'Îs(L) Þ x'ÎL) Ù ║s(L)║<║L║ teljesül, hiszen "iÎ[l..k]: x'_i¹x₁)

Megjegyzés:

Talán sejthető, hogy a 2. e/s-pár a hátulról „bejárás” kellékei. A 3. a hamarosan sorra kerülő logaritmikus kereséshez, a 4. pedig a rekurzió-típus kapcsán szóba kerülő Quicksort rendezéshez tartoznak.

2. Lineáris keresés rendezett sorozatban

LinKeresésRendezettben(H^*,H,F(H´H,L)):L ÈLxN

Be: NÎN, XÎH^*, yÎH, £ÎF(HxH,L) (T_y:H®N, T_y (h):=(h=y))

Ki: VanÎL , SorszÎN

Ef: N=Hossz(X) Ù RendezettHalmaz_£(H) Ù RendezettSorozat_£(X)

Uf: Van º $iÎ[1..N] : x_i=y Ù Van Þ (SorszÎ[1..N] Ù x_Sorsz=y Ù "iÎ[1..Sorsz) : x_i<y)

Az absztrakt algoritmus elé:

· L

L:=(x_i,…x_N) – elejétől végig, i: ahol tartunk a végrehajtás során = 1..N+1

Figyelem, a rendezettség kihasználandó! A végrehajtás véget érhet még annak előtte, hogy az L sorozat N. eleméhez érnénk! Pontosan akkor, amikor az x_i>y első ízben bekövetkezik (elölről haladva).

L egyértelműen jellemezhető, sőt helyettesíthető az algoritmus végrehajtásakor éppen érvényes első elemének indexével: L:=L(i)®i

Azaz minden L-re vonatkozó műveletben i-vel operál(hat)unk.

· s

(1) s(L(i))®(x_i+1,...x_N), ha x_i£y

(2) s(L(i))®(x_N+1,...x_N), ha x_i>y

(Az világos, hogy (1) és (2) Þ s(L(i))Í(x_i,...x_N)=L(i))

Azaz s(L)=s(L(i))=s(i)®Ha x_i£y akkor i:+1 különben i:=N+1.

· e

e(L)=e₁(L(i)):=i – a „mindenkori” vizsgált elem: L(i)-beli első elem indexe

Azaz e(L)=e₁(L(i))=e₁(i)®i

Ekkor ║L(i)║=N-i+1, s így ║L(i)║>0 Û N-i+1>0 Û N³i.

„Vezessük le” az absztraktból:

*Az absztrakt keresés*	*Lineáris keresés rendezettben*
L:=X	i:=1 [X 1. eleménél kezdődik a keresés]
Ciklus amíg ║L║>0	Ciklus amíg N³i [van még hol keresni]
és nem T(X(e(L)))	és X(i)¹y [az i. olyan-e]
L:=s(L)	Elágazás X(i)£y esetén i:+1 X(i)>y esetén i:=N+1 Elágazás vége
Ciklus vége	Ciklus vége
Van:=║L║>0	Van:=N³i
Ha Van akkor Sorsz:=e(L)	Ha Van akkor Sorsz:=i [a keresett]

Az algoritmus bizonyos redundanciákat rejt, amiket az alábbiakban felderítünk és megszüntetünk.

Vegyük észre, hogy

A ciklusból két ok miatt léphetünk ki: „N<i vagy X(i)=y”

N<i	találtunk nagyobbat, azaz a korábbi i-re: X(i)>y (l. s definíciójának 2. ágát) vagy „simán” a sorozat végére értünk: N+1=i
X(i)=y	megtaláltuk a keresettet.

Az első olyan i, amelyre X(i)>y teljesült, rögvest beállítjuk az N+1=i ciklusfeltétel (egy) termináló értékét. Tehát figyelembe véve a X(i)¹y feltételt, világos, hogy eddig az elágazásnak csak az X(i)£y-hoz tartozó ága lett végrehajtva. Ezért „logikusnak” látszik redukálni a ciklusmagot az elágazás ezen ágára. Persze ez csak úgy történhet, hogy a hozzá tartozó feltétellel bővítjük a ciklusfeltételt… Azaz

Ciklus N³i és X(i)¹y és X(i)£y
i:+1
Ciklus vége

E lépéssel viszont összekavartunk két eddig könnyen szétválasztható esetet. Figyeljük meg, mi teljesült a ciklus után a korábbi (még helyes) algoritmusban, és mi a mostaniban:

Ha …	*Korábban*	*Most*
…benne van	N³i [és X(i)=y]	N³i és X(i)=y
…nincs benne	i>N	N³i és X(i)>y [mert sebtében kiléptünk] vagy i>N [mert a sorozat végére értünk]

Az N³i feltétel már egymaga nem képes megválaszolni a keresés sikerességének kérdését. Ebből következőleg a folytatást is módosítani kell!

Van:=N³i és X(i)=y

Az algoritmus ezek után:

Alg:

Eljárás LinKeresRendben(Konstans N:Egész, X:THk, Y:TH
Változó Van:Logikai, Sorsz:Egész):
Változó
i:Egész

i:=1
Ciklus amíg N³i és X(i)<y
i:+1
Ciklus vége
Van:=N³i és X(i)=y
Ha Van akkor Sorsz:=i
Eljárás vége.

Hatékonyság (N>0):

Hasonlításszám	*Min*	*Átlag*	*Max*
Van keresett	1+1[2]	(N+3)/2[3]	N+1	O(N)
Nincs keresett	1+1	(N+5)/2[4]	N+1	O(N)

Vö. a lineáris kereséssel!

3. Logaritmikus keresés

LogaritmikusKeresés(H^*,H,F(H´H,L)):L ÈLxN

Be: NÎN, XÎH^*, yÎH, £ÎF(H´H,L) (T_y:H®L, T_y (h):=(h=y))

Ki: VanÎL , SorszÎN

Ef: N=Hossz(X) Ù RendezettHalmaz_£(H) Ù RendezettSorozat_£(X) Ù
$elem:H^*´N®H szelekciós függvény: elem(X,i)=x_i[5]

Uf: Van º $iÎ[1..N] : x_i=y Ù Van Þ (SorszÎ[1..N] Ù x_Sorsz=y)

Az absztrakt algoritmus elé:

· L

L:=(x_e,…x_u) – a mindenkori elejétől az utolsóig, kezdetben (e,u)=(1,N)

L egyértelműen jellemezhető, sőt helyettesíthető az algoritmus végrehajtásakor éppen érvényes első + utolsó elemének indexével: L:=L(e,u)®(e,u)

Azaz minden L-re vonatkozó műveletben e-vel és/vagy u-val operál(hat)unk.

· s

(1) s(L(e,v)):=s_<_k(L(e,v)), ha x_e_(L(e,v))<y

(2) s(L(e,v)):=s_>k(L(e,v)), ha x_e_(L(e,v))>y

Azaz s(L)=s(L(e,v))=s(e,v)®    Elágazás
                                                     x_e_(L(e,v))<y esetén (e,v):=(e,e(L(e,v))-1)
                                                     x_e_(L(e,v))>y esetén (e,v):=(e(L(e,v))+1,v)
                                                     Elágazás vége.

· e

e(L(e,v)):=e_k(L(e,v)):=(e+v) Div 2 – a mindenkori sorozat középső elemének indexe

Azaz e(L)=e_k(L(e,v))=e_k(e,v)®(e+v) Div 2

Ekkor ║L(e,v)║=v-e+1, s így ║L(e,v)║>0 Û v-e+1>0 Û v³e.

„Vezessük le” az absztraktból:

*Az absztrakt keresés*	*Logaritmikus keresés*
L:=X	(e,v):=(1,N)
Ciklus amíg ║L║>0	Ciklus amíg v³e [van még hol keresni]
és nem T(X(e(L)))	és X((e+v) Div 2)¹y [az i. olyan-e]
L:=s(L)	Elágazás X((e+v) Div 2)<y esetén (e,v):=(e,(e+v) Div 2-1) X((e+v) Div 2)>y esetén (e,v):=((e+v) Div 2+1,v) Elágazás vége
Ciklus vége	Ciklus vége
Van:=║L║>0	Van:=v³e
Ha Van akkor Sorsz:=e(L)	Ha Van akkor Sorsz:=(e+v) Div 2

Megjegyzés:

Az egyszerűbb leírhatóság és a többszörös kiszámolás elkerülése érdekében tároljuk az e(L(e,v))-dik (=(e+v) DIV 2) elem indexét a k változóban, e leválasztás viszont a külön számolást jelent! Másrészt az „X(k)¹y” feltétel a ciklusfeltételben egy feltétel vizsgálattal elintézhetőre egyszerűsíti a ciklusmagbeli elágazást. Harmadrészt, az üres értékadásokat elhagyjuk. Így az alábbi algoritmus marad:

Alg:

Eljárás LogKeresés(Konstans N:Egész, X:THk, Y:TH
Változó Van:Logikai, Sorsz:Egész):
Változó
e,v,k:Egész

(e,v):=(1,N); k:=(e+v) Div 2
Ciklus amíg v³e és X(k)¹y
    Ha X(k)<y akkor (e,v):=(e,k-1)
            különben (e,v):=(k+1,v)
    k:=(e+v) Div 2
Ciklus vége
Van:=v³e
Ha Van akkor Sorsz:=k
Eljárás vége.

Hatékonyság (N>0):

Hasonlításszám	*Min*	*Átlag*	*Max*
Van keresett	1	~2*(log₂(N)-1)[6]	é2*log₂(N)ù	O(log₂(N))
Nincs keresett	é2*log₂(N)ù	2*log₂(N)	é2*log₂(N)ù	Q(log₂(N))

Vö. a lineáris keresés rendezettben hatékonyságával!

Megjegyzés:

A fenti számításban szereplő kettesalapú logaritmus (is) magyarázza, miért emlegetik e keresést gyakorta „bináris keresés”-ként.

3. Visszalépéses keresés (backtrack)

3.1. A „backtrack” gondolat

Bevezetésként gondolkozzunk el egy-két tipikus feladaton és ezek megoldásvázlatain.

1. feladat:

Adott egy N´N-es sakktábla. Helyezzünk el rajta N vezért úgy, hogy ne üssék egymást!

1. megoldásvázlat:

Helyezzük el valahogy az N vezért, majd döntsük el, ütik-e egymást! Ha igen, helyezzük el másként. Addig próbálkozzunk, amíg sikert nem érünk.

Bajok:

1. Hogyan helyezzük el a vezéreket úgy, hogy nyugodtak lehessünk: nem marad ki véletlenül egy lehetséges elhelyezés.

2. Nagyon sok lehetőséget kell kipróbálni. Jelen esetben: .

Ui.: az 1. vezérnek N² lehetősége van, a 2.-nak eggyel kevesebb, az N.-nek N²-N+1.

2. megoldásvázlat:

Minden vezérhez rendeljünk egy oszlopot, amelybe el próbáljuk helyezni. Az elhelyezés után ellenőrizzük, ütik-e egymást! Ha igen, válasszuk a következő helyet a saját oszlopában az N.-nek. Ha összes lehetőségét kimerítettük az N.-nek, akkor válasszuk az N-1. következőjét. Így gondolkozunk, ha az N-1. helyeit is kimerítettük… Addig próbálkozzunk, amíg sikert nem érünk.

Bajok közül az 1.-n túl tehetjük magunkat, a 2. is mérséklődött, de azért elégedettek nem lehetünk. Hiszen még mindig nagyszámú lehetőség végiggondolásával érhetünk csak célt: N^N.

3. megoldásvázlat:

Ha magunknak kellene kézzel a vezéreket elhelyezni, bizonyára az alábbi szisztéma mellett döntenénk:

Sorszámozzuk meg az oszlopokat és a sorokat 1-től N-ig. Helyezzük el az 1. vezért az 1. oszlopba! Keressük meg a 2. vezérnek az első adandó mezőt a 2. oszlopba, éít. Ha egyik vezérnél már nem találunk alkalmas mezőt, akkor –azt gondolván, hogy az eddigiek vannak rossz helyen– az előzőnek keresünk egy „jobbnak” ígérkező helyett (az eddig még nem vizsgáltak között). Vagy, ha már neki sincs további alkalmasnak tűnő, akkor az azt megelőzővel foglalkozunk, vagy az azt megelőzővel éít., addig amíg meg nem találtuk az igazi elhelyezést…

Valahogy így: nézzük meg a demonstrációt!

2. feladat:

Hányféleképpen lehet címletezni N Ft-ot? Nyilván adottak a címletezésben szereplő bankjegyek, ill. pénzérmék.

1. megoldásvázlat:

Vegyük a legkisebb névértékű pénzérmét vagy bankjegyet, s határozzuk meg, belőle hány kellene az N Ft felváltásához. (Megengedjük, hogy ez pontosan nem sikerül, ekkor azt a legkisebb számot kerestük, amely darabnyi ebből nem kevesebb, mint N Ft.) Az biztos, hogy minden megoldás ennél nem több címletet használ föl. Állítsuk tehát elő valamilyen szisztematikus sorrendben az összes legfeljebb ennyi címletet tartalmazó sorozatot, majd számoljuk meg hánynak éppen N az értéke.

2. megoldásvázlat:

Rakjuk –mondjuk érték szerint csökkenő– sorrendbe a címletezésben felhasználható bankjegyeket és pénzérméket. Állítsunk elő egy lehetséges felváltását az N Ft-nak az alábbiak szerint.

Válasszuk ki azt a címletet, amely nem nagyobb, mint a címletezendő összeg, és vonjuk le belőle a címlet értékét. Járjunk így a maradék összeggel. Világos, hogy egyre kisebb címletekkel próbálkozunk. Ha a maradék összeg már nem címletezhető, akkor a legutóbbi választásunkat visszavonjuk (visszaadva értékét a maradék összeghez) és a következő (kisebb értékű) címlettel teszünk kísérletet.

Ha egy címletezést megkaptunk, akkor a megoldás-számlálót növeljük, majd a következő megoldást ebből kiindulva úgy próbáljuk megtalálni, hogy „eldobjuk” az utolsó címletet –mintha rossz lett volna– és keresünk egy másikat, éppenúgy, ahogy eddig tettük.

Az biztos, hogy ugyanazt a címletezést kétszer nem kaphatjuk meg, mert címletkombinációkat (azaz sorrendfüggetlen címlet-összeállítást) generáltunk (a rendezettség és a szisztematikus választás miatt).

3. feladat:

Egy éhes egérnek egy labirintusban elhelyeznek egy darab sajtot. Segítsünk az egérnek megkeresni a sajthoz vezető utat!

Megoldásvázlat:

Kiindulási ponttól lépésről lépesre a következőt tesszük. A labirintus folyosójának egy-egy pontjából odébb lépni többnyire 2 irányba lehet: előre és vissza. A visszafelé lépést el kell kerülni, sőt általában is elkerülendő egy olyan helyre lépés, ahol már játunk. (Ellenkező esetben végtelen ciklusban kódorognánk a labirintusban.) Ha azonban egy útelágazáshoz érünk, akkor szisztematikusan válasszunk az irányok közül. Mindaddig haladunk, amíg zsákutcába nem jutunk. Ekkor visszavonogatjuk lépéseinket mindaddig, amíg egy olyan útelágazáshoz nem érünk, ahol van még eddig nem választott irány.

Valahogy így: nézzük meg a demonstrációt! (Vajon milyen sorrendben[7] „néz körül” az egér? Állapítsa meg a demonstráció alapján!)

3.2. A backtrack alapú keresés

Milyen feladat tehát a „backtrack”-feladat? Vonjunk le következtetéseket a példákból!

1. Kimenet: mindegyiknél egy sorozatot állítunk elő.

1. feladat: ~~mező-koordináták /~~ sor-indexek sorozata

2. feladat: a címletek sorozata

3. feladat: a lépésirányok sorozata

2. Bemenet: több sorozat, amelyekből (mindegyikből egy-egy) állítjuk elő a kimenet egyetlen sorozatát.

1. feladat: i. alapsorozat=i. oszlop

2. feladat: i. alapsorozat=címletek sorozata

3. feladat: i. alapsorozat=lépésirányok sorozata

3. Valamiféle összefüggés kapcsolja össze az eddig kiválasztott értékeket és a következőként kiválasztható értéket.

1. feladat: az (i-1).-ig letettek ne üssék az i.-et

2. feladat: az (i-1).-ig kiválasztott címleteknél nem lehet nagyobb az i. címlet, és össz értékük nem lehet nagyobb N Ft-nál

3. feladat: az i. lépés után nem lehet az egér olyan helyen, ahol már járt.

BacktrackKeresés(´₍_i_=1..K)H_i^*, F(È₍_j_=1..K)(´₍_i_=1..j)H_i),L)):L ÈLxN^*[8]

Egy másik szignatúra is rendelhető a feladathoz:

BacktrackKeresés(´₍_i_=1..K)H_i^*, F(N^*,L)):L ÈLxN^*[9]

Be:      KÎN, MÎN^*             – K elemszámú méretsorozat,
            Y_iÎH_i^* (iÎ[1..K])     – m_i elemszámú lehetőségsorozatok,
            l: H_j®L    – lehetőségek összeférése,

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

Ef: K=Hossz(M) Ù K³2 Ù "iÎ[1..K]: ( M_j=Hossz(Y_j) Ù HalmazFölsorolás(Y_j) ) Ù "jÎ[1..K], "iÎ[1..j]: l(h₁,...h_j) Þ l(h₁,...h_i)	Ef: K=Hossz(M) Ù K³2 Ù "iÎ[1..K]: ( M_j=Hossz(Y_j) Ù HalmazFölsorolás(Y_j) ) Ù "jÎ[1..K], "iÎ[1..j]: l(n₁,...n_j) Þ l(n₁,...n_i)
az első változat előfeltétele	a második változat előfeltétele
Uf: Van º $ZÎY₁´Y₂´...´Y_K: l(Z) Ù	Uf: Van º $ZÎ[1..m₁]´[1..m₂]´...´[1..m_K]: l(Z) Ù
az első változat utófeltétele	a második változat utófeltétele

Az absztrakt algoritmus elé:

· L

A keresett megoldás a Y_i K-dimenziós (L-) tér egy pontja, amely kielégíti az l-t. Ennek megadását az X-tömb végzi a Y_i-beli komponensek indexeinek felsorolásával. A megoldás keresése során e teret kell ügyesen bejárnunk, lehetőleg úgy, hogy ne kelljen mind az M₁*...* M_K „pontjának” vizsgálatát elvégeznünk. Ezt úgy tesszük, hogy szisztematikusan szűkítjük a teret egyre szűkülő alterek uniójára, azáltal, hogy újabb és újabb komponensét kötjük meg a leendő megoldásnak. Kezdetben csak az 1. dimenzióban lesz kötött érték. Ekkor tehát a térnek azt a K-1 dimenziós alterét szemeltük ki további vizsgálatra, amelynek 1. komponense éppen a rögzített érték. A vizsgálatra szoruló pontok halmaza még a teljes tér. Amikor kiderül a komponensek konkretizálása során, hogy a „koncentrált” altér nem tartalmazhatja a megoldást, akkor a teljes alteret elvetve vesszük a „szomszédos” (valamelyik soronkövetkező, azaz a megfelelő Y_i -beli későbbi elem által meghatározott) alteret.

Ezek után az L a következő indexsorozatok halmaza: az (1,1,...1), első elemek sorozatától az (m₁,m₂,...m_K) utolsó sorozatig „tart”. (Az m_i=║Y_i║.) (Formális okok miatt egészítsük ki a fenti teret olyan elemekkel is, amelyek bármely koordinátája a 0 is lehet.) Ezt a halmazt tesszük pontok sorozatává az e és s függvények segítségével.

A gondolatmenetből nyilvánvaló, hogy a pontfelsorolás alapja az L-beli sorozatok kezdőszeletei lesznek. Az aktuális L azonosítására mód van a „kiinduló” sorozat nem triviális (azaz rögzített) elemeket tartalmazó kezdőszelete által:

L:=L(x₁,x₂,...x_i) (az x_i -k az indexeket jelentik).

Azaz minden L-re vonatkozó műveletben i-vel és X-szel operálunk.

Egyszerűség kedvéért elvárjuk, hogy

L(x₁,x₂,...x_i)=L(x₁,x₂,...x_i,0,...0).

Tehát L(x₁,x₂,...x_i) az alábbi halmazt jelöli valójában:

            L(x₁,x₂,...x_i) = {(x₁,x₂,...x_i,z_i+1,...z_K)½ "jÎ[i+1..K]: z_jÎ[1..m_j]}
                                    È_(z=xi+1..Mi₎ L(x₁,x₂,...x_i-1,z)
            – pirossal emeltük ki a rögzített paramétereket.

Például az L-tér az

1. feladatban: i. dimenziója az i. vezér sorkoordinátáinak halmaza[10]

2. feladatban: i. dimenziója az i.-ként kiválasztható címletek halmaza, a tér annyi „dimenziós”, ahány címlet szükségeltetik maximálisan a címletezéshez

3. feladatban: az i. (és az összes) dimenziója a lépésirányok halmaza, a „dimenziószám” az út hossza.

Vegyük észre az L alábbi tulajdonságait!

1. Az összes lehetőség L halmaza: L(1,1,...,1).

2. Monoton csökkenés:

a. L(x₁,...,x_i)=L(x₁,...x_i+1) "x_i+1Î[1..m_i+1],

azaz „előrehaladáskor” nem csökken a vizsgálatban szereplők száma;

b. L(x₁,...,x_i)ÉL(x₁,...x_i-2,z_i-1) "z_i-1Î(x_i-1..m_i-1].

azaz „visszalépéskor” éppen annyival csökken, ahány „dimenziós” alteret sikerült kizárni a további vizsgálatból, pontosabban éppen az

{(x₁,...,x_i-1,z_i,...,z_K)½ "jÎ[i..K] z_jÎ[1..m_j] }

alteret, ami elemszáma ;

c. L(x₁,...,x_i)ÉL(x₁,...x_i-1,z_i) " z_iÎ(x_i..m_i],

azaz többszörös visszalépés után az „átlépett” alterekbeli elemekkel csökkenthető a vizsgálat;

d. a b. és a c.-ből következik, hogy a „legkisebb” L(x₁,...,x_i) az L(), amely az L(x_m₁)-ből való visszalépés után adódik. Ebben 0 darab elem van.

Az „L-mérték” nyomonkövetését végzi a ║.║ függvény, így elkerülhetetlen ennek matematikai megragadása. Nyilvánvaló lehetőség lenne az előbbiekre építve a még ki nem szórt pontok számával mérni. Ennél lényegesen egyszerűbb mód is van. A d. figyelembe vételével az L üressé válását észlelhetjük az éppen a lerögzített elemek számának figyelésével: amikor az 0-ra csökken, akkor ürült ki a tér is.

Vagyis, ha i jelöli a kezdőszelet aktuális hosszát (L=L(x₁,...,x_i)), akkor

║L║>0 Û i³1

illetve ha a végrehajtás során a K.-et is kielégítettük, akkor találtuk meg a keresett elemét a térnek:

i>K

· s

(1) s(L(x₁,...x_i)):=L(x₁,...x_i,x_i+1), ha i≤K Ù l(x₁,…x_i-1,x_i)
– előrelépés

(2)    s(L(x₁,...x_i)):=L(x₁,...z_j,0), ha i³1 Ù
                                                        Øl(x₁,…x_i-1,x_i) Ù $^*jÎ[1..i): $_*z_jÎ(x_j..m_j]: l(x₁,…z_j)
                                                                                                                 – visszalépés

($_*,$^*jelentése:
$_*pÎ[a..f]: létezik és ha nem egyértelmű, akkor közülük az első, azaz az a-hoz legközelebbi)…
$^*pÎ[a..f]: létezik és ha nem egyértelmű, akkor közülük az utolsó, azaz az f-hez legközelebbi)

(3) s(L(x₁,...x_i)):=(0,0,…0), egyéb esetben
– leállás, kielégíthetetlen esetben.

· e

e(L(x₁,...,x_i)):=(x₁,...,x_i,0,...,0)

Alg:

Konstans MaxN:Egész(???)
Típus TMk=Tömb(1..MaxN:Egész)
TXk=Tömb(1..MaxN:Egész)
TKeresett=Rekord(van:Logikai, melyik:Egész)

Eljárás BacktrackKeresés(Konstans K:Egész
                         Változó Van:Logikai, X:TXk):
Változó
    i:Egész
    ker:TKeresett

i:=1; X(1..K):=0 [az i. kezdőszeletnél tartunk]
Ciklus amíg i³1 és i£K
    ker:=JóElem(i)
    Elágazás
      i≤K és ker.van esetén X(i):=ker.melyik; i:+1
          i³1        esetén X(i):=0; i:-1
    Elágazás vége
Ciklus vége
Van:=i³1
[X-ben található a megoldás, ha létezik]
Eljárás vége.

A ciklusmagban a s-transzformáció nem „eredeti” megfelelője található, hanem annak egy módosított (egyszerűsített, de ekvivalens) változata. (A (2)-ág bonyolult feltétele egy keresés tétellel lenne megvalósítható. Ennek ciklusa „egyesíthető” a befoglaló külső ciklussal. S így nyertük a fenti megoldást.)

Mivel a ciklusban csak i³1 és i£K esetben vagyunk, s csak ekkor történhet az i növelése, vagy csökkentése, ezért a kétirányú elágazás helyett írható Ha-típusú elágazás is, egyszerűbb feltétellel. Így kapjuk (csak a ciklusbelüli részt ismételjük meg):

Ciklus amíg i³1 és i£K
    ker:=JóElem(i) [az i.-ig lehetséges-e a kiválasztás?]
    Ha ker.van akkor X(i):=ker.melyik; i:+1
             különben X(i):=0; i:-1
Ciklus vége

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..K) 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 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:=l(Y(1)(X(1)),...,Y(i-1)(X(i-1)),Y(i)(j))
Függvény vége.

Érdemes meggondolni az egyes konkrét feladatmegoldásoknál, mekkora a hatékonyságnövekedés a „naiv” megoldáshoz képest.

Rekurzív változat

Alkalmazás példákra

3.3. A backtrack gondolat további tételekben

Ha nem keresnünk kell backtrack alapon, akkor sincs nagy vész, mivel mechanikus átírási sablonok segítenek nekünk. Mindössze annyi az észreveendő, hogy

Absztrakt keresés algoritmusának fogalma	*Backtrack algoritmus kelléke*
║L║>0	i³1
T(e(L))	i£K
L :=s(L)	ker:=JóElem(i) Ha ker.van akkor X(i):=ker.melyik; i:+1 Különben X(i):=0; i:-1 Elágazás vége

Nincs más teendőnk, mint az algoritmus legfelsőbb szintjét minimálisan újraalkotni. Arra persze oda kell figyelni, hogy ugyanaz a változó az alapalgorimusban esetleg nem ugyanazzal a jelentéssel bír, mint a backtrack-es változatban.

A kiválasztás:

*Alapalgoritmus*	*Backtrack-változat*
i:=1 Ciklus amíg nem T(X(i)) i:+1 Ciklus vége Sorsz:=i	i:=1; X(1..K):=0 Ciklus amíg i£K ker:=JóElem(i) Ha ker.van akkor X(i):=ker.melyik; i:+1 Különben X(i):=0; i:-1 Elágazás vége Ciklus vége [a keresett elem az X-ben]

A megszámlálás:

*Alapalgoritmus*	*Backtrack-változat[11]*
Db:=0 Ciklus i=1-től N-ig Ha T(X(i)) akkor Db:+1 Ciklus vége	Db:=0 i:=1; X(1..K):=0 Ciklus amíg i³1 Ha i>K akkor Db:+1; i:-1 [visszalépés] Elágazás vége ker:=JóElem(i) Ha ker.van akkor X(i):=ker.melyik; i:+1 Különben X(i):=0; i:-1 Elágazás vége Ciklus vége

A maximum-kiválasztás:

Itt feltételezzük, hogy $£,< rendezés az L téren, ami X megoldásokat összevethetővé teszi. Az egyszerűség kedvéért föltesszük, hogy az L legkisebb eleme az (0,...,0), azaz "(x₁,x₁,… x_K)ÎL: (0,...,0)<(x₁,x₁,… x_K).

*Alapalgoritmus*	*Backtrack-változat*
max:=X(1) Ciklus i=2-től N-ig Ha X(i)>max akkor max:=X(i) Ciklus vége	i:=1; X(1..K):=0 max:=X Ciklus amíg i³1 Ha i>K akkor Ha X>max akkor max:=X i:-1 [visszalépés] Elágazás vége Elágazás vége ker:=JóElem(i) Ha ker.van akkor X(i):=ker.melyik; i:+1 Különben X(i):=0; i:-1 Elágazás vége Ciklus vége [max-ban a „leg”]

[1] N-i+1>0 Û N>i-1 Û N³i . S ez a lineáris keresésben előforduló ciklusfeltétel első tényezője.

[2] A „+1” a ciklus utáni hasonlítást számlálja.

[3] ((1+1) [X(1)=y]+ (2+1) [X(2)=y]+…+(N+1) [X(N)=y])/N=(N*(N+1)/2+N)/N = (N/2*((N+1)+2))/N = (N+3)/2

[4] ((1+1) [X(1)>y]+ (2+1) [X(2)>y]+…+(N+1) [X(N)>y]+(N+0) [X(N)<y])/N=((N*(N+1)/2+N)+N)/N = =(N/2*((N+1)+4))/N = (N+5)/2

[5] Ugyanez kifejezhető úgy is, hogy X közvetlen elérésű.

[6] Az átlagos hasonlításszám kalkulálásához meg kell határozni az összehasonlítás fa átlagos ághosszat. Ez egyenletes eloszlást feltételezve n! számú ág hosszának átlagolását jelenti. Mivel a fa „lefelé” exponenciálisan terebélyesedik, ezért az átlag alig lesz kevesebb, mint a maximális.

[7] A „körülnézés” abszolút sorrendben történik (azaz nem függ attól, hogy az egér éppen milyen irányban halad): Nyugat, Észak, Kelet, Dél.

[8] A szignatúráról:

1. paraméter – K db alaphalmazon nyugvó sorozatok direktszorzata (K db sorozat)

2. paraméter – egy logikai értékű függvény, amely az alaphalmazokból vett egy-egy elemből alkotott sorozat kezdőszeleteihez rendel Igaz/Hamis értéket.

[9] A szignatúráról:

1. paraméter – K db alaphalmazon nyugvó sorozatok direktszorzata (K db sorozat)

2. paraméter – egy logikai értékű függvény, amely egy indexsorozat kezdőszeleteihez rendel Igaz/Hamis értéket. Az i. index az i. alapsorozathoz tartozik, s azt fejezi ki, hogy abból éppen az i.-ket választottuk ki.

[10] Jobb lenne sorozatot mondani a halmaz helyett, hiszen, mint hamarosan kiderül, ebből kell valahányadikat kiválasztani, ami egy halmazból lehetetlen.

[11] Először a számlálásos ciklust amíg-ossá alakítottuk, s csak azután álltunk a mechanikus átíráshoz.

ProgramozásMódszertan 6. előadás’2004 (vázlat)

„Szokásos” s/e-függvénydefiníciók

ProgramozásMódszertan
6. előadás’2004
(vázlat)