വിൽസന്റെ അൽഗോരിതം മെയ്സ് ജനറേറ്റർ

വിൽസന്റെ അൽഗോരിതം ഒരു ലൂപ്പ്-മായ്ച്ചുകളഞ്ഞ റാൻഡം വാക്ക് രീതിയാണ്, ഇത് വിസ്മയം സൃഷ്ടിക്കുന്നതിനായി ഏകീകൃത സ്പാനിംഗ് മരങ്ങൾ സൃഷ്ടിക്കുന്നു. ഇതിനർത്ഥം ഒരു നിശ്ചിത വലുപ്പത്തിലുള്ള സാധ്യമായ എല്ലാ അത്ഭുതങ്ങളും തുല്യമായി സൃഷ്ടിക്കപ്പെടാൻ സാധ്യതയുണ്ട്, ഇത് ഒരു പക്ഷപാതരഹിതമായ മേസ് ജനറേഷൻ ടെക്നിക്കായി മാറുന്നു. വിൽസന്റെ അൽഗോരിതം ആൽഡസ്-ബ്രോഡർ അൽഗോരിതത്തിന്റെ മെച്ചപ്പെട്ട പതിപ്പായി കണക്കാക്കാം, കാരണം ഇത് സമാന സ്വഭാവസവിശേഷതകളുള്ള അത്ഭുതങ്ങൾ സൃഷ്ടിക്കുന്നു, പക്ഷേ ഇത് വളരെ വേഗത്തിൽ പ്രവർത്തിക്കുന്നു, അതിനാൽ ഇവിടെ ആൽഡസ്-ബ്രോഡർ അൽഗോരിതം നടപ്പിലാക്കാൻ ഞാൻ മിനക്കെട്ടില്ല.

ഒരു തികഞ്ഞ ചക്രവാളം എന്നത് ഒരു ചക്രവാളത്തിലെ ഏതെങ്കിലും ഒരു ബിന്ദുവിൽ നിന്ന് മറ്റൊരു ബിന്ദുവിലേക്ക് കൃത്യമായി ഒരു പാത മാത്രമുള്ള ഒരു ചക്രവാളമാണ്. അതായത് നിങ്ങൾക്ക് വൃത്താകൃതിയിൽ ചുറ്റി സഞ്ചരിക്കാൻ കഴിയില്ല, പക്ഷേ നിങ്ങൾ പലപ്പോഴും നിർജ്ജീവമായ അറ്റങ്ങൾ നേരിടേണ്ടിവരും, അത് നിങ്ങളെ തിരിഞ്ഞുനോക്കാനും തിരികെ പോകാനും നിർബന്ധിതരാക്കും.

ഇവിടെ ജനറേറ്റ് ചെയ്‌ത മേജ് മാപ്പുകളിൽ സ്റ്റാർട്ട്, ഫിനിഷ് പൊസിഷനുകളൊന്നുമില്ലാത്ത ഒരു ഡിഫോൾട്ട് പതിപ്പ് ഉൾപ്പെടുന്നു, അതിനാൽ നിങ്ങൾക്ക് അവ സ്വയം തീരുമാനിക്കാം: മേജിലെ ഏത് പോയിന്റിൽ നിന്നും മറ്റേതെങ്കിലും പോയിന്റിലേക്ക് ഒരു പരിഹാരം ഉണ്ടാകും. നിങ്ങൾക്ക് പ്രചോദനം വേണമെങ്കിൽ, നിങ്ങൾക്ക് നിർദ്ദേശിക്കപ്പെട്ട ഒരു സ്റ്റാർട്ട്, ഫിനിഷ് പൊസിഷൻ പ്രവർത്തനക്ഷമമാക്കാം - കൂടാതെ രണ്ടിനുമിടയിലുള്ള പരിഹാരം പോലും കാണാം.

Wilson's Algorithm കുറിച്ച്

ലൂപ്പ്-മായ്ച്ചുകളഞ്ഞ റാൻഡം മതിൽ ഉപയോഗിച്ച് വൃക്ഷങ്ങളിൽ യൂണിഫോം സൃഷ്ടിക്കുന്നതിനുള്ള വിൽസന്റെ അൽഗോരിതം ഡേവിഡ് ബ്രൂസ് വിൽസൺ സൃഷ്ടിച്ചു.

1996-ൽ വിൽസൺ ഈ അൽഗോരിതം ആദ്യമായി അവതരിപ്പിച്ചത് യാദൃച്ഛികമായി വ്യാപിച്ചുകിടക്കുന്ന വൃക്ഷങ്ങളെയും മാർക്കോവ് ശൃംഖലകളെയും പ്രോബബിലിറ്റി സിദ്ധാന്തത്തിൽ ഗവേഷണം ചെയ്യുമ്പോഴാണ്. അദ്ദേഹത്തിന്റെ പ്രവർത്തനങ്ങൾ പ്രാഥമികമായി ഗണിതശാസ്ത്രത്തിലും സ്റ്റാറ്റിസ്റ്റിക്കൽ ഭൗതികശാസ്ത്രത്തിലും ആയിരുന്നുവെങ്കിലും, തികച്ചും ഏകീകൃത വിസ്മയങ്ങൾ നിർമ്മിക്കാനുള്ള കഴിവ് കാരണം അൽഗോരിതം മാസ് ജനറേഷനായി വ്യാപകമായി സ്വീകരിച്ചു.

മേസ് ജനറേഷനായി വിൽസന്റെ അൽഗോരിതം എങ്ങനെ പ്രവർത്തിക്കുന്നു

ക്രമരഹിതമായ നടത്തം ഉപയോഗിച്ച് സന്ദർശിക്കാത്ത സെല്ലുകളിൽ നിന്ന് പാതകൾ കൊത്തിയെടുത്ത് അവസാന വിസ്മയം ലൂപ്പുകളില്ലാതെ പൂർണ്ണമായും ബന്ധിപ്പിച്ചിട്ടുണ്ടെന്ന് വിൽസന്റെ അൽഗോരിതം ഉറപ്പാക്കുന്നു.

ഘട്ടം 1: പ്രാരംഭം

• ചുവരുകൾ നിറഞ്ഞ ഒരു ഗ്രിഡ് ഉപയോഗിച്ച് ആരംഭിക്കുക.
• സാധ്യമായ എല്ലാ പാസേജ് സെല്ലുകളുടെയും ഒരു ലിസ്റ്റ് നിർവചിക്കുക.

ഘട്ടം 2: റാൻഡം സ്റ്റാർട്ടിംഗ് സെൽ തിരഞ്ഞെടുക്കുക

• ഏതെങ്കിലും ക്രമരഹിതമായ സെൽ തിരഞ്ഞെടുത്ത് സന്ദർശിച്ചതായി അടയാളപ്പെടുത്തുക. ഇത് തലമുറയിലെ വിസ്മയത്തിന്റെ ആരംഭ പോയിന്റായി വർത്തിക്കുന്നു.

ഘട്ടം 3: ലൂപ്പ്-എറേസിംഗ് ഉപയോഗിച്ച് റാൻഡം വാക്ക്

• സന്ദർശിക്കാത്ത ഒരു സെൽ തിരഞ്ഞെടുത്ത് ക്രമരഹിതമായ ഒരു നടത്തം ആരംഭിക്കുക (ക്രമരഹിതമായ ദിശകളിൽ നീങ്ങുക).
• നടത്തം ഇതിനകം സന്ദർശിച്ച ഒരു സെല്ലിൽ എത്തുകയാണെങ്കിൽ, പാതയിലെ ഏതെങ്കിലും ലൂപ്പുകൾ മായ്ച്ചുകളയുക.
• നടത്തം സന്ദർശിച്ച പ്രദേശവുമായി ബന്ധിപ്പിച്ചുകഴിഞ്ഞാൽ, പാതയിലെ എല്ലാ സെല്ലുകളും സന്ദർശിച്ചതുപോലെ അടയാളപ്പെടുത്തുക.

ഘട്ടം 4: എല്ലാ സെല്ലുകളും സന്ദർശിക്കുന്നതുവരെ ആവർത്തിക്കുക:

• സന്ദർശിക്കാത്ത കോശങ്ങൾ തിരഞ്ഞെടുക്കുന്നതും ഓരോ കോശവും വിസ്മയത്തിന്റെ ഭാഗമാകുന്നതുവരെ ക്രമരഹിതമായ നടത്തം നടത്തുന്നതും തുടരുക.