7. óra
Előzmények
Az algoritmus leprogramozása
Az útvesztőt a már megbeszélt, négyzetrácsos, N-szer M-es pályán fogjuk elkészíteni. (N, M: páratlan) Ezt is egy map[sor, oszlop], logikai értékeket tartalmazó tömbben fogjuk tárolni, és a falakból álló keretet is fel fogjuk hozzá venni. Megbeszéltük, hogy bizonyos mezők biztosan falak lesznek. A következő ábráról leolvasható, hogy ezek pontosan azok, amiknek mindkét koordinátájuk páros.
Az algoritmus alaplépése, azaz az élek kitörlése itt az él típusú mezők befalazását fogja jelenteni. Kétféle él típusú mező létezik: a "függőlegesre" péda a zöld "a", a "vízszintesre" pedig a zöld "b". Mindkettőnél majd azt fogjuk vizsgálni, hogy ha befalaznánk, akkor maradna-e más út a szomszédos mezői között, de a "függőlegeseknél" ezek az alatta és fölötte lévők, a "vízszinteseknél" pedig a mellette lévők. Az él típusú mezőknek mindig pontosan az egyik koordinátája lesz páros. Azt, hogy vízszintes, vagy függőleges-e az adott mező, eldönthetjük például az alapján, hogy melyik koordinátája a páros.
Előkészítés
Először beállítjuk a térképet, hogy a megfelelő helyen falak legyenek.
Eljárás Feltolt()
Ciklus sor:= 0-től N+1-ig
Ciklus oszlop:= 0-től M+1-ig
map[sor, oszlop]:= Nem
((sor = 0) vagy (sor = N+1) vagy
(oszlop = 0) vagy (oszlop = M+1) vagy
((sor Modulo 2 = 0) és
(oszlop Modulo 2 = 0)));
Ciklus vége
Ciklus vége
Eljárás vége
A Nem logikai tagadást jelöl.
Véletlenszerű sorrend
Az előkészítése után véletlenszerű sorrendben végig kell venni az él típusú mezőket.
Erre az a legegyszerűbb módszer, hogy véletlenszerűen sorban generáljuk az él-koordinátákat,
és ha olyan él-mező koordinátáját kaptuk, ami még nem volt, akkor elvégezzük rá az
algoritmus műveletét, és feljegyezzük, hogy ez a mező már volt. Azt, hogy mely élek
voltak már, egy volt[sor, oszlop], tömbben tároljuk, aminek kezdetben minden eleme
Hamis, és csak az él-típusú mezőket fogjuk figyelni.
osszes:= N * M / 2 - 1
voltmar:= 0;
Ciklus Amíg (voltmar < osszes)
VEl(sor, oszlop);
Ha (volt[sor, oszlop] = Hamis) Akkor
Kezel(sor, oszlop);
volt[sor, oszlop]:= Igaz;
voltmar:= voltmar + 1;
Elágazás vége
Ciklus Vége
A VEl(sor, oszlop) egy véletlenszerűen kisorsolt él mező koordinátáit adja vissza. A
Kezel(sor, oszlop) dönti el, hogy befalazzuk-e az adott élet, és be is falazza, ha kell. (Ezt majd később írjuk meg.) A legegyszerűbb VEl() függvény:
Eljárás VEl(max)
sor:= 0; oszlop:= 0;
Ciklus Amíg ((sor Modulo 2) +
(oszlop Modulo 2) <> 1)
sor:= Veletlen(N)+1;
oszlop:= Veletlen(M)+1;
Ciklus vége
Eljárás vége
A Veletlen(k) függvény egy 0 és k-1 közti véletlenszerű egész számot sorsol ki. A ciklus feltétele azt ellenőrzi, hogy a sor és az oszlop közül pontosan az egyik
legyen páros.
Mindkét kódrészletben azt a módszert alkalmaztuk, hogy addig kértünk újabb véletlenszámokat, míg azok valamilyen feltételnek meg nem feleltek. Ez a módszer 1 valószínűséggel lefut véges idő alatt, viszont nem hatékony. Mivel nagyon egyszerű leprogramozni, általában érdemes mindig megpróbálkozni vele. Így ugyanis kevesebb hibalehetőség lesz a programunkban, mint egy hatékonyabb de bonyolultabb algoritmus esetén. A végén pedig még mindig lecserélhetjük, ha már kész a program, de túl lassú.
A következő két fejezet nem szűkséges a program elkészítéséhez.
Szemléltetés
A pályán 31 darab él-mező van. Annak a valószínűsége, hogy az első körben nem pl. a (4, 2)-es koordinátájú mező jön ki: $1-\frac{1}{31} \approx 0.97$. Annak a valószínűsége, hogy a második körben sem, már: $0.97^2 \approx 0.94$. Így annak a valószínűsége, hogy az n. körben még nem jött ki ez az él-mező: $0.97^n$. Ha n elég nagy, akkor ez már egy elhanyagolhatóan kis szám, pl. n = 670 esetén a valószínűség $0.000000001$ körüli. A többi mezőre is ugyanez a valószínűség igaz, tehát annak a valószínűsége, hogy még van egy mező, ami nem jött ki, az ennek nem több, mint a 31-szerese. Tehát a 670. lépés után kb. $0.000000031$ valószínűséggel nem lesz kész a program. Ezért átlagosan kb. minden 28,000,000 futtatásból 1-szer nem lesz kész a program a 670. lépésre. (A 28 millió a valószínűség reciproka.) Ilyenkor megkérhetjük a felhasználót, hogy futtassa le újra. :-) De még ennél is jobb a helyzet, ugyanis ahogy növeljük a lépések számát, a futtatások száma, amelyekben befejeződik az utolsó lépésre, a végtelenbe tart. $\lim_{n \to \infty}{\frac{1}{0.97^n}} = \infty $
Hatékonyabb(?) módszerek
Első módszer: Tudjuk, hogy pl. 31 él típusú mező van, tehát először választunk egy x véletlenszámot 1 és 31 között: az első kisorsolt él-mező az x-edik lesz. (Pl. fentről lefelé, balról jobbra kiszámoljuk) Ezután már 30 él-mező van csak, így sorsolunk egy másik x számot 1 és 30 között: most is az x-edik él-mező lesz a választott, de természetesen az eddig még nem választott él-mezők közül az x-edik. (a kiszámolásnál most átugorjuk a már kisorsolt él-mezőket...) És így tovább, mindig eggyel kisebb intervallumból sorsolunk számot, és a már régebben kisorsolt él-mezőket mindig átugorjuk. A példa főprogram:
osszes:= N * M / 2 - 1;
Ciklus maradek:= osszes-től 1-ig
x:= Veletlen(maradek)+1;
szamlalo:= 0;
Ciklus sor:= 1-től N-ig
Ciklus oszlop:= 1-től M-ig
Ha (sor Modulo 2 + oszlop Modulo 2 = 1) és
(volt[sor, oszlop] = Hamis) Akkor
INC(szamlalo);
Ha szamlalo = x Akkor
volt[sor, oszlop]:= Igaz;
Kezel(sor, oszlop);
Elágazás vége
Elágazás vége
Ciklus vége
Ciklus vége
Ciklus vége
Tovább gyorsíthatun ezen a módszeren, ha kilépünk a belső számláló ciklusokból, amint megtaláltuk az x-edik él-mezőt. Néhány mérés alapján mégsem tűnik sokkal gyorsabbnak az előző módszernél, még ha "okosabb" is nála. Lehet, hogy azért nem gyorsabb, mert túl sokat pörög a két for ciklus, és a tömböt is sokat olvassa. Más ötlet?
Befalazás
A Kezel(sor, oszlop) eljárás:
Eljárás Kezel(sor, oszlop)
Ha (sor Modulo 2 = 0) Akkor
map[sor, oszlop]:= Hamis;
map[sor, oszlop]:=
Nem Ut(sor-1, oszlop, sor+1, oszlop);
Különben
map[sor, oszlop]:= Hamis;
map[sor, oszlop]:=
Nem Ut(sor, oszlop-1, sor, oszlop+1);
Elágazás vége
Eljárás vége
Az Ut() az előző órán megírt függvény. Mindkét élmező-típusnál először elfalazzuk az élet, majd, ha van más út a két szomszédja között, akkor Hamis értéket (tehát falat) állítunk be, ha pedig nincs más út, akkor Igaz értéket (tehát átjárható mezőt) állítunk be.
Megoldások
