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

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

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

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

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

അമേരിക്കൻ ഗണിതശാസ്ത്രജ്ഞനും, സ്റ്റാറ്റിസ്റ്റിഷ്യനും, കമ്പ്യൂട്ടർ ശാസ്ത്രജ്ഞനുമായ ജോസഫ് ബെർണാഡ് ക്രുസ്കൽ ജൂനിയറാണ് ക്രുസ്കലിന്റെ അൽഗോരിതം സൃഷ്ടിച്ചത്. 1956-ൽ "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem" എന്ന തന്റെ പ്രബന്ധത്തിലാണ് അദ്ദേഹം ആദ്യമായി അൽഗോരിതം വിശദീകരിച്ചത്.

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

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

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

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

ഘട്ടം 2: ചുവരുകൾ അടുക്കുക

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

ഘട്ടം 3: പ്രോസസ് ഭിത്തികൾ

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

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

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

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

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

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

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