റിക്കേഴ്‌സീവ് ബാക്ക്‌ട്രാക്കർ മെയ്സ് ജനറേറ്റർ

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

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

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

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

പേര് ഇങ്ങനെയാണെങ്കിലും, ഇത് ആവർത്തനം ഉപയോഗിച്ച് നടപ്പിലാക്കണമെന്നില്ല. പലപ്പോഴും ഒരു LIFO ക്യൂ (അതായത് ഒരു സ്റ്റാക്ക്) ഉപയോഗിച്ച് ഒരു ആവർത്തന സമീപനത്തിലാണ് ഇത് നടപ്പിലാക്കുന്നത്. വളരെ വലിയ മേസുകൾക്ക്, പ്രോഗ്രാമിംഗ് ഭാഷയെയും ലഭ്യമായ മെമ്മറിയെയും ആശ്രയിച്ച്, ആവർത്തനം ഉപയോഗിക്കുന്നത് കോൾ സ്റ്റാക്ക് ഓവർഫ്ലോയ്ക്ക് കാരണമാകും. വലിയ അളവിലുള്ള ഡാറ്റ കൈകാര്യം ചെയ്യുന്നതിന് ഒരു LIFO ക്യൂ കൂടുതൽ എളുപ്പത്തിൽ പൊരുത്തപ്പെടുത്താൻ കഴിയും, ലഭ്യമായ മെമ്മറി പര്യാപ്തമല്ലെങ്കിൽ ഡിസ്കിലോ ഡാറ്റാബേസിലോ ക്യൂ സൂക്ഷിക്കുന്നത് പോലും.

ഇത് എങ്ങനെ പ്രവർത്തിക്കുന്നു

സ്റ്റാക്ക് അടിസ്ഥാനമാക്കിയുള്ള ഡെപ്ത്-ഫസ്റ്റ് സെർച്ച് സമീപനം ഉപയോഗിച്ചാണ് അൽഗോരിതം പ്രവർത്തിക്കുന്നത്. ഘട്ടം ഘട്ടമായുള്ള വിശദീകരണം ഇതാ:

1. ഒരു ആരംഭ സെൽ തിരഞ്ഞെടുത്ത് അത് സന്ദർശിച്ചതായി അടയാളപ്പെടുത്തുക.
2. സന്ദർശിക്കാത്ത സെല്ലുകൾ ഉള്ളപ്പോൾ:
   • ഇതുവരെ സന്ദർശിച്ചിട്ടില്ലാത്ത അയൽ സെല്ലുകൾ നോക്കൂ.
   • സന്ദർശിക്കാത്ത ഒരു അയൽക്കാരനെങ്കിലും ഉണ്ടെങ്കിൽ:
     • സന്ദർശിക്കാത്ത അയൽക്കാരിൽ ഒരാളെ ക്രമരഹിതമായി തിരഞ്ഞെടുക്കുക.
     • നിലവിലുള്ള സെല്ലിനും തിരഞ്ഞെടുത്ത അയൽക്കാരനും ഇടയിലുള്ള മതിൽ നീക്കം ചെയ്യുക.
     • തിരഞ്ഞെടുത്ത അയൽക്കാരന്റെ അടുത്തേക്ക് നീങ്ങി സന്ദർശിച്ചതായി അടയാളപ്പെടുത്തുക.
     • നിലവിലെ സെൽ സ്റ്റാക്കിലേക്ക് തള്ളുക.
   • സന്ദർശിക്കാത്ത അയൽക്കാർ ഇല്ലെങ്കിൽ:
     • സ്റ്റാക്കിൽ നിന്ന് അവസാന സെൽ പോപ്പ് ചെയ്തുകൊണ്ട് ബാക്ക്‌ട്രാക്ക് ചെയ്യുക.
3. സ്റ്റാക്ക് ശൂന്യമാകുന്നതുവരെ ഈ പ്രക്രിയ തുടരുക.

ഈ അൽഗോരിതത്തെക്കുറിച്ചുള്ള രസകരമായ ഒരു വസ്തുത, ഇത് ഒരു മേസ് ജനറേറ്ററായും ഒരു മേസ് സോൾവറായും പ്രവർത്തിക്കുന്നു എന്നതാണ്. നിങ്ങൾ ഇതിനകം ജനറേറ്റ് ചെയ്ത ഒരു മേസിൽ ഇത് പ്രവർത്തിപ്പിച്ച് നിങ്ങൾ തീരുമാനിച്ച അവസാന പോയിന്റിൽ എത്തുമ്പോൾ നിർത്തുകയാണെങ്കിൽ, സ്റ്റാക്കിൽ മേസിനുള്ള പരിഹാരം അടങ്ങിയിരിക്കും.

ഈ സൈറ്റിൽ ഈ അൽഗോരിതത്തിന്റെ രണ്ട് പതിപ്പുകൾ എന്റെ കൈവശമുണ്ട്: ഈ പേജിൽ മേസുകൾ സൃഷ്ടിക്കുന്നതിനുള്ള LIFO ക്യൂ അടിസ്ഥാനമാക്കിയുള്ള ഒന്ന്, മേസുകൾ പരിഹരിക്കുന്നതിനുള്ള റിക്കർഷൻ അടിസ്ഥാനമാക്കിയുള്ള ഒന്ന്, മറ്റ് അൽഗോരിതങ്ങൾ സൃഷ്ടിക്കുന്ന മേസുകൾ (സൊല്യൂഷനുകളുള്ള മാപ്പുകൾ നിർമ്മിക്കുന്നത് അങ്ങനെയാണ്). രണ്ട് വ്യത്യസ്ത പതിപ്പുകൾ ഉള്ളത് സ്പോർട്സിന് മാത്രമുള്ളതാണ്, കാരണം ഞാൻ അത് രസകരമായി കാണുന്ന ഒരു നെർഡ് ആണ്, രണ്ടിനും ഒന്നുകിൽ പ്രവർത്തിക്കാമായിരുന്നു ;-)