MOOC Programmeerimise alused - Kursused

3.5 Labürint

MIS ON LABÜRINT?

Labürindiks nimetatakse keerdkäikudega ehitist ehk keerdkäigustikku (vt ÕS 2013) ning sõna labürint tuleneb kreekakeelsest sõnast labyrinthos.

Sageli jagatakse labürindid kahte erinevasse liiki, mis erinevad teineteisest läbitavuse poolest.

Leidub labürinte (ingl labyrinth), mille puhul pole eesmärgiks inimese eksitamine, vaid rändaja juhtimine ühe võimaliku tee kaudu. Selliseid keerdkäigustikke tuntakse juba tuhandeid aastaid. Eestiski leidub selline labürint Aegna saarel, mille ehitamise aega täpselt ei teata (vt kivilabürint).
Samas on rajatud labürinte (ingl maze), mille eesmärgiks on sinna sattunud külalist segadusse ajada erinevate võimalike teedega. Neid võib nimetada ka labürintmõistatusteks ning üle maailma on neid rajatud hekklabürintidena näiteks aedadesse. Ka Kreeka mütoloogias esinev Minotauruse labürint on mõeldud selleks, et sinna sattunud inimene eksiks ja ei leiaks väljapääsu.

Meie keskendumegi niisugustele labürintidele, mis püüavad inimesi eksitada.

MAAILMA SUURIMAD

Labürinte on tekitatud erinevat moodi. Näiteks on neid ehitatud jääst, kasvatatud hekina ja rajatud maisipõllule. Tutvustame mõnda rekordilist labürinti.

Maailma suurim jääst valmistatud labürint tehti Buffalos, USAs Buffalo Powder Keg festivali raames 26. veebruaril 2010. aastal. Labürindi pindala oli 1194,33 m², laius 25,85 m ja pikkus 46,21 m. Müüride kõrguseks oli 1,83 m ning selle ehitamiseks kulus 2171 jääplokki, kusjuures üks plokk kaalus 136 kg.

Allikas: http://www.guinnessworldrecords.com/world-records/4000/largest-maze-ice-maze

Maailma suurim hekklabürint asub Hiinas, Yanchengis. Labürindi pindala on 35 596,74 m² ja raja kogupikkus on 9 457,36 m. Labürint koosneb suurest hirvelabürindist ja mitmetest väiksematest labürintidest (südamekujuline labürint, 2 ringikujulist labürinti ja lastepargi labürint).

Allikas: http://www.guinnessworldrecords.com/world-records/1/largest-maze-permanent-hedge-maze

Suurim maisipõllule rajatud labürint on 24,28 ha suurune. See loodi ettevõtte Cool Patch Pumpkins poolt ja asub California osariigis Dixonis.

Allikas: http://www.guinnessworldrecords.com/world-records/1000/largest-maze-temporary-corn-crop-maze

Labürindi teematikaga seoses on tehtud ka filme. Näiteks 2014. aastal jõudis kinodesse “Labürindijooksja” (ingl The Maze Runner) esimene film, mis põhineb James Dashneri poolt kirjutatud samanimelisel ulmetriloogial. Filmis satub mälukaotusega poiss Thomas suurde labürinti, kust koos teiste saatusekaaslastega väljapääsu otsima hakkab. Filmi kohta saab täpsemalt uurida siit ning vaadata filmi treilerit:

2015. aastal valmis triloogia teine film "Labürindijooksja: Põlenu katsed" ja järgmise aasta alguses jõuab kinodesse kolmas film "Labürindijooksja: Surma ravim".

LABÜRINDIST PÄÄSEMINE

Labürint kui ehitis pole otseselt seotud programmeerimisega, kuigi labürinti saab arvuti abil planeerida. Selliseid generaatoreid on veebiski.

Suuremat huvi pakuvad aga keerdkäigustikust väljapääsemise ülesanded, sest nende lahendused on algoritmilised. Järgmisena tutvustatakse mõnda lahenduseeskirja, mis aitavad eksinud ränduril leida keerulisest labürindist pääsetee.

Hiire algoritm

Üks lihtsamaid algoritme, mida saab väljapääsu leidmiseks kasutada, on juhuslik hiire algoritm (ingl Random mouse algorithm). Nagu selle nimigi ütleb, siis tegemist on viisiga, kuidas hiir otsiks labürindist väljapääsu. Selle põhimõtteks on liikuda labürindis otse seinani ning seejärel pöörata suvalisse suunda ja liikuda taas otse seinani. Seesugust tegevust korratakse kuni väljapääsu leidmiseni. Teisisõnu on idee selles, et uidatakse keerdkäigustikus ringi kuni avastatakse väljapääs. Tegelikult on siin tegemist tsüklilise käitumismustriga. Igal tsükli sammul minnakse otse seinani ja siis pööratakse suvalisse suunda. Selle algoritmi nõrkuseks on see, et sageli kulub palju aega enne väljapääsu leidmist, eriti kui on tegemist väga suure labürindiga.

Seinajärgija algoritm

Teine lihtne võimalus, kuidas labürinti läbida, on kasutada seinajärgija algoritmi. Esmalt tuleb valida parem või vasak käsi ja hoida see käsi pidevas kontaktis labürindi seinaga väljapääsu leidmiseni.

Allikas: https://en.wikipedia.org/wiki/Maze_solving_algorithm#/media/File:Maze01-02.png

Selline algoritm aga ei tööta, kui algus- ja lõpp-punkt pole omavahel seinapidi ühendatud.

Tupikute täitmise algoritm

Leidub labürindi lahendusalgoritme, mis ei aita tundmatus keerdkäigustikus teed kaotanud inimesel pääseda, sest tal pole ülevaadet kogu labürindist. Küll aga võimaldavad need leida tee, kui kogu labürindi kaart on ees. Näiteks võib selleks luua vastava programmi. Tupikute täitmise algoritmi puhul vaadatakse kogu labürinti korraga ning eesmärgiks on

leida kõik tupikud,
arvata kogu tee tupikust esimese ristmikuni kaardilt välja.

Selle meetodi mõistmiseks vaadake järgmist videot.

Trémaux’ algoritm

Algoritm on saanud oma nime selle looja Charles Pierre Trémaux’ järgi, kes oli 19. sajandi prantsuse matemaatik. Tema algoritmi põhimõte on selles, et labürindi lahendamiseks peab eksinud rändur läbitud tee märkimiseks joonistama enda järele joone. Juhul, kui satutakse tupikusse, siis pööratakse ümber ja minnakse tuldud teed tagasi. Kui leitakse ristmik, kus varem käidud pole, siis valitakse suvaline suund (kust ei tuldud) ning jätkatakse teed. Kui kõnnitakse mööda teed, mida on juba külastatud (näiteks on üks kord joonega märgitud) ja satutakse ristmikule, siis valitakse uus tee, kui see on saadaval (pole joonega märgitud), ning minnakse mööda seda teed. Vastasel juhul minnakse mööda vana teed, mis oli ühel korral märgitud. Kõik teed on kas märkimata, märgitud üks kord (käidud on seda teed vaid üks kord) või märgitud kaks korda, mis tähendab seda, et seda mööda on käidud ja siis tagasi tuldud. Lõpptulemusena saadakse ühe joonega märgitud tee, mis ühendab algust ja lõppu. Algoritmi paremaks mõistmiseks vaadake selgitavat videot:

Millist algoritmi kasutaksite, kui satuksite labürinti?

Ülesanne

Labürindis liikumist saab harjutada näiteks Blockly: Maze mängu abil.

Edasijõudnutele

Need, kelle jaoks on tsükkel ja moodulite importimine selged ja soovivad oma programmerimisoskusi proovile panna, võiksid uurida lisamaterjali “Pykkar”, kus saab luua ise labürindi ning kirjutada programmi, mis selle lahendab.

ALLIKAD

< eelmine

3. nädala sisukord

järgmine >

MOOC Programmeerimise alused 2018/19 sügis