Jenereta ya Maze ya Backtracker ya Kujirudia

Algoritimu ya kurudia ya kifuatiliaji nyuma ni utafutaji wa kina wa madhumuni ya jumla. Inapotumika kwa ajili ya uzalishaji wa maze, ilibadilishwa kidogo ili kuchagua njia bila mpangilio, ilhali ikitumika kwa madhumuni halisi ya utafutaji, mtu kwa kawaida angetafuta kila ngazi kwa mpangilio wa mstari. Huelekea kutoa maze yenye korido ndefu, zinazopinda na suluhisho refu sana, linalopinda.

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.

Algoritimu ya kurudia ya kifuatiliaji cha nyuma ni mbinu ya utafutaji wa kina wa kwanza kwa ajili ya kutengeneza mazes kamilifu (mazes zisizo na mizunguko na njia moja kati ya sehemu mbili). Ni rahisi, yenye ufanisi, na hutoa mazes nyeti zenye kuvutia zenye korido ndefu na zenye kupinda.

Licha ya jina lake, si lazima litekelezwe kwa kutumia urudiaji. Mara nyingi hutekelezwa kwa mbinu ya kurudiaji kwa kutumia foleni ya LIFO (yaani mrundikano). Kwa maze makubwa sana, kutumia urudiaji kuna uwezekano mkubwa wa kusababisha kufurika kwa mrundikano wa simu, kulingana na lugha ya programu na kumbukumbu inayopatikana. Foleni ya LIFO inaweza kubadilishwa kwa urahisi zaidi ili kushughulikia kiasi kikubwa cha data, hata kuweka foleni kwenye diski au kwenye hifadhidata ikiwa kumbukumbu inayopatikana haitoshi.

Jinsi Inavyofanya Kazi

Algoritimu hufanya kazi kwa kutumia mbinu ya utafutaji wa kina-kwanza inayotegemea mrundiko. Hapa kuna uchanganuzi wa hatua kwa hatua:

1. Chagua seli ya kuanzia na uweke alama kama iliyotembelewa.
2. Ingawa kuna seli ambazo hazijatembelewa: Angalia seli jirani ambazo hazijatembelewa bado. Ikiwa angalau jirani mmoja ambaye hajatembelewa yupo: Chagua bila mpangilio mmoja wa majirani ambao hawajatembelewa. Ondoa ukuta kati ya seli ya sasa na jirani aliyechaguliwa. Sogeza hadi kwa jirani aliyechaguliwa na uweke alama kama aliyetembelewa. Sukuma seli ya sasa kwenye rundo. Ikiwa hakuna majirani ambao hawajatembelewa: Rudi nyuma kwa kutoa seli ya mwisho kutoka kwenye rundo.
3. Endelea na mchakato huu hadi mrundikano uwe tupu.

Ukweli wa kuvutia kuhusu algoriti hii ni kwamba inafanya kazi kama jenereta ya maze na kama kitatuzi cha maze. Ukiiendesha kwenye maze iliyotengenezwa tayari na ukasimama tu unapofikia mwisho uliopangwa, rundo litakuwa na suluhisho la maze.

Kwa kweli nina matoleo mawili ya algoriti hii yanayotumika kwenye tovuti hii: moja ya foleni ya LIFO inayotokana na kutengeneza maze kwenye ukurasa huu na moja inayotokana na kujirudia kwa ajili ya kutatua maze, pia maze yanayotokana na algoriti zingine (hivyo ndivyo ramani zenye suluhisho zinavyotengenezwa). Kuwa na matoleo mawili tofauti ni kwa ajili ya michezo tu kwa sababu mimi ni msomi ambaye ninaona inavutia, yoyote yangeweza kufanya kazi kwa yote mawili ;-)

Kusoma Zaidi

Ikiwa ulifurahia chapisho hili, unaweza pia kupenda mapendekezo haya:

• Jenereta ya Maze ya Algorithm ya Eller
• Kuongezeka kwa Jenereta ya Maze ya Algorithm ya Miti
• Jenereta ya Maze ya Algorithm ya Kruskal