A probléma vizsgálata
Egy dominósor végei alatt a sorozat két végén lévő fél-dominókon lévő pöttyök számát fogjuk értnei...
Ez a nagyfejezet innentől nem feltétlenül kell a megoldás megértéséhez.
Sebesség
Nézzük meg először a minden lehetőséget végignéző, rekurzív back-track eljárást.
Legyen a Leghosszabb(a, b, i) egy olyan függvény, ami megadja, hogy ha Mohó Marci az i. dominónál tart, és a kirakott dominósor egyik végén a db. pötty van, a másikon pedig b db, akkor milyen hosszú lehet a kirakott dominósor lehető leghosszabb kiegészítése. Így a megoldás értéke Leghosszabb(domino1[1], domino2[1], 2) lesz, ahol domino1[i] az i. dominó egyik vége, domino2[i] pedig a másik vége. (A dominón lévő pöttyök számáról van szó természetesen.)
A Leghosszabb(a, b, i) eljárást úgy lehet pl. megírni, hogy önmaga meghívásának a segítségével kiválasztja, hogy az i. dominó a-b sorhoz való illesztései közül melyik adja a leghosszabb folytatást, és hozzáad egyet. A visszatérési érék pedig lehet ez a kapott hossz, vagy az abban az esetben adódó folytatás hossza, amikor az i. dominó nem kerül illesztésre, attól függően, hogy melyik érték a nagyobb.
Eljárás Leghosszabb(a, b, i)
Ha i > N Akkor Leghosszabb := 0;
Különben
x := domino1[i]; y := domino2[i];
h1 := 0; h2 := 0; h3 := 0; h4 := 0; h5 := 0;
Ha x = a Akkor h1 := 1 + Leghosszabb(y, b, i+1);
Ha y = a Akkor h2 := 1 + Leghosszabb(x, b, i+1);
Ha x = b Akkor h3 := 1 + Leghosszabb(y, a, i+1);
Ha y = b Akkor h4 := 1 + Leghosszabb(x, a, i+1);
h5 := Leghosszabb(a, b, i+1);
Leghosszabb := Maximum(h1, h2, h3, h4, h5);
Elágazás Vége
Eljárás Vége
Ez a rekurzió $100,000$ szintes is lehet, szintenként 1 és 5 közötti irányba ágazik, és minden ágon lemegy a legalsó szintig. (A felső határ valójában 5 helyett 3, ha megírjuk, hogy azonos dominósorok hosszát ne kérdezze le többször.) A szükséges lépések száma viszont így valamilyen $x^{100000}$ nagyságrendű szám lesz, ahol ($1 \leq x \leq 3$) az elágazások átlagos száma. $x$-et nagyon nehéz lenne normálisan kiszámolni, de nagyobb lesz 1-nél annyival, hogy ez reménytelenül sok legyen. (Jobb becslések?)
Segíthetünk viszont algoritmusunkon a feljegyzéses módszerrel: felveszünk egy 10-szer 10-szer 100,000-es cache[a, b, i] tömböt, amibe minig eltároljuk ez eljárás lefutásának az eredményét, tehát egy paraméter-kombinációra már csak egyszer fog lefutni. Így már legfeljebb csak $10 * 10 * 100,000 = 10,000,000$ lépésre lesz szükség, és ez már vállalható. A cache[] tömbnek viszon dominósor-hosszakat kell tárolni, amik 0 és 100,000 közti számok lehetnek, amiket valószínűleg 4 bájtos változókban fogunk tárolni, de legalább is 7-bitesekben. Ez így már 20-40 megabájt lefoglalt memóriát jelent, ami nagyon sok. (A szükséges verem-területről nem is beszélve.) De vizsgáljuk meg a memória-problémát kicsit közelebbről is...
Memória
A programnak legrosszabb esetben akár N = 100.000 dominó kezelésére is fel kell készülnie. Egy dominót két 0 és 9 közötti számmal írhatunk le. Normális esetben ezt két bájtban tennénk meg, de így körülbelül 200 kilbájtot foglalna el a programunk. Tudjuk viszont, hogy ezeken a versenyeken a megoldások-programoknak általában 64 kilobájtba is be kell férniük. Próbálkozhatunk ügyesebb tárolással is: számoljuk össze, hogy hányféle dominó létezik: $10+\frac{10 \times 9}{2} = 55$, mert van $10$ darab dupla, a nem dupláknak pedig az egyik fele $10$ féle lehet, a másik pedig csak $9$, de így kétszer számoltuk az ilyeneket. Így ha minden dominóhoz egy 0 és 54 közti számot rendelünk, akkor a dominók tárolhatóak 5 biten, mert $2^5 = 64 > 54$. Így a 100,000 dominó egyidejű tárolásához elegendő 5 * 100.000 bit = 62.500 bájt. Ne feledjük, hogy ez egy nagyon bonyolult tárolási módszer. Ha így akarnánk tárolni a dominókat, akkor bitenkénti műveleteket kéne használnunk és írnunk kéne egy GetDomino(i) és egy SetDomino(i) függvényt külön arra, hogy az i-edik dominót lekérdezzük, vagy felírjuk! OKTV-n és Nemes Tihaméron legtöbbször létezni szokott ennél egyszerűbb megoldás is. Ez tehát valószínűleg egy olyan megoldás lesz, ami nem tárolja egyszerre a memóriában az összes dominót...
Egy "olyan" megoldás
Bevezető
A rekurzív és a feljegyzéses megoldás mindkettő olyan volt, hogy meg tudták állapítani a legjobb dominósort is. (A rekurzívban kicsit több paramétert kellene átadni, hogy a legalsó szinten is meglegyenek a hosszak, és ott egy maximumkiválasztást csinálni. A feljegyzésesben még többet kellene trükközni...) Maga a dominósor viszont nem kell a feladathoz, úgyhogy lehet remény sokkal egyszerűbb megoldásokra is.
Az algoritmus
Vegyünk fel egy képzeletbeli tömböt, ami az algoritmus lefutása utánn minden kezdés-végződés számkombinációhoz tárolni fogja a kirakható lehetséges leghosszabb, olyan kezdésű és végződésű dominósor hosszát. Pl. hosszak[1, 4] = hosszak[4, 1] a Mohó Marci dominóiból a szabályok szerint kirakható, leghosszabb 1-el kezdődő és 4-re végződő dominósor hossza. (Ha egy ilyen dominósort sem lehet kirakni, akkor legyen pl. hosszak[1, 4] = 0!) Ha egy ilyen tömböt fel tudnánk építeni, akkor ennek a legnagyobb eleme lenne a megoldás, és még a leghosszabb dominósor végein lévő pöttyök számát is meg tudnánk határozni.
A tömb felépítése: a dominókat sorban fogjuk beolvasni, és úgy építjük fel fokozatosan a tömböt. Kezdetben minden eleme nulla, utána pedig minden dominó beolvasása után az addig beolvasott dominók felhasználásával kirakható leghosszabb sorok hosszait fogja tárolni.
Az első dominó beolvasása után még csak egyetlen sorozatnál nem nulla a tömb. Ha a dominó pl. 5-6 alakú volt, akkor hosszak[5, 6] = 1. (És hosszak[6, 5]-nél is 1, de ezt mostantól nem fogjuk jelölni.) Ha a második dominó pl. 6-7 alakú, akkor a hosszak[5, 6] = 1 mellé bekerül egy hosszak[5, 7] = 2 is. És így tovább: az összes új dominót megpróbáljuk illeszteni a meglévő dominósorokhoz, és ha így új dominósor jönne létre, akkor azt bejegyezzük a tömbbe, eggyel nagyobb hosszal, mint az a sor, amiből létrehoztuk. Ha viszont már létezik ugyanolyan végű dominósor, mint ami létrejött, akkor az új és a régi közül a hosszabbat tartjuk meg és tesszük be a tömbbe.
Megvalósítás
A dominókat sorban olvasuk be, és mindig meghívunk egy Betesz(a, b) eljárást, ahol a-b a beolvasott dominó két száma. Az új dominó beillesztésénél arra kell figyelni, hogy lehetséges, hogy többféleképpen, több meglévő dominósorhoz is hozzá lehet majd illeszteni. Az is lehetséges, hogy egy már önmaga felhasználásával létrehozott sorhoz is hozzá lehetne még egyszer illeszteni. Ennek elkerülésére egy ujhossz[] tömböt fogunk használni: Betesz(a, b) eljárásnak a következő dolgokat kell csinálnia:
- Minden hosszt átmásol a hossz[] tömbből az ujhossz[] tömbbe.
- Megnézni, hogy hogyan lehet a hossz[]-ban tárolt sorokhoz hozzáilleszteni az adott dominót, és ha talál illeszkedést, akkor a létrejövő új sorok hosszait már az ujhossz[]-ban lévő hosszakkal veti össze, és oda is másolja be őket, ha nagyobbak.
- Miután minden lehetőséget végignézett, visszamásolja az ujhossz[] tömböt a hossz[] tömbbe.
Eljárás Betesz(a, b)
ujhossz := hossz;
Ciklus i := 0-tól 9-ig
Ha (hossz[a, i] > 0) és (hossz[a, i] + 1 > ujhossz[b, i]) Akkor
ujhossz[b, i] := hossz[a, i] + 1;
ujhossz[i, b] := hossz[a, i] + 1;
Elágazás Vége
Ciklus Vége
hossz := ujhossz;
Eljárás Vége
Ez a kódrészlet csak az a végével próbálja illeszteni a dominót. A b végével való illesztés is hasonló. A tömb olvasásánal kihasználjuk, hogy szimmetrikus, ezért az írásnál is figyelnünk kell rá, hogy ez a szimmetria fennmaradjon. Teljes tömböket nem minden nyelven lehet egymásnak értékül adni. Pascalban például csak akkor lehet, ha deklarálunk egy tömb típus és mindkét tömb olyan típusú. Ne felejtsük, hogy az első dominót külön kell berakni. Ha minden dominót feldolgoztunk, akkor már csak a maximális értéket kell megkeresni a hossz[] tömbben.
Megoldások
