പാരാമീറ്ററൈസ്ഡ് അൽഗോരിതങ്ങൾ ഉപയോഗിച്ച് NP-ഹാർഡ് പ്രശ്നങ്ങൾ എങ്ങനെ പരിഹരിക്കാം

ഞങ്ങളുടെ പരിശീലനത്തിന്റെ ഏറ്റവും രസകരമായ ഭാഗമാണ് ഗവേഷണ പ്രവർത്തനങ്ങൾ. യൂണിവേഴ്സിറ്റിയിൽ ആയിരിക്കുമ്പോൾ തന്നെ നിങ്ങൾ തിരഞ്ഞെടുത്ത ദിശയിൽ സ്വയം പരീക്ഷിക്കുക എന്നതാണ് ആശയം. ഉദാഹരണത്തിന്, സോഫ്റ്റ്‌വെയർ എഞ്ചിനീയറിംഗ്, മെഷീൻ ലേണിംഗ് എന്നീ മേഖലകളിൽ നിന്നുള്ള വിദ്യാർത്ഥികൾ പലപ്പോഴും കമ്പനികളിൽ ഗവേഷണം നടത്തുന്നു (പ്രധാനമായും JetBrains അല്ലെങ്കിൽ Yandex, പക്ഷേ മാത്രമല്ല).

ഈ പോസ്റ്റിൽ ഞാൻ കമ്പ്യൂട്ടർ സയൻസിലെ എന്റെ പ്രോജക്റ്റിനെക്കുറിച്ച് സംസാരിക്കും. എന്റെ ജോലിയുടെ ഭാഗമായി, ഏറ്റവും പ്രശസ്തമായ NP- ഹാർഡ് പ്രശ്‌നങ്ങളിലൊന്ന് പരിഹരിക്കുന്നതിനുള്ള സമീപനങ്ങൾ ഞാൻ പഠിക്കുകയും പ്രായോഗികമാക്കുകയും ചെയ്തു: ശീർഷം മൂടുന്ന പ്രശ്നം.

ഇക്കാലത്ത്, NP- ഹാർഡ് പ്രശ്നങ്ങൾക്കുള്ള രസകരമായ ഒരു സമീപനം വളരെ വേഗത്തിൽ വികസിച്ചുകൊണ്ടിരിക്കുന്നു - പാരാമീറ്ററൈസ്ഡ് അൽഗോരിതങ്ങൾ. ഞാൻ നിങ്ങളെ വേഗത്തിലാക്കാൻ ശ്രമിക്കും, കുറച്ച് ലളിതമായ പാരാമീറ്ററൈസ്ഡ് അൽഗോരിതങ്ങൾ പറഞ്ഞുതരും, എന്നെ വളരെയധികം സഹായിച്ച ശക്തമായ ഒരു രീതി വിവരിക്കുക. PACE ചലഞ്ച് മത്സരത്തിൽ ഞാൻ എന്റെ ഫലങ്ങൾ അവതരിപ്പിച്ചു: ഓപ്പൺ ടെസ്റ്റുകളുടെ ഫലങ്ങൾ അനുസരിച്ച്, എന്റെ പരിഹാരം മൂന്നാം സ്ഥാനത്താണ്, അന്തിമ ഫലങ്ങൾ ജൂലൈ 1 ന് അറിയപ്പെടും.

എന്നെക്കുറിച്ച്

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

പാരാമീറ്ററൈസ്ഡ് അൽഗോരിതങ്ങളിലെ പരിമിതമായ എണ്ണം സ്പെഷ്യലിസ്റ്റുകൾ ബാറിലേക്ക് പ്രവേശിക്കുന്നു...

പുസ്തകത്തിൽ നിന്ന് എടുത്ത ഉദാഹരണം "പാരാമീറ്ററൈസ്ഡ് അൽഗോരിതങ്ങൾ"

നിങ്ങൾ ഒരു ചെറിയ പട്ടണത്തിലെ ബാർ സെക്യൂരിറ്റി ഗാർഡാണെന്ന് സങ്കൽപ്പിക്കുക. എല്ലാ വെള്ളിയാഴ്ചയും, നഗരത്തിന്റെ പകുതിയും വിശ്രമിക്കാൻ നിങ്ങളുടെ ബാറിലേക്ക് വരുന്നു, ഇത് നിങ്ങൾക്ക് വളരെയധികം പ്രശ്‌നങ്ങൾ നൽകുന്നു: വഴക്കുകൾ തടയാൻ നിങ്ങൾ ബാറിൽ നിന്ന് റൗഡി ഉപഭോക്താക്കളെ പുറത്താക്കേണ്ടതുണ്ട്. ഒടുവിൽ, നിങ്ങൾ മടുത്തു, പ്രതിരോധ നടപടികൾ സ്വീകരിക്കാൻ തീരുമാനിക്കുന്നു.

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

നിർഭാഗ്യവശാൽ, നിങ്ങളുടെ മുന്നിലുള്ള പ്രശ്നം ഒരു ക്ലാസിക് NP-ഹാർഡ് പ്രശ്നമാണ്. നിങ്ങൾക്ക് അവളെ അങ്ങനെ അറിയാമായിരിക്കാം വെർട്ടക്സ് കവർ, അല്ലെങ്കിൽ ഒരു വെർട്ടക്സ് കവറിങ് പ്രശ്നമായി. അത്തരം പ്രശ്നങ്ങൾക്ക്, പൊതുവായ സാഹചര്യത്തിൽ, സ്വീകാര്യമായ സമയത്ത് പ്രവർത്തിക്കുന്ന അൽഗോരിതങ്ങൾ ഒന്നുമില്ല. കൃത്യമായി പറഞ്ഞാൽ, തെളിയിക്കപ്പെടാത്തതും ശക്തവുമായ അനുമാനം ETH (എക്‌സ്‌പോണൻഷ്യൽ ടൈം ഹൈപ്പോതെസിസ്) പറയുന്നത് ഈ പ്രശ്‌നം കൃത്യസമയത്ത് പരിഹരിക്കാൻ കഴിയില്ല എന്നാണ്. , അതായത്, പൂർണ്ണമായ തിരയലിനേക്കാൾ ശ്രദ്ധേയമായ ഒന്നും നിങ്ങൾക്ക് ചിന്തിക്കാൻ കഴിയില്ല. ഉദാഹരണത്തിന്, ആരെങ്കിലും നിങ്ങളുടെ ബാറിലേക്ക് വരാൻ പോകുന്നു എന്ന് പറയാം n = 1000 മനുഷ്യൻ. അപ്പോൾ പൂർണ്ണമായ തിരയൽ ആയിരിക്കും ഏകദേശം ഉള്ള ഓപ്ഷനുകൾ - ഭ്രാന്തൻ തുക. ഭാഗ്യവശാൽ, നിങ്ങളുടെ മാനേജ്മെന്റ് നിങ്ങൾക്ക് ഒരു പരിധി നൽകിയിരിക്കുന്നു k = 10, അതിനാൽ നിങ്ങൾ ആവർത്തിക്കേണ്ട കോമ്പിനേഷനുകളുടെ എണ്ണം വളരെ ചെറുതാണ്: പത്ത് മൂലകങ്ങളുടെ ഉപഗണങ്ങളുടെ എണ്ണം . ഇത് മികച്ചതാണ്, പക്ഷേ ശക്തമായ ഒരു ക്ലസ്റ്ററിൽ പോലും ഇത് ഒരു ദിവസത്തിനുള്ളിൽ കണക്കാക്കില്ല.

ബാറിന്റെ സന്ദർശകർ തമ്മിലുള്ള ബന്ധങ്ങളുടെ ഈ കോൺഫിഗറേഷനിൽ വഴക്കുണ്ടാകാനുള്ള സാധ്യത ഇല്ലാതാക്കാൻ, നിങ്ങൾ ബോബ്, ഡാനിയൽ, ഫെഡോർ എന്നിവരെ ഒഴിവാക്കേണ്ടതുണ്ട്. രണ്ടെണ്ണം മാത്രം ബാക്കിയാകുന്ന ഒരു പരിഹാരവുമില്ല.

വഴങ്ങി എല്ലാവരെയും അകത്തേക്ക് വിടാനുള്ള സമയമാണിതെന്ന് ഇതിനർത്ഥം? നമുക്ക് മറ്റ് ഓപ്ഷനുകൾ പരിഗണിക്കാം. ശരി, ഉദാഹരണത്തിന്, വളരെ വലിയ ആളുകളുമായി വഴക്കിടാൻ സാധ്യതയുള്ളവരെ മാത്രം നിങ്ങൾക്ക് അനുവദിക്കാൻ കഴിയില്ല. ആർക്കെങ്കിലും വഴക്കിടാൻ കഴിയുമെങ്കിൽ k+1 മറ്റൊരാൾ, അപ്പോൾ നിങ്ങൾക്ക് തീർച്ചയായും അവനെ അകത്തേക്ക് കടക്കാൻ കഴിയില്ല - അല്ലാത്തപക്ഷം നിങ്ങൾ എല്ലാവരേയും പുറത്ത് നിർത്തേണ്ടിവരും k+1 നഗരവാസികൾ, അവനുമായി യുദ്ധം ചെയ്യാൻ കഴിയും, ഇത് തീർച്ചയായും നേതൃത്വത്തെ അസ്വസ്ഥമാക്കും.

ഈ തത്ത്വമനുസരിച്ച് നിങ്ങൾക്ക് കഴിയുന്ന എല്ലാവരെയും പുറത്താക്കാൻ നിങ്ങളെ അനുവദിക്കുക. അപ്പോൾ മറ്റെല്ലാവർക്കും അതിൽ കൂടുതലൊന്നും കൂടാതെ യുദ്ധം ചെയ്യാം k ആളുകൾ. അവരെ പുറത്താക്കുന്നു k മനുഷ്യാ, നിങ്ങൾക്ക് അതിൽ കൂടുതലൊന്നും തടയാൻ കഴിയില്ല സംഘർഷങ്ങൾ. അതിലും കൂടുതൽ ഉണ്ടെങ്കിൽ എന്നാണ് ഇതിനർത്ഥം ഒരു വ്യക്തി കുറഞ്ഞത് ഒരു സംഘട്ടനത്തിലെങ്കിലും ഉൾപ്പെട്ടിട്ടുണ്ടെങ്കിൽ, തീർച്ചയായും നിങ്ങൾക്ക് അവയെല്ലാം തടയാൻ കഴിയില്ല. തീർച്ചയായും, നിങ്ങൾ തീർച്ചയായും തികച്ചും വൈരുദ്ധ്യമില്ലാത്ത ആളുകളെ അനുവദിക്കുമെന്നതിനാൽ, ഇരുനൂറിൽ പത്ത് പേരുടെ എല്ലാ ഉപവിഭാഗങ്ങളിലൂടെയും നിങ്ങൾ പോകേണ്ടതുണ്ട്. ഏകദേശം ഉണ്ട് , കൂടാതെ ഈ പ്രവർത്തനങ്ങളുടെ എണ്ണം ഇതിനകം തന്നെ ക്ലസ്റ്ററിൽ അടുക്കാൻ കഴിയും.

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

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

മുകളിലുള്ള ഉദാഹരണം ഒരു ഉദാഹരണമാണ് പാരാമീറ്റർ ചെയ്ത അൽഗോരിതം. കൃത്യസമയത്ത് പ്രവർത്തിക്കുന്ന അൽഗോരിതങ്ങളാണ് പാരാമീറ്ററൈസ്ഡ് അൽഗോരിതങ്ങൾ f(k) poly(n)എവിടെ p - ബഹുപദം, f ഒരു അനിയന്ത്രിതമായ കംപ്യൂട്ടബിൾ ഫംഗ്ഷനാണ്, കൂടാതെ k - ചില പരാമീറ്റർ, അത്, ഒരുപക്ഷേ, പ്രശ്നത്തിന്റെ വലിപ്പത്തേക്കാൾ വളരെ ചെറുതായിരിക്കും.

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

പേസ് ചലഞ്ച്

മത്സരം PACE ചലഞ്ച് (The Parameterized Algorithms and Computational Experiments Challenge) 2015-ൽ ജനിച്ചത് പാരാമീറ്ററൈസ്ഡ് അൽഗോരിതങ്ങളും കമ്പ്യൂട്ടേഷണൽ പ്രശ്നങ്ങൾ പരിഹരിക്കാൻ പ്രായോഗികമായി ഉപയോഗിക്കുന്ന സമീപനങ്ങളും തമ്മിൽ ഒരു ബന്ധം സ്ഥാപിക്കാനാണ്. ആദ്യത്തെ മൂന്ന് മത്സരങ്ങൾ ഒരു ഗ്രാഫിന്റെ മരത്തിന്റെ വീതി കണ്ടെത്തുന്നതിനാണ് നീക്കിവച്ചത് (ട്രീവിഡ്ത്ത്), ഒരു സ്റ്റൈനർ മരത്തിനായി തിരയുന്നു (സ്റ്റൈനർ ട്രീ) ചക്രങ്ങളെ മുറിക്കുന്ന ഒരു കൂട്ടം ലംബങ്ങൾക്കായി തിരയുന്നു (ഫീഡ്ബാക്ക് വെർട്ടക്സ് സെറ്റ്). ഈ വർഷം, നിങ്ങൾക്ക് ശ്രമിക്കാവുന്ന ഒരു പ്രശ്നമാണ് മുകളിൽ വിവരിച്ച വെർട്ടെക്സ് കവറിംഗ് പ്രശ്നം.

മത്സരം എല്ലാ വർഷവും ജനപ്രീതി നേടുന്നു. പ്രാഥമിക ഡാറ്റ നിങ്ങൾ വിശ്വസിക്കുന്നുവെങ്കിൽ, ഈ വർഷം 24 ടീമുകൾ വെർട്ടക്സ് കവറിംഗ് പ്രശ്നം മാത്രം പരിഹരിക്കാൻ മത്സരത്തിൽ പങ്കെടുത്തു. മത്സരം നിരവധി മണിക്കൂറുകളോ ഒരാഴ്ചയോ അല്ല, നിരവധി മാസങ്ങൾ നീണ്ടുനിൽക്കുമെന്നത് ശ്രദ്ധിക്കേണ്ടതാണ്. ടീമുകൾക്ക് സാഹിത്യം പഠിക്കാനും സ്വന്തം യഥാർത്ഥ ആശയം കൊണ്ടുവരാനും അത് നടപ്പിലാക്കാൻ ശ്രമിക്കാനും അവസരമുണ്ട്. ചുരുക്കത്തിൽ, ഈ മത്സരം ഒരു ഗവേഷണ പദ്ധതിയാണ്. സമ്മേളനത്തോടനുബന്ധിച്ച് ഏറ്റവും ഫലപ്രദമായ പരിഹാരങ്ങൾക്കായുള്ള ആശയങ്ങളും വിജയികൾക്ക് അവാർഡും നൽകും IPEC യൂറോപ്പിലെ ഏറ്റവും വലിയ വാർഷിക അൽഗോരിതമിക് മീറ്റിംഗിന്റെ ഭാഗമായി (പാരാമീറ്ററൈസ്ഡ് ആൻഡ് എക്‌സ്‌ക്റ്റ് കമ്പ്യൂട്ടേഷൻ ഓൺ ഇന്റർനാഷണൽ സിമ്പോസിയം) വാളുറ. മത്സരത്തെക്കുറിച്ചുള്ള കൂടുതൽ വിശദമായ വിവരങ്ങൾ ഇവിടെ കാണാം സൈറ്റ്, മുൻ വർഷങ്ങളിലെ ഫലങ്ങൾ നുണ ഇവിടെ.

പരിഹാര ഡയഗ്രം

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

പൊതുവായ സ്കീം ഇതാണ്: ഞങ്ങൾ ലളിതവൽക്കരണ നിയമങ്ങൾ പ്രയോഗിക്കുന്നു, തുടർന്ന് ഞങ്ങൾ ചില ശീർഷകങ്ങൾ തിരഞ്ഞെടുത്ത് രണ്ട് ആവർത്തന കോളുകൾ ചെയ്യുന്നു: ആദ്യം ഞങ്ങൾ അത് പ്രതികരണമായി എടുക്കുന്നു, മറ്റൊന്നിൽ ഞങ്ങൾ അതിന്റെ എല്ലാ അയൽക്കാരെയും എടുക്കുന്നു. ഇതിനെയാണ് നമ്മൾ ഈ ശീർഷകത്തിൽ വിഭജിക്കുന്നത് (ശാഖകൾ) എന്ന് വിളിക്കുന്നത്.

അടുത്ത ഖണ്ഡികയിൽ ഈ സ്കീമിലേക്ക് കൃത്യമായി ഒരു കൂട്ടിച്ചേർക്കൽ നടത്തും.

വിഭജിക്കുന്ന (ബ്രഞ്ചിംഗ്) നിയമങ്ങൾക്കുള്ള ആശയങ്ങൾ

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

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

ഇത് എങ്ങനെ ചെയ്യാം? ഗ്രാഫിൽ ഒരു ആർട്ടിക്കുലേഷൻ പോയിന്റ് ഉണ്ടെങ്കിൽ, നിങ്ങൾ അതിൽ പോരാടേണ്ടതുണ്ട്. നീക്കം ചെയ്യുമ്പോൾ ഗ്രാഫിന് അതിന്റെ കണക്റ്റിവിറ്റി നഷ്ടപ്പെടുന്ന തരത്തിൽ ഒരു ശീർഷകമാണ് ആർട്ടിക്യുലേഷൻ പോയിന്റ്. ഒരു ഗ്രാഫിലെ എല്ലാ ജംഗ്ഷൻ പോയിന്റുകളും ലീനിയർ ടൈമിൽ ക്ലാസിക്കൽ അൽഗോരിതം ഉപയോഗിച്ച് കണ്ടെത്താനാകും. ഈ സമീപനം ശാഖകളെ ഗണ്യമായി വേഗത്തിലാക്കുന്നു.

തിരഞ്ഞെടുത്ത ഏതെങ്കിലും ലംബങ്ങൾ നീക്കം ചെയ്യുമ്പോൾ, ഗ്രാഫ് ബന്ധിപ്പിച്ച ഘടകങ്ങളായി വിഭജിക്കും.

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

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

ക്രമരഹിതമായ ലംബങ്ങളുടെ ജോഡികൾക്കിടയിലുള്ള മുറിവുകൾ നോക്കാനും ഏറ്റവും സമതുലിതമായ ഒന്ന് എടുക്കാനും ഞാൻ പലതവണ ശ്രമിച്ചു. നിർഭാഗ്യവശാൽ, ഇത് ഓപ്പൺ പേസ് ചലഞ്ച് ടെസ്റ്റിംഗിൽ മോശം ഫലങ്ങൾ ഉണ്ടാക്കി. ഞാൻ അതിനെ ഒരു ആൽഗരിതവുമായി താരതമ്യം ചെയ്തു, അത് പരമാവധി ഡിഗ്രിയുടെ ലംബങ്ങളെ വിഭജിക്കുകയും ഇറക്കത്തിന്റെ ആഴത്തിൽ ഒരു പരിമിതിയോടെ അവയെ പ്രവർത്തിപ്പിക്കുകയും ചെയ്യുന്നു. ഈ രീതിയിൽ ഒരു കട്ട് കണ്ടെത്താൻ ശ്രമിക്കുന്ന ഒരു അൽഗോരിതം വലിയ ഗ്രാഫുകൾക്ക് പിന്നിൽ അവശേഷിക്കുന്നു. മുറിവുകൾ വളരെ അസന്തുലിതമായി മാറിയതാണ് ഇതിന് കാരണം: 5-10 ലംബങ്ങൾ നീക്കം ചെയ്താൽ, 15-20 വരെ മാത്രമേ വിഭജിക്കാൻ കഴിയൂ.

സൈദ്ധാന്തികമായി വേഗതയേറിയ അൽഗോരിതങ്ങളെക്കുറിച്ചുള്ള ലേഖനങ്ങൾ വിഭജിക്കുന്നതിന് വെർട്ടിസുകൾ തിരഞ്ഞെടുക്കുന്നതിന് കൂടുതൽ വിപുലമായ സാങ്കേതിക വിദ്യകൾ ഉപയോഗിക്കുന്നു എന്നത് ശ്രദ്ധിക്കേണ്ടതാണ്. അത്തരം ടെക്നിക്കുകൾക്ക് വളരെ സങ്കീർണ്ണമായ നിർവ്വഹണവും സമയത്തിന്റെയും മെമ്മറിയുടെയും കാര്യത്തിൽ പലപ്പോഴും മോശം പ്രകടനമുണ്ട്. പരിശീലനത്തിന് സ്വീകാര്യമായവ തിരിച്ചറിയാൻ എനിക്ക് കഴിഞ്ഞില്ല.

ലളിതവൽക്കരണ നിയമങ്ങൾ എങ്ങനെ പ്രയോഗിക്കാം

കേർണലൈസേഷനുള്ള ആശയങ്ങൾ ഞങ്ങൾക്കുണ്ട്. ഞാൻ നിങ്ങളെ ഓർമ്മിപ്പിക്കട്ടെ:

1. ഒറ്റപ്പെട്ട ശീർഷകം ഉണ്ടെങ്കിൽ, അത് ഇല്ലാതാക്കുക.
2. ഡിഗ്രി 1 ന്റെ ഒരു ശീർഷകം ഉണ്ടെങ്കിൽ, അത് നീക്കം ചെയ്ത് പ്രതികരണമായി അതിന്റെ അയൽക്കാരനെ എടുക്കുക.
3. കുറഞ്ഞത് ഡിഗ്രിയുടെ ഒരു ശീർഷകം ഉണ്ടെങ്കിൽ k+1, തിരികെ എടുക്കുക.

ആദ്യ രണ്ടിൽ എല്ലാം വ്യക്തമാണ്, മൂന്നാമത്തേതിൽ ഒരു തന്ത്രമുണ്ട്. ഒരു ബാറിനെക്കുറിച്ചുള്ള ഒരു കോമിക് പ്രശ്‌നമുണ്ടെങ്കിൽ ഞങ്ങൾക്ക് ഉയർന്ന പരിധി നൽകിയിട്ടുണ്ട് k, പിന്നെ PACE ചലഞ്ചിൽ നിങ്ങൾ ഏറ്റവും കുറഞ്ഞ വലുപ്പമുള്ള ഒരു വെർട്ടെക്സ് കവർ കണ്ടെത്തേണ്ടതുണ്ട്. ഇത് തിരയൽ പ്രശ്‌നങ്ങളെ തീരുമാന പ്രശ്‌നങ്ങളാക്കി മാറ്റുന്ന ഒരു സാധാരണ രൂപമാണ്; പലപ്പോഴും രണ്ട് തരത്തിലുള്ള പ്രശ്‌നങ്ങൾ തമ്മിൽ വ്യത്യാസമില്ല. പ്രായോഗികമായി, ഞങ്ങൾ വെർട്ടെക്സ് കവറിങ് പ്രശ്നത്തിന് ഒരു സോൾവർ എഴുതുകയാണെങ്കിൽ, ഒരു വ്യത്യാസമുണ്ടാകാം. ഉദാഹരണത്തിന്, മൂന്നാമത്തെ പോയിന്റിലെന്നപോലെ.

നടപ്പാക്കൽ വീക്ഷണകോണിൽ നിന്ന്, മുന്നോട്ട് പോകാൻ രണ്ട് വഴികളുണ്ട്. ആദ്യത്തെ സമീപനത്തെ ഇറ്ററേറ്റീവ് ഡീപ്പനിംഗ് എന്ന് വിളിക്കുന്നു. ഇത് ഇപ്രകാരമാണ്: ഉത്തരത്തിന് താഴെ നിന്ന് ന്യായമായ ചില നിയന്ത്രണങ്ങൾ ഉപയോഗിച്ച് നമുക്ക് ആരംഭിക്കാം, തുടർന്ന് ഈ പരിമിതിയെക്കാൾ ആവർത്തനത്തിൽ താഴേക്ക് പോകാതെ, മുകളിൽ നിന്നുള്ള ഉത്തരത്തിന് ഒരു നിയന്ത്രണമായി ഈ പരിമിതിയെ ഉപയോഗിച്ച് ഞങ്ങളുടെ അൽഗോരിതം പ്രവർത്തിപ്പിക്കാം. ഞങ്ങൾ എന്തെങ്കിലും ഉത്തരം കണ്ടെത്തിയാൽ, അത് ഒപ്റ്റിമൽ ആണെന്ന് ഉറപ്പുനൽകുന്നു, അല്ലാത്തപക്ഷം നമുക്ക് ഈ പരിധി ഒന്ന് കൂട്ടി വീണ്ടും ആരംഭിക്കാം.

നിലവിലുള്ള ചില ഒപ്റ്റിമൽ ഉത്തരം സംഭരിച്ച് ചെറിയ ഉത്തരത്തിനായി നോക്കുക, കണ്ടെത്തുമ്പോൾ ഈ പാരാമീറ്റർ മാറ്റുക എന്നതാണ് മറ്റൊരു സമീപനം k തിരയലിൽ അനാവശ്യമായ ശാഖകൾ വെട്ടിമാറ്റുന്നതിന്.

നിരവധി രാത്രി പരീക്ഷണങ്ങൾ നടത്തിയതിന് ശേഷം, ഈ രണ്ട് രീതികളുടെ സംയോജനത്തിൽ ഞാൻ സ്ഥിരതാമസമാക്കി: ആദ്യം, തിരയൽ ആഴത്തിൽ ഒരു പരിധിവരെ ഞാൻ എന്റെ അൽഗോരിതം പ്രവർത്തിപ്പിക്കുന്നു (പ്രധാന പരിഹാരവുമായി താരതമ്യപ്പെടുത്തുമ്പോൾ ഇത് തിരഞ്ഞെടുക്കുന്നതിന് വളരെ കുറച്ച് സമയമെടുക്കും) മികച്ചത് ഉപയോഗിക്കുക. ഉത്തരത്തിനുള്ള ഉയർന്ന പരിധിയായി പരിഹാരം കണ്ടെത്തി - അതായത്, അതേ കാര്യത്തിന് k.

ഡിഗ്രി 2 ന്റെ ശീർഷകങ്ങൾ

ഡിഗ്രി 0, 1 എന്നിവയുടെ ശീർഷകങ്ങൾ ഞങ്ങൾ കൈകാര്യം ചെയ്തിട്ടുണ്ട്. ഡിഗ്രി 2 ന്റെ ശീർഷകങ്ങൾ ഉപയോഗിച്ച് ഇത് ചെയ്യാൻ കഴിയുമെന്ന് ഇത് മാറുന്നു, എന്നാൽ ഇതിന് ഗ്രാഫിൽ നിന്ന് കൂടുതൽ സങ്കീർണ്ണമായ പ്രവർത്തനങ്ങൾ ആവശ്യമാണ്.

ഇത് വിശദീകരിക്കാൻ, നമുക്ക് എങ്ങനെയെങ്കിലും ലംബങ്ങൾ നിശ്ചയിക്കേണ്ടതുണ്ട്. ഡിഗ്രി 2 ന്റെ ഒരു ശീർഷകത്തെ നമുക്ക് ശീർഷകം എന്ന് വിളിക്കാം v, അതിന്റെ അയൽക്കാർ - vertices x и y. അടുത്തതായി നമുക്ക് രണ്ട് കേസുകൾ ഉണ്ടാകും.

1. എപ്പോൾ x и y - അയൽക്കാർ. അപ്പോൾ നിങ്ങൾക്ക് ഉത്തരം നൽകാം x и yഒപ്പം v ഇല്ലാതാക്കുക. തീർച്ചയായും, ഈ ത്രികോണത്തിൽ നിന്ന് കുറഞ്ഞത് രണ്ട് ലംബങ്ങളെങ്കിലും എടുക്കേണ്ടതുണ്ട്, ഞങ്ങൾ എടുത്താൽ തീർച്ചയായും നഷ്ടപ്പെടില്ല x и y: അവർക്ക് ഒരുപക്ഷേ മറ്റ് അയൽക്കാർ ഉണ്ടായിരിക്കാം, കൂടാതെ v അവർ ഇവിടെ ഇല്ല.
2. എപ്പോൾ x и y - അയൽക്കാരല്ല. അപ്പോൾ മൂന്ന് ശീർഷകങ്ങളും ഒന്നായി ഒട്ടിക്കാൻ കഴിയുമെന്ന് പ്രസ്താവിക്കുന്നു. ഈ സാഹചര്യത്തിൽ ഒരു സമുചിതമായ ഉത്തരം ഉണ്ടെന്നാണ് ആശയം, അതിൽ ഞങ്ങൾ ഒന്നുകിൽ എടുക്കും v, അല്ലെങ്കിൽ രണ്ട് ലംബങ്ങളും x и y. മാത്രമല്ല, ആദ്യ സന്ദർഭത്തിൽ ഞങ്ങൾ എല്ലാ അയൽക്കാരെയും പ്രതികരണമായി എടുക്കേണ്ടിവരും x и y, എന്നാൽ രണ്ടാമത്തേതിൽ അത് ആവശ്യമില്ല. പ്രതികരണമായി ഒട്ടിച്ച ശീർഷകം എടുക്കാതിരിക്കുമ്പോഴും ഞങ്ങൾ എടുക്കുമ്പോഴും ഇത് കൃത്യമായി യോജിക്കുന്നു. രണ്ട് സാഹചര്യങ്ങളിലും അത്തരമൊരു പ്രവർത്തനത്തിൽ നിന്നുള്ള പ്രതികരണം ഒന്നായി കുറയുന്നു എന്നത് ശ്രദ്ധിക്കേണ്ടതാണ്.

ന്യായമായ രേഖീയ സമയത്ത് ഈ സമീപനം കൃത്യമായി നടപ്പിലാക്കാൻ വളരെ ബുദ്ധിമുട്ടാണ് എന്നത് ശ്രദ്ധിക്കേണ്ടതാണ്. ലംബങ്ങൾ ഒട്ടിക്കുന്നത് ഒരു സങ്കീർണ്ണ പ്രവർത്തനമാണ്; നിങ്ങൾ അയൽക്കാരുടെ പട്ടികകൾ പകർത്തേണ്ടതുണ്ട്. ഇത് അശ്രദ്ധമായി ചെയ്യുകയാണെങ്കിൽ, നിങ്ങൾക്ക് അസിംപ്റ്റിക്കലി സബ്പ്റ്റിമൽ റണ്ണിംഗ് ടൈം ഉപയോഗിച്ച് അവസാനിപ്പിക്കാം (ഉദാഹരണത്തിന്, ഓരോ ഒട്ടിച്ചതിന് ശേഷവും നിങ്ങൾ ധാരാളം അരികുകൾ പകർത്തുകയാണെങ്കിൽ). ഡിഗ്രി 2 ന്റെ ശീർഷകങ്ങളിൽ നിന്ന് മുഴുവൻ പാതകളും കണ്ടെത്തുന്നതിലും ഒരു കൂട്ടം പ്രത്യേക കേസുകൾ വിശകലനം ചെയ്യുന്നതിലും ഞാൻ തീരുമാനിച്ചു.

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

ലീനിയർ കേർണൽ

അവസാനമായി, കേർണലിന്റെ ഏറ്റവും രസകരമായ ഭാഗം.

ആരംഭിക്കുന്നതിന്, ബൈപാർട്ടൈറ്റ് ഗ്രാഫുകളിൽ ഏറ്റവും കുറഞ്ഞ വെർട്ടെക്സ് കവർ ഉപയോഗിച്ച് കണ്ടെത്താൻ കഴിയുമെന്ന് ഓർക്കുക . ഇത് ചെയ്യുന്നതിന്, നിങ്ങൾ അൽഗോരിതം ഉപയോഗിക്കേണ്ടതുണ്ട് ഹോപ്ക്രോഫ്റ്റ്-കാർപ്പ് അവിടെ പരമാവധി പൊരുത്തം കണ്ടെത്തുന്നതിന്, തുടർന്ന് സിദ്ധാന്തം ഉപയോഗിക്കുക കോനിഗ്-എഗർവാരി.

ഒരു ലീനിയർ കേർണലിന്റെ ആശയം ഇതാണ്: ആദ്യം നമ്മൾ ഗ്രാഫ് വിഭജിക്കുന്നു, അതായത്, ഓരോ ശീർഷത്തിനും പകരം v നമുക്ക് രണ്ട് കൊടുമുടികൾ ചേർക്കാം и , കൂടാതെ ഓരോ അരികിനും പകരം u - v നമുക്ക് രണ്ട് വാരിയെല്ലുകൾ ചേർക്കാം и . തത്ഫലമായുണ്ടാകുന്ന ഗ്രാഫ് ബൈപാർട്ടൈറ്റ് ആയിരിക്കും. അതിൽ ഏറ്റവും കുറഞ്ഞ വെർട്ടെക്സ് കവർ നമുക്ക് കണ്ടെത്താം. യഥാർത്ഥ ഗ്രാഫിന്റെ ചില ശീർഷകങ്ങൾ രണ്ടുതവണ അവിടെ എത്തും, ചിലത് ഒരിക്കൽ മാത്രം, ചിലത് ഒരിക്കലും. ഈ സാഹചര്യത്തിൽ ഒരാൾക്ക് ഒരിക്കൽ പോലും അടിക്കാത്ത ശീർഷകങ്ങൾ നീക്കം ചെയ്യാമെന്നും രണ്ടുതവണ തട്ടിയവ തിരിച്ചെടുക്കാമെന്നും നെംഹൗസർ-ട്രോട്ടർ സിദ്ധാന്തം പറയുന്നു. മാത്രമല്ല, ശേഷിക്കുന്ന ലംബങ്ങളിൽ (ഒരിക്കൽ അടിച്ചവ) നിങ്ങൾ പകുതിയെങ്കിലും ഉത്തരമായി എടുക്കേണ്ടതുണ്ടെന്ന് അവൾ പറയുന്നു.

അതിൽ കൂടുതൽ വിട്ടുപോകാൻ ഞങ്ങൾ പഠിച്ചിട്ടില്ല 2k കൊടുമുടികൾ തീർച്ചയായും, ബാക്കിയുള്ള ഉത്തരം എല്ലാ ലംബങ്ങളുടെയും പകുതിയെങ്കിലും ആണെങ്കിൽ, മൊത്തത്തിൽ കൂടുതൽ ലംബങ്ങളൊന്നുമില്ല. 2k.

ഇവിടെ എനിക്ക് ഒരു ചെറിയ ചുവടുവെപ്പ് മുന്നോട്ട് വയ്ക്കാൻ കഴിഞ്ഞു. ഈ രീതിയിൽ നിർമ്മിച്ച കേർണൽ ബൈപാർട്ടൈറ്റ് ഗ്രാഫിൽ ഞങ്ങൾ ഏത് തരം മിനിമൽ വെർട്ടെക്സ് കവർ എടുത്തു എന്നതിനെ ആശ്രയിച്ചിരിക്കുന്നു എന്നത് വ്യക്തമാണ്. ശേഷിക്കുന്ന ലംബങ്ങളുടെ എണ്ണം വളരെ കുറവായിരിക്കാൻ ഒരെണ്ണം എടുക്കാൻ ഞാൻ ആഗ്രഹിക്കുന്നു. മുമ്പ്, അവർക്ക് ഇത് കൃത്യസമയത്ത് മാത്രമേ ചെയ്യാൻ കഴിയൂ . ഈ അൽഗോരിതം നടപ്പിലാക്കാൻ ഞാൻ ആ സമയത്താണ് വന്നത് , അങ്ങനെ, ഓരോ ബ്രാഞ്ചിംഗ് ഘട്ടത്തിലും ലക്ഷക്കണക്കിന് ലംബങ്ങളുടെ ഗ്രാഫുകളിൽ ഈ കാമ്പ് തിരയാൻ കഴിയും.

ഫലം

നൂറുകണക്കിന് വെർട്ടീസുകളുടെയും ആയിരക്കണക്കിന് അരികുകളുടെയും പരിശോധനകളിൽ എന്റെ പരിഹാരം നന്നായി പ്രവർത്തിക്കുന്നുവെന്ന് പ്രാക്ടീസ് കാണിക്കുന്നു. അത്തരം പരിശോധനകളിൽ അരമണിക്കൂറിനുള്ളിൽ ഒരു പരിഹാരം കാണുമെന്ന് പ്രതീക്ഷിക്കുന്നത് തികച്ചും സാദ്ധ്യമാണ്. ഗ്രാഫിന് ഉയർന്ന ഡിഗ്രിയുടെ ആവശ്യത്തിന് വലിയ അളവുകൾ ഉണ്ടെങ്കിൽ, തത്വത്തിൽ, സ്വീകാര്യമായ സമയത്ത് ഉത്തരം കണ്ടെത്താനുള്ള സാധ്യത വർദ്ധിക്കുന്നു, ഉദാഹരണത്തിന്, ഡിഗ്രി 10 ഉം ഉയർന്നതും.

മത്സരത്തിൽ പങ്കെടുക്കാൻ, പരിഹാരങ്ങൾ അയയ്‌ക്കേണ്ടതായിരുന്നു optil.io. അവിടെ അവതരിപ്പിച്ച വിവരങ്ങളാൽ വിലയിരുത്തപ്പെടുന്നു അടയാളം, ഓപ്പൺ ടെസ്റ്റുകളിലെ എന്റെ സൊല്യൂഷൻ ഇരുപതിൽ മൂന്നാം സ്ഥാനത്താണ്, രണ്ടാമത്തേതിൽ നിന്ന് വലിയ വിടവ്. പൂർണ്ണമായും സത്യസന്ധമായി പറഞ്ഞാൽ, മത്സരത്തിൽ തന്നെ പരിഹാരങ്ങൾ എങ്ങനെ വിലയിരുത്തപ്പെടും എന്നത് പൂർണ്ണമായും വ്യക്തമല്ല: ഉദാഹരണത്തിന്, എന്റെ പരിഹാരം നാലാം സ്ഥാനത്തുള്ള പരിഹാരത്തേക്കാൾ കുറച്ച് പരിശോധനകളിൽ വിജയിക്കുന്നു, എന്നാൽ വിജയിക്കുന്നവയിൽ ഇത് വേഗത്തിൽ പ്രവർത്തിക്കുന്നു.

ക്ലോസ്ഡ് ടെസ്റ്റുകളുടെ ഫലം ജൂലൈ ഒന്നിന് അറിയാം.

അവലംബം: www.habr.com