Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2004-2005‎ > ‎

7. óra - Útvesztő-generálás 2.


Előzmények

A 6. órán elkezdett útvesztőgeneráló programot folytattuk.

Az algoritmus megvalósítá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.

{ennyi él típusú mező van összesen, számolj utána:}
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-1/31≈0.97. Annak a valószínűsége, hogy a második körben sem, már: 0.972≈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.97n. 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. limn→∞10.97n=∞

Hatékonyabb(?) módszerek

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; {1..maradek}
  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
        szamlalo := szamlalo + 1;
        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íthatunk 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
    {függőleges típusú}
    map[sor, oszlop]:= Hamis;
    map[sor, oszlop]:=
        Nem Ut(sor-1, oszlop, sor+1, oszlop);
  Különben
    {vízszintes típusú}
    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.

Megvalósítások

Fehér Gábor (Pascal): fg_utv.pas
Fehér Gábor (Pascal): fg_utv2.pas
A második random módszert használja, de nem tűnik gyorsabbnak.
Tihanyi Balázs (Visual Basic.NET): tb_utv.vb
Mészáros Balázs (C): mb_utv.c
Fejér Attila (Delphi): fa_utv.dpr
ċ
fa_utv.dpr
(3k)
Gábor Fehér,
2012. jún. 24. 7:17
ċ
fg_utv.pas
(3k)
Gábor Fehér,
2012. jún. 24. 7:17
ċ
fg_utv2.pas
(3k)
Gábor Fehér,
2012. jún. 24. 7:17
ċ
mb_utv.c
(2k)
Gábor Fehér,
2012. jún. 24. 7:17
ċ
tb_utv.vb_
(3k)
Gábor Fehér,
2012. jún. 24. 7:17
Comments