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

മാസ് ജനറേഷനായി പൊരുത്തപ്പെടുത്താൻ കഴിയുന്ന ഒരു മിനിമം സ്പാനിംഗ് ട്രീ അൽഗോരിതമാണ് ക്രൂസ്കലിന്റെ അൽഗോരിതം. തികഞ്ഞ അത്ഭുതങ്ങൾ സൃഷ്ടിക്കുന്നതിന് ഇത് പ്രത്യേകിച്ചും ഫലപ്രദമാണ്. ക്രുസ്കലിന്റെ അൽഗോരിതത്തിന് ഒരു ബദൽ പ്രിമിന്റെ അൽഗോരിതമാണ്, ഇത് ഒരു മിനിമം സ്പാനിംഗ് ട്രീ അൽഗോരിതം കൂടിയാണ്, പക്ഷേ അവ സമാനമായ വിസ്മയങ്ങൾ സൃഷ്ടിക്കുകയും ക്രുസ്കലിന്റെ വേഗത്തിൽ ഓടുകയും ചെയ്യുന്നതിനാൽ, പ്രിം നടപ്പാക്കുന്നതിൽ ഞാൻ മിനക്കെട്ടില്ല.

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

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

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

അമേരിക്കൻ ഗണിതശാസ്ത്രജ്ഞനും സ്റ്റാറ്റിസ്റ്റീഷ്യനും കമ്പ്യൂട്ടർ ശാസ്ത്രജ്ഞനുമായ ജോസഫ് ബെർണാഡ് ക്രൂസ്കൽ ജൂനിയർ ആണ് ക്രൂസ്കലിന്റെ അൽഗോരിതം സൃഷ്ടിച്ചത്. 1956-ൽ "ഓൺ ദ ഷോർട്ട് സ്പാനിംഗ് സബ്ട്രീ ഓഫ് എ ഗ്രാഫ് ആൻഡ് ദി ട്രാവലിംഗ് സെയിൽസ്മാൻ പ്രോബ്ലം" എന്ന തന്റെ പ്രബന്ധത്തിൽ അദ്ദേഹം അൽഗോരിതം ആദ്യമായി വിവരിച്ചു.

ഒരു ഗ്രാഫിന്റെ മിനിമം സ്പാനിംഗ് ട്രീ (എംഎസ്ടി) കണ്ടെത്തുന്നതിനാണ് അൽഗോരിതം രൂപകൽപ്പന ചെയ്തിരിക്കുന്നത്, ചക്രങ്ങൾ ഒഴിവാക്കിക്കൊണ്ട് എല്ലാ വെർട്ടിസുകളും സാധ്യമായ ഏറ്റവും കുറഞ്ഞ അറ്റ ഭാരവുമായി ബന്ധിപ്പിച്ചിരിക്കുന്നുവെന്ന് ഉറപ്പാക്കുന്നു.

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

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

• അത്ഭുതത്തിലെ ഓരോ കോശത്തെയും ഒരു പ്രത്യേക സെറ്റായി (ഒരു സവിശേഷ ഘടകം) പരിഗണിക്കുക.
• അടുത്തുള്ള കോശങ്ങൾക്കിടയിലുള്ള എല്ലാ മതിലുകളും സാധ്യതയുള്ള അറ്റങ്ങളായി പട്ടികപ്പെടുത്തുക.

ഘട്ടം 2: സോർട്ട് ഭിത്തികൾ

• ഭിത്തികൾ മാറ്റുകയോ ക്രമരഹിതമായി ഓർഡർ ചെയ്യുകയോ ചെയ്യുക. ഇത് ഒരു യഥാർത്ഥ ക്രുസ്കലിന്റെ അൽഗോരിതമായി നടപ്പിലാക്കുകയാണെങ്കിൽ, ക്രമരഹിതമായ ക്രമത്തിൽ മതിലുകൾ തരംതിരിക്കുക (മാസ് ജനറേഷന് ഭാരങ്ങൾ ആവശ്യമില്ലാത്തതിനാൽ).

ഘട്ടം 3: പ്രോസസ്സ് മതിലുകൾ

• ഇളകിയ ചുവരുകളിലൂടെ സഞ്ചരിക്കുക.
• ഭിത്തിയാൽ വിഭജിക്കപ്പെട്ടിരിക്കുന്ന രണ്ട് സെല്ലുകൾ വ്യത്യസ്ത സെറ്റുകളിൽ പെട്ടതാണെങ്കിൽ (അതായത്, അവ ഇതുവരെ മാളത്തിൽ ബന്ധിപ്പിച്ചിട്ടില്ല), ഭിത്തി നീക്കം ചെയ്ത് സെറ്റുകൾ ലയിപ്പിക്കുക.
• അവ ഇതിനകം ഒരേ സെറ്റിലാണെങ്കിൽ, മതിൽ ഒഴിവാക്കുക (ചക്രങ്ങൾ ഒഴിവാക്കാൻ).

ഘട്ടം 4: പൂർത്തിയാകുന്നതുവരെ തുടരുക

• എല്ലാ കോശങ്ങളും ബന്ധിപ്പിക്കപ്പെടുന്നതുവരെ ഈ പ്രക്രിയ ആവർത്തിക്കുക, ഒരൊറ്റ സ്പാനിംഗ് വൃക്ഷം രൂപപ്പെടുന്നു.
• അവസാനം, ഓരോ കോശവും ലൂപ്പുകളോ ഒറ്റപ്പെട്ട വിഭാഗങ്ങളോ ഇല്ലാതെ മറ്റുള്ളവയുമായി ബന്ധിപ്പിച്ചിരിക്കുന്നു.

ക്രുസ്കലിന്റെ അൽഗോരിതം ലയന സെറ്റുകളെ ആശ്രയിച്ചിരിക്കുന്നതിനാൽ, യൂണിയൻ-ഫൈൻഡ് അൽഗോരിതം ഉപയോഗിച്ച് ഇത് ഒപ്റ്റിമൈസ് ചെയ്യാൻ കഴിയും, ഇത് മാസ് ജനറേഷനിൽ കണക്റ്റുചെയ് ത സെല്ലുകൾ ട്രാക്കുചെയ്യുന്നതിനുള്ള കാര്യക്ഷമമായ മാർഗം നൽകുന്നു. യൂണിയൻ-ഫൈൻഡ് അൽഗോരിതത്തിന്റെ എന്റെ പിഎച്ച്പി നടപ്പാക്കൽ നിങ്ങൾക്ക് ഇവിടെ കാണാൻ കഴിയും: PHP-യിലെ Disjoint Set (Union-Find Algorithm)