Jenereta ya Maze ya Backtracker ya Kujirudia

Algorithm ya kurudia ya backtracker ni kweli lengo la jumla la utafutaji wa kwanza. Wakati kutumika kwa ajili ya kizazi maze, ni kidogo iliyopita kuchukua njia katika random, wakati kama kutumika kwa madhumuni halisi ya utafutaji, moja ingekuwa kawaida tu kutafuta kila ngazi katika utaratibu linear. Inaelekea kuzalisha mazes na barabara ndefu, za upepo na suluhisho la muda mrefu sana, linalozunguka.

Maze kamili ni maze ambayo kuna njia moja kutoka kwa hatua yoyote kwenye maze hadi hatua nyingine yoyote. Hiyo ina maana kwamba huwezi kuishia kuzunguka kwenye miduara, lakini mara nyingi utakutana na ncha zisizokufa, na kukulazimisha kugeuka na kurudi nyuma.

Ramani za mlolongo zinazozalishwa hapa ni pamoja na toleo chaguo-msingi bila nafasi zozote za kuanza na kumaliza, kwa hivyo unaweza kujiamulia hizo: kutakuwa na suluhu kutoka sehemu yoyote kwenye msururu hadi sehemu nyingine yoyote. Ikiwa unataka msukumo, unaweza kuwezesha nafasi iliyopendekezwa ya kuanza na kumaliza - na hata kuona suluhisho kati ya hizo mbili.

Algorithm ya kurudia ya backtracker ni njia ya kwanza ya utafutaji ya kuzalisha mazes kamili (mazes bila kitanzi na njia moja kati ya pointi mbili). Ni rahisi, yenye ufanisi, na hutoa mazes ya kuvutia ya kuona na barabara ndefu, za upepo.

Licha ya jina lake, sio lazima itekelezwe kwa kutumia kurudia. Mara nyingi hutekelezwa kwa njia ya iterative kwa kutumia foleni ya LIFO (yaani stack). Kwa mazes kubwa sana, kutumia kurudia kuna uwezekano mkubwa wa kusababisha mpororo wa simu, kulingana na lugha ya programu na kumbukumbu inayopatikana. Foleni ya LIFO inaweza kubadilishwa kwa urahisi zaidi kushughulikia kiasi kikubwa cha data, hata kuweka foleni kwenye diski au kwenye hifadhidata ikiwa kumbukumbu inayopatikana haitoshi.

Jinsi inavyofanya kazi

Algorithm inafanya kazi kwa kutumia njia ya utafutaji wa kina wa msingi. Hapa kuna kuvunjika kwa hatua kwa hatua:

1. Chagua seli ya kuanzia na uweke alama kama ilivyotembelewa.
2. Wakati kuna seli zisizotembelewa:
   • Angalia seli za jirani ambazo bado hazijatembelewa.
   • Ikiwa angalau jirani mmoja ambaye hajatembelewa yupo:
     • Chagua moja ya majirani wasiotembelewa.
     • Ondoa ukuta kati ya seli ya sasa na jirani aliyechaguliwa.
     • Nenda kwa jirani aliyechaguliwa na uweke alama kama ilivyotembelewa.
     • Bonyeza seli ya sasa kwenye stack.
   • Ikiwa hakuna majirani ambao hawajatembelewa wapo:
     • Backtrack kwa popping seli ya mwisho kutoka stack.
3. Endelea na mchakato huu mpaka mpororo uwe tupu.

Ukweli wa kuvutia juu ya algorithm hii ni kwamba inafanya kazi kama jenereta ya maze na kama kisuluhishi cha maze. Ikiwa unaiendesha kwenye maze iliyozalishwa tayari na kuacha tu unapogonga hatua ya mwisho iliyoamuliwa, stack itakuwa na suluhisho la maze.

Kwa kweli nina matoleo mawili ya algorithm hii katika kucheza kwenye tovuti hii: foleni ya LIFO kulingana na moja ya kuzalisha mazes kwenye ukurasa huu na moja ya kurudia kwa kutatua mazes, pia mazes zinazozalishwa na algorithms nyingine (ndio jinsi ramani na suluhisho zinafanywa). Kuwa na matoleo mawili tofauti ni kwa ajili ya michezo kwa sababu mimi ni nerd ambaye anaona ni ya kuvutia, ama inaweza kuwa kazi kwa wote ;-)