Wilson se algoritme doolhof kragopwekker

Wilson se algoritme is 'n lus-uitgevee ewekansige loopmetode wat uniforme oorspannende bome vir doolhofskepping genereer. Dit beteken dat alle moontlike doolhowe van 'n gegewe grootte ewe waarskynlik gegenereer sal word, wat dit 'n onbevooroordeelde doolhofgenereringstegniek maak. Wilson se algoritme kan as 'n verbeterde weergawe van die Aldous-Broder-algoritme beskou word, aangesien dit doolhowe met identiese eienskappe genereer, maar dit loop baie vinniger, so ek het nie die moeite gedoen om die Aldous-Broder-algoritme hier te implementeer nie.

'n Volmaakte doolhof is 'n doolhof waarin daar presies een pad van enige punt in die doolhof na enige ander punt is. Dit beteken dat jy nie uiteindelik in sirkels kan rondloop nie, maar jy sal dikwels doodloopstrate teëkom, wat jou dwing om om te draai en terug te gaan.

Die doolhofkaarte wat hier gegenereer word, bevat 'n verstekweergawe sonder enige begin- en eindposisies, so jy kan dit self besluit: daar sal 'n oplossing wees van enige punt in die doolhof na enige ander punt. As jy inspirasie wil hê, kan jy 'n voorgestelde begin- en eindposisie aktiveer - en selfs die oplossing tussen die twee sien.

Oor Wilson se Algoritme

Wilson se algoritme vir die generering van uniforme oorspannende bome met behulp van 'n lus-uitgevee ewekansige muur is deur David Bruce Wilson geskep.

Wilson het hierdie algoritme oorspronklik in 1996 bekendgestel terwyl hy navorsing gedoen het oor ewekansige oorspannende bome en Markov-kettings in waarskynlikheidsteorie. Alhoewel sy werk hoofsaaklik in wiskunde en statistiese fisika was, is die algoritme sedertdien wyd aangeneem vir doolhofgenerering as gevolg van sy vermoë om perfek uniforme doolhowe te produseer.

Hoe Wilson se Algoritme Werk vir Doolhofgenerering

Wilson se algoritme verseker dat die finale doolhof volledig verbind is sonder enige lusse deur iteratief paaie uit onbesoekte selle te kerf met behulp van ewekansige wandelings.

Stap 1: Inisialiseer

• Begin met 'n rooster gevul met mure.
• Definieer 'n lys van alle moontlike deurgangselle.

Stap 2: Kies 'n ewekansige beginsel

• Kies enige ewekansige sel en merk dit as besoek. Dit dien as die beginpunt van die doolhof tydens generering.

Stap 3: Willekeurige loop met lusuitwissing

• Kies 'n onbesoekte sel en begin 'n ewekansige stap (beweeg in ewekansige rigtings).
• As die stap 'n reeds besoekte sel bereik, vee enige lusse in die pad uit.
• Sodra die staptog met die besoekte streek verbind, merk al die selle in die pad as besoek.

Stap 4: Herhaal totdat alle selle besoek is:

• Gaan voort met die seleksie van onbesoekte selle en die uitvoering van ewekansige wandelings totdat elke sel deel van die doolhof is.

Verdere Leeswerk

As jy hierdie plasing geniet het, sal jy dalk ook van hierdie voorstelle hou:

• Jag en maak doolhof kragopwekker dood
• Kruskal se algoritme doolhof kragopwekker
• Groeiende boom algoritme doolhof kragopwekker