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

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

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

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

വിൽസന്റെ അൽഗോരിതത്തെക്കുറിച്ച്

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

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

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

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

ഘട്ടം 1: ഇനീഷ്യലൈസ് ചെയ്യുക

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

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

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

ഘട്ടം 3: ലൂപ്പ്-ഇറേസിംഗ് ഉപയോഗിച്ച് ക്രമരഹിതമായ നടത്തം

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

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

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

കൂടുതൽ വായനയ്ക്ക്

നിങ്ങൾക്ക് ഈ പോസ്റ്റ് ഇഷ്ടപ്പെട്ടെങ്കിൽ, ഈ നിർദ്ദേശങ്ങളും നിങ്ങൾക്ക് ഇഷ്ടപ്പെട്ടേക്കാം:

• റിക്കേഴ്‌സീവ് ബാക്ക്‌ട്രാക്കർ മെയ്സ് ജനറേറ്റർ
• ക്രുസ്കലിന്റെ അൽഗോരിതം മെയ്സ് ജനറേറ്റർ
• എല്ലർ അൽഗോറിതം മേസു ജനറേറ്റർ