Isibali sekhodi sehashi Eller's Algorithm Maze Generator

I-algorithm ka-Eller iyi-algorithm yesizukulwane se-maze ekhiqiza ngempumelelo ama-mazes aphelele (ama-maze angenalo amaluphu kanye nendlela eyodwa phakathi kwanoma yimaphi amaphuzu amabili) kusetshenziswa indlela yomugqa ngomugqa. Ikhiqiza ama-maze afana ne-algorithm ye-Kruskal, kodwa ikwenza lokho ngokukhiqiza umugqa owodwa ngesikhathi, ngaphandle kwesidingo sokugcina yonke inqolobane enkumbulweni. Lokho kukwenza kube usizo ekukhiqizeni ama-maze amakhulu kakhulu kumasistimu akhawulelwe kakhulu nasekukhiqizeni okuqukethwe kwenqubo.

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-Eller's Algorithm

I-Algorithm ka-Eller yethulwa nguDavid Eller.

I-algorithm iphawuleka ngendlela yayo ephumelelayo yomugqa ngomugqa ekwenzeni i-maze, iyenze ilungele ama-maze angapheli noma ama-maze akhiqizwa ngesikhathi sangempela. Kuvame ukucashunwa ekukhiqizeni okuqukethwe kwenqubo kanye nemibhalo yesizukulwane se-maze, kodwa angikwazanga ukuthola imithombo eyinhloko echaza ukushicilelwa kwayo koqobo.

Isebenza kanjani i-algorithm ye-Eller ku-Maze Generation

I-algorithm ka-Eller icubungula umugqa owodwa ngesikhathi, igcina futhi ilungisa amasethi amaseli axhunyiwe. Iqinisekisa ukuxhumana ngenkathi igwema izihibe, futhi inweba kahle i-maze iye phansi.

Ngokwethiyori ingasetshenziswa ukukhiqiza ama-maze angapheli, kodwa ukuze kuqinisekiswe ukuthi i-maze ekhiqiziwe iyaxazululeka, kuyadingeka ukushintshela kumqondo "womugqa wokugcina" ngesikhathi esithile ukuze uqedele imaze.

Isinyathelo 1: Qalisa Umugqa Wokuqala

• Nikeza iseli ngalinye emugqeni isethi eyingqayizivele ye-ID.

Isinyathelo sesi-2: Joyina Amanye Amaseli Aseduze Ngokuvundlile

• Hlanganisa amaseli aseduze ngokungahleliwe ngokuwabeka kusethi efanayo ye-ID. Lokhu kuqinisekisa ukuthi kukhona amaphaseji avundlile.

Isinyathelo sesi-3: Dala Ukuxhumana Okuqondile Kumugqa Olandelayo

• Kusethi ngayinye evela kumugqa, okungenani iseli eyodwa kufanele ixhume phansi (ukuqinisekisa ukuxhumana).
• Khetha ngokungahleliwe iseli elilodwa noma amaningi kusethi ngayinye ukuze uxhume kumugqa olandelayo.

Isinyathelo sesi-4: Hambisa kumugqa olandelayo

• Dlulisa phambili ukuxhumana okuqondile ngokunikeza isethi ye-ID efanayo kumaseli ahambisanayo angezansi.
• Yabela amasethi amasha ama-ID kunoma imaphi amaseli angabelwe.

Isinyathelo sesi-5: Phinda Izinyathelo 2–4 Kuze Kufinyelelwe Umugqa Wokugcina

• Qhubeka ucubungula umugqa ngomugqa.

Isinyathelo sesi-6: Lungiselela Umugqa Wokugcina

• Qinisekisa ukuthi wonke amaseli kumugqa wokugcina awesethi efanayo ngokuhlanganisa noma yimaphi amasethi ahlukene asele.