19 Silmaring: Labürint

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

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

  • Üheteelise labürindi (ingl labyrinth) puhul pole eesmärk inimese eksitamine, vaid rändaja juhtimine ühe võimaliku tee kaudu. Selliseid keerdkäigustikke tuntakse juba tuhandeid aastaid, tavaliselt sümboliseerivad need (vaimset) rännakut. Eestiski leidub selline labürint Aegna saarel, kuid selle ehitamise aega täpselt ei teata (vt kivilabürint).
  • Hargneva labürindi (ingl maze) eesmärk on sinna sattunud külalist segadusse ajada ning erinevate võimalike teedega eksitada. Neid võib nimetada ka labürintmõistatusteks. Selliseid labürinte on rajatud üle maailma näiteks hekklabürintidena uhkematesse aedadesse. Kreeka mütoloogiast tuntud Minotauruse labürint on arvatavasti kuulsaim ehitis, kust pääsemine on äärmiselt keeruline.

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.

Suurim jääst labürint

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õrgus 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

Suurim hekklabürint

Maailma suurim hekklabürint asub Hiinas, Yanchengis. Labürindi pindala on 35 596,74 m² ja raja kogupikkus 9 457,36 m. Labürint koosneb suurest hirvelabürindist ja mitmest väiksemast labürindist (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 maisilabürint

Suurim maisipõllule rajatud labürint on 24,28 ha suurune. Selle lõi ettevõte Cool Patch Pumpkins ja rajatis asub California osariigis Dixonis.

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

Labürint meedias

Labürindi temaatikaga seoses on tehtud ka raamatuid ja filme. Näiteks 2014. aastal jõudis kinodesse “Labürindijooksja” (ingl The Maze Runner) esimene film, mis põhineb James Dashneri 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 2018. aastal film “Labürindijooksja: Surma ravim” (tõsi küll, labürintidega on neil järgedel üsna vähe seost).

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 tegemist on 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 tee 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. Tupikute täitmise algoritmi puhul vaadatakse kogu labürinti korraga ning eesmärgiks on

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

Selle meetodi mõistmiseks vaata 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 vaata selgitavat videot:

Millist algoritmi kasutaksid, kui satuksid labürinti?

Ülesanne

Labürindis liikumist saab harjutada näiteks Blockly: Maze programmeerimismä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

  1. http://www.labyrinthos.net
  2. http://en.wikipedia.org/wiki/Maze_solving_algorithm
  3. http://www.guinnessworldrecords.com/world-records/4000/largest-maze-ice-maze
  4. http://www.guinnessworldrecords.com/world-records/1/largest-maze-permanent-hedge-maze
  5. http://www.guinnessworldrecords.com/world-records/1000/largest-maze-temporary-corn-crop-maze

Litsents

Icon for the Creative Commons Attribution 4.0 International License

Programmeerimine on loodud Eno Tõnisson, Tauno Palts, Merilin Säde, Kaarel Tõnisson jt poolt Creative Commons Attribution 4.0 International License litsentsi alusel, kui pole teisiti märgitud.

Jaga seda raamatut