Wilson sika Algorithm Maze Generator

I-algorithm kaWilson iyindlela yokuhamba okungahleliwe ye-loop-erased ekhiqiza iyunifomu ehlanganisa imithi yokudalelwa kwe-maze. Lokhu kusho ukuthi wonke ama-mazes angenzeka osayizi onikeziwe ngokulinganayo kungenzeka ukuthi akhiqizwe, okwenza kube inqubo yesizukulwane se-maze engakhethi. I-algorithm kaWilson ingabhekwa njengenguqulo ethuthukisiwe ye-algorithm ye-Aldous-Broder, njengoba ikhiqiza ama-mazes anezici ezifanayo, kodwa igijima ngokushesha okukhulu, ngakho-ke angizange ngizihluphe ngokusebenzisa i-algorithm ye-Aldous-Broder lapha.

I-maze ephelele i-maze lapho kukhona indlela eyodwa ncamashi ukusuka kunoma iyiphi indawo ku-maze ukuya kunoma iyiphi enye indawo. Lokho kusho ukuthi ngeke ugcine usuzungeza emibuthanweni, kodwa uzohlangana nezinto ezifile, okuphoqa ukuthi ujike uphinde ubuyele emuva.

Amamephu we-maze akhiqizwe lapha afaka inguqulo ezenzakalelayo ngaphandle kwanoma yiziphi izindawo zokuqala nokuqeda, ukuze ukwazi ukuzinqumela lokho: kuzoba nesixazululo kusuka kunoma iyiphi indawo ku-maze kuya kunoma iyiphi enye indawo. Uma ufuna ugqozi, ungavumela indawo yokuqala neyokuqeda ephakanyisiwe - futhi ubone ngisho nesixazululo phakathi kwakho kokubili.

Mayelana ne-Algorithm kaWilson

I-algorithm kaWilson yokukhiqiza iyunifomu ehlanganisa imithi esebenzisa udonga olungahleliwe lwe-loop-erased yadalwa nguDavid Bruce Wilson.

Wilson ekuqaleni wethula le algorithm ngo-1996 ngenkathi ucwaninga okungahleliwe spanning imithi kanye Markov amaketanga e amathuba theory. Nakuba umsebenzi wakhe ngokuyinhloko kwizibalo kanye ne-physics yezibalo, i-algorithm kusukela ngaleso sikhathi yamukelwa kabanzi isizukulwane se-maze ngenxa yekhono layo lokukhiqiza ama-mazes afanayo ngokuphelele.

I-Algorithm kaWilson isebenza kanjani kuMaze Generation

I-algorithm kaWilson iqinisekisa ukuthi i-maze yokugcina ixhunywe ngokugcwele ngaphandle kwama-loops ngokuphindaphinda ukuqopha izindlela ezivela kumaseli angafakwanga usebenzisa ukuhamba okungahleliwe.

Isinyathelo 1: Qalisa

• Qala ngegridi egcwele izindonga.
• Chaza uhlu lwawo wonke amaseli okudlula okungenzeka.

Isinyathelo 2: Khetha i-Random Starting Cell

• Khetha noma yiliphi iseli elingahleliwe bese uliphawula njengoba livakashelwe. Lokhu kusebenza njengesiqalo se-maze ngesikhathi sesizukulwane.

Isinyathelo 3: Ukuhamba okungahleliwe nge-Loop-Erasing

• Khetha iseli elingafakwanga bese uqala ukuhamba okungahleliwe (ukuhamba ngezindlela ezingahleliwe).
• Uma ukuhamba kufinyelela esitokisini esivele sivakashelwe, sula noma yimaphi ama-loops endleleni.
• Uma ukuhamba kuxhuma esifundeni esivakashelwe, phawula wonke amaseli endleleni njengoba evakashelwe.

Isinyathelo 4: Phinda Kuze Kube Yilapho Wonke Amaseli Evakashelwa:

• Qhubeka nokukhetha amaseli angafakwanga futhi wenze ukuhamba okungahleliwe kuze kube yilapho wonke amaseli ayingxenye ye-maze.