Endurkvæmur Backtracker Maze Generator

Endurkvæmi baksporsreikniritið er í raun almenn dýpt-fyrsta leit. Þegar það er notað til að búa til völundarhús, breyttist það örlítið til að velja slóðina af handahófi, en ef það er notað í raunverulegum leitartilgangi myndi maður venjulega bara leita á hverju stigi í línulegri röð. Það hefur tilhneigingu til að framleiða völundarhús með löngum, hlykkjóttum göngum og mjög langri, snúningslausn.

Fullkomið völundarhús er völundarhús þar sem það er nákvæmlega ein leið frá hvaða stað sem er í völundarhúsinu til annars staðar. Það þýðir að þú getur ekki endað á því að fara í hringi, en þú munt oft lenda í blindgötum, sem neyðir þig til að snúa við og fara til baka.

Völundarkortin sem mynduð eru hér innihalda sjálfgefna útgáfu án upphafs- og lokastaða, svo þú getur ákveðið þær sjálfur: það verður lausn frá hvaða stað sem er í völundarhúsinu til hvers annars. Ef þú vilt innblástur geturðu virkjað tillögu um upphafs- og lokastöðu - og jafnvel séð lausnina á milli þeirra tveggja.

Rekursífur bakútfærslualgoritmi er aðferð við leit í dýpt til að búa til fullkomna villur (villur án lykkja og með einum leið frá einum punkti til annars). Það er einfalt, árangursríkt og framleiðir sjónrænt fallega villur með löngum, vafinn göngum.

Þrátt fyrir nafnið þarf það ekki endilega að vera útfært með því að nota endurheimt. Það er oft útfært með endurteknum aðferðum með því að nota LIFO röð (þ.e. stakk). Fyrir mjög stórar villur er líklegra að endurheimt leiði til offlæðis í köllunarstafli, allt eftir forritunarmáli og tiltækri minni. LIFO röð er auðveldari til að aðlaga við að meðhöndla mikla gagnaflutninga, jafnvel með því að geyma röðina á disk eða í gagnagrunni ef tiltækt minni er ófullnægjandi.

Hvernig það virkar

Algoritminn virkar með því að nota stakk-bundna leit í dýpt aðferð. Hér er uppbygging skref fyrir skref:

1. Veldu upphafsfrumu og merktu það sem heimsótt.
2. Á meðan það eru óheimsóttar frumur:
   • Skoðaðu nágrannafrumur sem hafa ekki verið heimsóttar enn.
   • Ef að minnsta kosti ein óheimsótt nágranna er til:
     • Veldu handahófskennt einn af óheimsóttu nágrönnum.
     • Fjarlægðu vegginn á milli núverandi frumunnar og valda nágranna.
     • Færðu þig til valda nágranna og merktu það sem heimsótt.
     • Settu núverandi frumu á stakkinn.
   • Ef engir óheimsóttir nágrannar eru til:
     • Farðu aftur til baka með því að taka síðustu frumuna úr stakkinum.
3. Halda áfram þessari ferli þar til stakkurinn er tómur.

Áhugaverður staðreynd um þennan algoritma er að hann virkar bæði sem villubúandi og sem lausnari fyrir villur. Ef þú keyrir hann á þegar búinni villu og stoppar bara þegar þú kemst að ákveðnum enda, þá mun stakkurinn innihalda lausnina fyrir villuna.

Ég hef í raun tvær útgáfur af þessum algoritma í notkun á þessari síðu: eina sem byggir á LIFO röð til að búa til villur á þessari síðu og eina sem byggir á endurheimt til að leysa villur, líka villur sem eru búnar til með öðrum algoritma (þetta er hvernig kortin með lausnunum eru gerð). Að hafa tvær mismunandi útgáfur er bara fyrir íþróttir vegna þess að ég er tölvunarfræðingur sem finnst það áhugavert, hvor sem væri hefði getað virkað fyrir báðar ;-)