පරාමිතික ඇල්ගොරිතම සමඟ NP-දැඩි ගැටළු විසඳන්නේ කෙසේද

පර්යේෂණ කටයුතු සමහර විට අපගේ පුහුණුවේ වඩාත්ම සිත්ගන්නා කොටස විය හැකිය. අදහස වන්නේ විශ්ව විද්‍යාලයේ සිටියදී ඔබ තෝරාගත් දිශාවට ඔබම උත්සාහ කිරීමයි. උදාහරණයක් ලෙස, මෘදුකාංග ඉංජිනේරු සහ යන්ත්‍ර ඉගෙනීමේ ක්ෂේත්‍රවල සිසුන් බොහෝ විට සමාගම්වල පර්යේෂණ කිරීමට යයි (ප්‍රධාන වශයෙන් JetBrains හෝ Yandex, නමුත් පමණක් නොවේ).

මෙම ලිපියෙන් මම පරිගණක විද්‍යාව පිළිබඳ මගේ ව්‍යාපෘතිය ගැන කතා කරමි. මගේ කාර්යයේ කොටසක් ලෙස, මම වඩාත් ප්‍රසිද්ධ NP-දෘඩ ගැටළු විසඳීම සඳහා ප්‍රවේශයන් අධ්‍යයනය කර ප්‍රායෝගිකව ක්‍රියාත්මක කළෙමි: සිරස් ආවරණ ගැටළුව.

වර්තමානයේ, NP-දෘඩ ගැටළු සඳහා සිත්ගන්නා ප්රවේශයක් ඉතා ඉක්මනින් වර්ධනය වෙමින් පවතී - පරාමිතික ඇල්ගොරිතම. මම ඔබව වේගවත් කිරීමට උත්සාහ කරමි, ඔබට සරල පරාමිති ඇල්ගොරිතම කිහිපයක් කියන්න සහ මට බොහෝ උපකාර කළ එක් බලවත් ක්‍රමයක් විස්තර කරන්න. මම PACE අභියෝගතා තරඟයේදී මගේ ප්‍රතිඵල ඉදිරිපත් කළෙමි: විවෘත පරීක්ෂණවල ප්‍රතිඵලවලට අනුව, මගේ විසඳුම තුන්වන ස්ථානයට පත්වන අතර, අවසාන ප්‍රතිඵලය ජූලි 1දා දැනගත හැක.

මම ගැන

මගේ නම Vasily Alferov, මම දැන් ජාතික පර්යේෂණ විශ්ව විද්‍යාලයේ උසස් ආර්ථික විද්‍යා පාසලේ - ශාන්ත පීටර්ස්බර්ග් හි මගේ තුන්වන වසර අවසන් කරමි. මම මොස්කව් පාසලේ අංක 179 හි අධ්‍යාපනය ලැබූ අතර පරිගණක විද්‍යා ඔලිම්පියාඩ් වලට සාර්ථකව සහභාගී වූ විට මගේ පාසල් කාලයේ සිටම ඇල්ගොරිතම ගැන මම උනන්දු වෙමි.

පරාමිතික ඇල්ගොරිතම වල සීමිත විශේෂඥයින් පිරිසක් තීරුවට ඇතුළු වේ...

පොතෙන් උපුටා ගත් උදාහරණය "පරාමිතික ඇල්ගොරිතම"

ඔබ කුඩා නගරයක බාර් ආරක්ෂක නිලධාරියෙක් යැයි සිතන්න. සෑම සිකුරාදා දිනකම, නගරයෙන් අඩක් විවේක ගැනීම සඳහා ඔබේ බාර්එක වෙත පැමිණේ, එය ඔබට බොහෝ කරදර ඇති කරයි: රණ්ඩු වැලැක්වීම සඳහා ඔබ කලබලකාරී ගනුදෙනුකරුවන් බාර්එකෙන් ඉවතට විසි කළ යුතුය. අවසානයේදී, ඔබ පෝෂණය වන අතර වැළැක්වීමේ පියවර ගැනීමට තීරණය කරයි.

ඔබේ නගරය කුඩා බැවින්, ඔවුන් එකට බාර් එකකට ගියහොත් සටන් කිරීමට ඉඩ ඇති අනුග්‍රාහක යුගල මොනවාදැයි ඔබ හරියටම දන්නවා. ඔබට ලැයිස්තුවක් තිබේද? n අද රෑ බාර් එකට එන මිනිස්සු. කිසිවෙකු රණ්ඩුවකට නොපැමිණෙන පරිදි සමහර නගර වැසියන් බාර්එකෙන් පිටත තබා ගැනීමට ඔබ තීරණය කරයි. ඒ අතරම, ඔබේ ලොක්කන්ට ලාභ අහිමි වීමට අවශ්‍ය නැති අතර ඔබ ඊට වඩා ඉඩ නොදුන්නේ නම් අසතුටට පත් වනු ඇත. k මානව.

අවාසනාවකට, ඔබ ඉදිරියේ ඇති ගැටලුව සම්භාව්‍ය NP-දෘඪ ගැටලුවකි. ඔබ ඇයව හඳුනනවා විය හැකිය වර්ටෙක්ස් කවරය, හෝ සිරස් ආවරණ ගැටළුවක් ලෙස. එවැනි ගැටළු සඳහා, සාමාන්ය නඩුවේදී, පිළිගත හැකි කාලය තුළ ක්රියා කරන ඇල්ගොරිතම නොමැත. නිවැරදිව කිවහොත්, ඔප්පු නොකළ සහ තරමක් ශක්තිමත් කල්පිතය ETH (Exponential Time Hypothesis) පවසන්නේ මෙම ගැටලුව නියමිත වේලාවට විසඳිය නොහැකි බවයි. , එනම්, ඔබට සම්පූර්ණ සෙවුමකට වඩා සැලකිය යුතු දෙයක් ගැන සිතිය නොහැක. උදාහරණයක් විදියට අපි හිතමු කෙනෙක් ඔයාගේ බාර් එකට එනවා කියලා n = 1000 මානව. එවිට සම්පූර්ණ සෙවුම වනු ඇත ආසන්න වශයෙන් පවතින විකල්ප - පිස්සු මුදල. වාසනාවකට මෙන්, ඔබේ කළමනාකරණය ඔබට සීමාවක් ලබා දී ඇත k = 10, එබැවින් ඔබට පුනරාවර්තනය කිරීමට අවශ්‍ය සංයෝජන සංඛ්‍යාව වඩා කුඩා වේ: මූලද්‍රව්‍ය දහයක උප කුලක ගණන . මෙය වඩා හොඳයි, නමුත් එය තවමත් බලවත් පොකුරක් මත පවා දිනක් තුළ ගණන් නොගනු ඇත.

බාර්එක අමුත්තන් අතර ඇති දැඩි සම්බන්ධතා මෙම වින්‍යාසය තුළ ගැටුමක් ඇතිවීමේ හැකියාව ඉවත් කිරීම සඳහා, ඔබ බොබ්, ඩැනියෙල් සහ ෆෙඩෝර්ව ඉවත් කර තැබිය යුතුය. දෙදෙනෙකු පමණක් ඉතිරි වන විසඳුමක් නොමැත.

මෙයින් අදහස් කරන්නේ සියල්ලන්ටම ඉඩ දීමට කාලය පැමිණ ඇති බව ද? වෙනත් විකල්ප සලකා බලමු. හොඳයි, උදාහරණයක් ලෙස, ඔබට ඉතා විශාල පිරිසක් සමඟ සටන් කිරීමට ඉඩ ඇති අයට පමණක් ඉඩ දිය නොහැක. අඩුම තරමේ රණ්ඩු කරන්න පුළුවන් කෙනෙක් ඉන්නවා නම් k+1 වෙනත් පුද්ගලයෙක්, එවිට ඔබට අනිවාර්යයෙන්ම ඔහුට ඇතුලට යාමට ඉඩ දිය නොහැක - එසේ නොමැතිනම් ඔබට සියල්ලන්ම පිටත තබා ගැනීමට සිදුවනු ඇත k+1 ඔහුට සටන් කළ හැකි නගර වැසියන්, එය නිසැකවම නායකත්වය අවුල් කරනු ඇත.

මෙම මූලධර්මය අනුව ඔබට හැකි සෑම කෙනෙකුම ඉවත දැමීමට ඔබට ඉඩ දෙන්න. එවිට අන් සියල්ලන්ට වඩා වැඩි යමක් නොමැතිව සටන් කළ හැකිය k මහජන. ඒවා එළියට විසි කරනවා k මිනිසා, ඔබට ඊට වඩා දෙයක් වළක්වා ගත නොහැක ගැටුම්. මෙයින් අදහස් කරන්නේ වඩා වැඩි නම් පුද්ගලයෙකු අවම වශයෙන් එක් ගැටුමකට සම්බන්ධ නම්, ඔබට නිසැකවම ඒවා සියල්ලම වළක්වා ගත නොහැක. ඇත්ත වශයෙන්ම, ඔබ නියත වශයෙන්ම සම්පූර්ණයෙන්ම ගැටුම් නොවන පුද්ගලයින්ට ඇතුළු වීමට ඉඩ දෙන බැවින්, ඔබ දෙසිය දෙනෙකුගෙන් දහයක ප්‍රමාණයේ සියලුම උප කුලක හරහා යා යුතුය. ආසන්න වශයෙන් ඇත , සහ මෙම මෙහෙයුම් ගණන දැනටමත් පොකුර මත වර්ග කළ හැක.

ඔබට කිසිඳු ගැටුමක් නොමැති පුද්ගලයින් ආරක්ෂිතව රැගෙන යා හැකි නම්, එක් ගැටුමකට පමණක් සහභාගී වන අය ගැන කුමක් කිව හැකිද? ඇත්ත වශයෙන්ම, ඔවුන්ගේ විරුද්ධවාදියාට දොර වැසීමෙන් ඔවුන්ට ඇතුළු විය හැකිය. ඇත්ත වශයෙන්ම, ඇලිස් ගැටෙන්නේ බොබ් සමඟ පමණක් නම්, අපි ඔවුන් දෙදෙනාගෙන් ඇලිස්ට ඉඩ දුන්නොත්, අපට අහිමි නොවනු ඇත: බොබ්ට වෙනත් ගැටුම් තිබිය හැකිය, නමුත් ඇලිස්ට නිසැකවම ඒවා නොමැත. අනික අපි දෙන්නටම ඇතුලට යන්න නොදී තේරුමක් නෑ. එවැනි මෙහෙයුම් වලින් පසුව තවත් ඉතිරි නොවේ නොවිසඳුණු ඉරණමක් සහිත අමුත්තන්: අපට ඇත්තේ පමණි ගැටුම්, එක් එක් සහභාගිවන්නන් දෙදෙනෙකු සිටින අතර එක් එක් අවම වශයෙන් දෙදෙනෙකුට සම්බන්ධ වේ. එබැවින් ඉතිරිව ඇත්තේ නිරාකරණය කිරීම පමණි විකල්ප, ලැප්ටොප් එකක දින භාගයක් පහසුවෙන් සැලකිය හැකිය.

ඇත්ත වශයෙන්ම, සරල තර්කනයකින් ඔබට වඩාත් ආකර්ෂණීය තත්වයන් ලබා ගත හැකිය. අපි අනිවාර්යයෙන්ම සියලු ආරවුල් විසඳීමට අවශ්‍ය බව සලකන්න, එනම්, එක් එක් පරස්පර යුගලයෙන්, අපි ඇතුළු වීමට ඉඩ නොදෙන අවම වශයෙන් එක් පුද්ගලයෙකු තෝරා ගන්න. අපි පහත ඇල්ගොරිතම සලකා බලමු: ඕනෑම ගැටුමක් ගන්න, එයින් අපි එක් සහභාගිවන්නෙකු ඉවත් කර ප්‍රත්‍යාවර්තීව ඉතිරියෙන් පටන් ගනිමු, පසුව අනෙකා ඉවත් කර ප්‍රත්‍යාවර්තීව ආරම්භ කරමු. අපි සෑම පියවරකදීම යමෙකු ඉවතට විසි කරන බැවින්, එවැනි ඇල්ගොරිතමයක පුනරාවර්තන ගස ගැඹුරේ ද්විමය ගසකි. k, එබැවින් සමස්තයක් ලෙස ඇල්ගොරිතම ක්‍රියා කරයි කොහෙද n යනු සිරස් ගණන, සහ m - ඉළ ඇට ගණන. අපගේ උදාහරණයේ දී, මෙය මිලියන දහයක් පමණ වන අතර, එය ලැප්ටොප් එකක පමණක් නොව, ජංගම දුරකථනයක පවා තත්පරයකට බෙදිය හැකිය.

ඉහත උදාහරණය උදාහරණයකි පරාමිතික ඇල්ගොරිතම. පරාමිතික ඇල්ගොරිතම යනු නියමිත වේලාවට ක්‍රියාත්මක වන ඇල්ගොරිතම වේ f(k) poly(n)කොහෙද p - බහුපද, f අත්තනෝමතික ගණනය කළ හැකි කාර්යයකි, සහ k - සමහර පරාමිතිය, සමහර විට, ගැටලුවේ ප්රමාණයට වඩා බෙහෙවින් කුඩා වනු ඇත.

මෙම ඇල්ගොරිතමයට පෙර ඇති සියලුම තර්ක උදාහරණ සපයයි කර්නලීකරණය පරාමිතික ඇල්ගොරිතම නිර්මාණය කිරීම සඳහා පොදු තාක්ෂණික ක්රම වලින් එකකි. කර්නලීකරණය යනු පරාමිතියක ශ්‍රිතයකින් සීමා වූ අගයකට ගැටළු ප්‍රමාණය අඩු කිරීමයි. ප්රතිඵලයක් වශයෙන් ගැටළුව බොහෝ විට කර්නලයක් ලෙස හැඳින්වේ. මේ අනුව, සිරස්වල අංශක පිළිබඳ සරල තර්කනය මගින්, අපි උත්තරයේ ප්‍රමාණයෙන් පරාමිතිකරණය කරන ලද Vertex ආවරණ ගැටළුව සඳහා චතුරස්රාකාර කර්නලයක් ලබා ගත්තෙමු. මෙම කාර්යය සඳහා ඔබට තෝරා ගත හැකි වෙනත් සැකසුම් ඇත (LP ඉහත Vertex Cover වැනි), නමුත් අප සාකච්ඡා කරනු ලබන්නේ මෙයයි.

වේග අභියෝගය

තරඟ PACE අභියෝගය (The Parameterized Algorithms and Computational Experiments Challenge) 2015 දී උපත ලැබුවේ පරාමිතික ඇල්ගොරිතම සහ පරිගණක ගැටළු විසඳීම සඳහා ප්‍රායෝගිකව භාවිතා කරන ප්‍රවේශයන් අතර සම්බන්ධතාවයක් ඇති කර ගැනීම සඳහා ය. පළමු තරඟ තුන වෙන් කරන ලද්දේ ප්‍රස්ථාරයක ගස් පළල සෙවීම සඳහා ය (Treewidth), ස්ටයිනර් ගසක් සොයමින් (ස්ටයිනර් ගස) සහ චක්‍ර කපා හරින සිරස් කට්ටලයක් සෙවීම (ප්‍රතිපෝෂණ වර්ටෙක්ස් කට්ටලය) මෙම වසරේ, ඔබට උත්සාහ කළ හැකි එක් ගැටළුවක් වූයේ ඉහත විස්තර කර ඇති සිරස් ආවරණ ගැටළුවයි.

තරඟය සෑම වසරකම ජනප්රිය වෙමින් පවතී. ඔබ මූලික දත්ත විශ්වාස කරන්නේ නම්, මෙම වසරේ කණ්ඩායම් 24 ක් ශීර්ෂ ආවරණය කිරීමේ ගැටලුව විසඳීම සඳහා තරඟයට සහභාගී විය. තරඟය පැය කිහිපයක් හෝ සතියක් නොව මාස කිහිපයක් පවතින බව සඳහන් කිරීම වටී. කණ්ඩායම්වලට සාහිත්‍යය අධ්‍යයනය කිරීමටත්, ඔවුන්ගේම මුල් අදහස ඉදිරිපත් කිරීමටත් එය ක්‍රියාත්මක කිරීමට උත්සාහ කිරීමටත් අවස්ථාව තිබේ. සාරාංශයක් ලෙස, මෙම තරඟය පර්යේෂණ ව්යාපෘතියකි. වඩාත් ඵලදායි විසඳුම් සඳහා අදහස් සහ ජයග්‍රාහකයින් ප්‍රදානය කිරීම සමුළුවට සමගාමීව සිදු කෙරේ IPEC (පරාමිතික සහ නිවැරදි ගණනය කිරීම් පිළිබඳ ජාත්‍යන්තර සම්මන්ත්‍රණය) යුරෝපයේ විශාලතම වාර්ෂික ඇල්ගොරිතම රැස්වීමේ කොටසක් ලෙස ALGO. තරඟය පිළිබඳ වඩාත් සවිස්තරාත්මක තොරතුරු මෙහි සොයාගත හැකිය වෙබ් අඩවිය, සහ පෙර වසරවල ප්රතිඵල බොරු මෙහි.

විසඳුම් රූප සටහන

සිරස් ආවරණ ගැටළුව විසඳීම සඳහා, මම පරාමිතික ඇල්ගොරිතම භාවිතා කිරීමට උත්සාහ කළෙමි. ඒවා සාමාන්‍යයෙන් කොටස් දෙකකින් සමන්විත වේ: සරල කිරීමේ නීති (ඉතා මැනවින් කර්නලීකරණයට තුඩු දෙන) සහ බෙදීමේ නීති. සරල කිරීමේ නීති යනු බහුපද කාලය තුළ ආදානය පෙර සැකසීමයි. එවැනි නීති යෙදීමේ අරමුණ වන්නේ ගැටලුව සමාන කුඩා ගැටලුවක් දක්වා අඩු කිරීමයි. සරල කිරීමේ නීති යනු ඇල්ගොරිතමයේ වඩාත්ම මිල අධික කොටස වන අතර, මෙම කොටස යෙදීමෙන් සම්පූර්ණ ධාවන කාලය ලැබේ. සරල බහුපද කාලය වෙනුවට. අපගේ නඩුවේදී, බෙදීමේ නීති පදනම් වී ඇත්තේ එක් එක් ශීර්ෂය සඳහා ඔබ එය හෝ එහි අසල්වැසියා පිළිතුරක් ලෙස ගත යුතුය යන කාරණය මත ය.

සාමාන්‍ය යෝජනා ක්‍රමය මෙයයි: අපි සරල කිරීමේ නීති රීති යොදන්නෙමු, පසුව අපි යම් ශීර්ෂයක් තෝරාගෙන පුනරාවර්තන ඇමතුම් දෙකක් කරන්නෙමු: පළමුව අපි එය ප්‍රතිචාර වශයෙන් ගන්නා අතර අනෙක අපි එහි සියලුම අසල්වැසියන් ගනිමු. මේකට තමයි අපි මේ ශීර්ෂය දිගේ බෙදීම (අතු බෙදීම) කියන්නේ.

ඊළඟ ඡේදයේ මෙම යෝජනා ක්රමයට හරියටම එක් එකතු කිරීමක් සිදු කෙරේ.

බෙදීමේ (bunching) නීති සඳහා අදහස්

බෙදීම සිදු වන ශීර්ෂයක් තෝරා ගන්නේ කෙසේදැයි සාකච්ඡා කරමු.
ප්‍රධාන අදහස ඇල්ගොරිතම අර්ථයෙන් ඉතා කෑදර ය: අපි උපරිම උපාධියේ ශීර්ෂයක් ගෙන එය දිගේ බෙදමු. එය වඩා හොඳ යැයි පෙනෙන්නේ ඇයි? මොකද recursive call එකේ දෙවෙනි ශාඛාවේදී අපි මේ විදියට vertices ගොඩක් අයින් කරනවා. ඔබට ඉතිරිව ඇති කුඩා ප්‍රස්ථාරයක් මත ගණන් ගත හැකි අතර අපට එය ඉක්මනින් වැඩ කළ හැක.

දැනටමත් සාකච්ඡා කර ඇති සරල කර්නලකරණ ශිල්පීය ක්‍රම සමඟින් මෙම ප්‍රවේශය හොඳින් පෙන්නුම් කරන අතර ප්‍රමාණයේ සිරස් දහස් ගණනක පරීක්ෂණ කිහිපයක් විසඳයි. නමුත්, උදාහරණයක් ලෙස, ඝන ප්‍රස්ථාර සඳහා එය හොඳින් ක්‍රියා නොකරයි (එනම්, එක් එක් ශීර්ෂයේ අංශක තුනක් ඇති ප්‍රස්ථාර).
තරමක් සරල අදහසක් මත පදනම් වූ තවත් අදහසක් තිබේ: ප්රස්ථාරය විසන්ධි කර ඇත්නම්, එහි සම්බන්ධිත සංරචක මත ගැටළුව ස්වාධීනව විසඳා ගත හැකිය, අවසානයේ පිළිතුරු ඒකාබද්ධ කිරීම. මෙය, මාර්ගය වන විට, යෝජනා ක්‍රමයේ කුඩා පොරොන්දු වූ වෙනස් කිරීමකි, එය විසඳුම සැලකිය යුතු ලෙස වේගවත් කරනු ඇත: මීට පෙර, මෙම අවස්ථාවේ දී, අපි සංරචකවල ප්‍රතිචාර ගණනය කිරීම සඳහා කාලවල නිෂ්පාදිතය සඳහා වැඩ කළෙමු, නමුත් දැන් අපි වැඩ කරන්නේ එකතුව. සහ අතු බෙදීම වේගවත් කිරීම සඳහා, ඔබ සම්බන්ධිත ප්‍රස්ථාරයක් විසන්ධි වූ එකක් බවට පත් කළ යුතුය.

එය කරන්නේ කෙසේද? ප්‍රස්ථාරයේ උච්චාරණ ලක්ෂ්‍යයක් තිබේ නම්, ඔබ එයට සටන් කළ යුතුය. උච්චාරණ ලක්ෂ්‍යයක් යනු ඉවත් කළ විට ප්‍රස්ථාරය එහි සම්බන්ධතාවය නැති වන පරිදි ශීර්ෂයකි. ප්‍රස්ථාරයක ඇති සියලුම සන්ධිස්ථාන රේඛීය වේලාවේ සම්භාව්‍ය ඇල්ගොරිතමයක් භාවිතයෙන් සොයා ගත හැක. මෙම ප්රවේශය අතු බෙදීම සැලකිය යුතු ලෙස වේගවත් කරයි.

තෝරාගත් ඕනෑම ශීර්ෂයක් ඉවත් කළ විට, ප්‍රස්ථාරය සම්බන්ධිත සංරචක වලට බෙදී යයි.

අපි මෙය කරන්නෙමු, නමුත් අපට තවත් අවශ්යයි. උදාහරණයක් ලෙස, ප්‍රස්ථාරයේ කුඩා සිරස් කැපීම් සොයන්න සහ එයින් සිරස් දිගේ බෙදන්න. අවම ගෝලීය ශීර්ෂ කප්පාදුව සොයා ගැනීමට මා දන්නා වඩාත්ම කාර්යක්ෂම ක්‍රමය නම් ඝන කාලය තුළ ගොඩනගා ඇති Gomori-Hu ගසක් භාවිතා කිරීමයි. PACE අභියෝගය තුළ, සාමාන්‍ය ප්‍රස්ථාර ප්‍රමාණය සිරස් දහස් ගණනකි. මෙම තත්වය තුළ, පුනරාවර්තන ගසේ එක් එක් ශීර්ෂය තුළ මෙහෙයුම් බිලියන ගණනක් සිදු කළ යුතුය. නියමිත කාලය තුළ ගැටලුව විසඳීමට නොහැකි බව පෙනී යයි.

විසඳුම ප්‍රශස්ත කිරීමට උත්සාහ කරමු. උපරිම ප්‍රවාහයක් ගොඩනඟන ඕනෑම ඇල්ගොරිතමයක් මඟින් සිරස් යුගලයක් අතර කපා ඇති අවම ශීර්ෂය සොයාගත හැකිය. ඔබට එය එවැනි ජාලයකට ඉඩ දිය හැකිය Dinitz ඇල්ගොරිතම, ප්රායෝගිකව එය ඉතා ඉක්මනින් ක්රියා කරයි. මෙහෙයුම් කාලය සඳහා ඇස්තමේන්තුවක් ඔප්පු කිරීමට න්‍යායාත්මකව හැකිදැයි මට සැකයක් ඇත , දැනටමත් බෙහෙවින් පිළිගත හැකි ය.

අහඹු සිරස් යුගල අතර කැපුම් සෙවීමට සහ වඩාත්ම සමතුලිත එකක් ගැනීමට මම කිහිප වතාවක්ම උත්සාහ කළෙමි. අවාසනාවන්ත ලෙස, මෙය විවෘත PACE අභියෝගතා පරීක්‍ෂණයේ දුර්වල ප්‍රතිඵල ඇති කළේය. මම එය උපරිම මට්ටමේ සිරස් බෙදන ඇල්ගොරිතමයක් සමඟ සංසන්දනය කළෙමි, ඒවා බැසීමේ ගැඹුරේ සීමාවක් සහිතව ධාවනය කළෙමි. මේ ආකාරයෙන් කැපුමක් සෙවීමට උත්සාහ කරන ඇල්ගොරිතමයක් විශාල ප්‍රස්ථාර පිටුපස ඉතිරි වේ. මෙයට හේතුව කප්පාදුව ඉතා අසමතුලිත වීමයි: සිරස් 5-10 ක් ඉවත් කිරීමෙන් පසුව බෙදීමට හැකි වූයේ 15-20 ක් පමණි.

න්‍යායාත්මකව වේගවත්ම ඇල්ගොරිතම පිළිබඳ ලිපි බෙදීම සඳහා සිරස් තෝරා ගැනීම සඳහා වඩාත් දියුණු තාක්ෂණික ක්‍රම භාවිතා කරන බව සඳහන් කිරීම වටී. එවැනි ශිල්පීය ක්‍රම ඉතා සංකීර්ණ ක්‍රියාත්මක කිරීමක් සහ කාලය සහ මතකය අනුව බොහෝ විට දුර්වල ක්‍රියාකාරිත්වයක් ඇත. පුහුණුව සඳහා බෙහෙවින් පිළිගත හැකි ඒවා හඳුනා ගැනීමට මට නොහැකි විය.

සරල කිරීමේ නීති යෙදිය යුතු ආකාරය

කර්නලීකරණය සඳහා අපට දැනටමත් අදහස් තිබේ. මම ඔබට මතක් කරන්නම්:

1. හුදකලා ශීර්ෂයක් තිබේ නම්, එය මකා දමන්න.
2. අංශක 1 හි ශීර්ෂයක් තිබේ නම්, එය ඉවත් කර ප්රතිචාර වශයෙන් එහි අසල්වැසියා ගන්න.
3. අවම වශයෙන් උපාධියේ ශීර්ෂයක් තිබේ නම් k+1, එය ආපසු ගන්න.

පළමු දෙක සමඟ සෑම දෙයක්ම පැහැදිලිය, තුන්වැන්න සමඟ එක් උපක්රමයක් තිබේ. බාර් එකක් ගැන කොමික් ප්‍රශ්නයක් නම් අපිට ඉහළ සීමාවක් දුන්නා k, පසුව PACE Challenge හි ඔබට අවශ්‍ය වන්නේ අවම ප්‍රමාණයේ සිරස් ආවරණයක් සොයා ගැනීමයි. මෙය සෙවුම් ගැටළු තීරණ ගැනීමේ ගැටළු බවට සාමාන්‍ය පරිවර්තනයකි; බොහෝ විට ගැටළු වර්ග දෙක අතර වෙනසක් නොමැත. ප්‍රායෝගිකව, අපි සිරස් ආවරණ ගැටලුව සඳහා විසඳුම් ලියන්නේ නම්, වෙනසක් තිබිය හැකිය. උදාහරණයක් ලෙස, තුන්වන කරුණෙහි මෙන්.

ක්රියාත්මක කිරීමේ දෘෂ්ටි කෝණයෙන්, ඉදිරියට යාමට ක්රම දෙකක් තිබේ. පළමු ප්රවේශය පුනරාවර්තන ගැඹුරු කිරීම ලෙස හැඳින්වේ. එය පහත පරිදි වේ: අපට පිළිතුරට පහළින් යම් සාධාරණ බාධාවකින් ආරම්භ කළ හැකි අතර, මෙම සීමාවට වඩා ප්‍රත්‍යාවර්තනයෙන් පහළට නොගොස්, ඉහතින් ලැබෙන පිළිතුරට බාධාවක් ලෙස මෙම බාධාව භාවිත කර අපගේ ඇල්ගොරිතම ක්‍රියාත්මක කළ හැක. අපි යම් පිළිතුරක් සොයා ගත්තා නම්, එය ප්රශස්ත බව සහතිකයි, එසේ නොමැතිනම් අපට මෙම සීමාව එකකින් වැඩි කර නැවත ආරම්භ කළ හැකිය.

තවත් ප්‍රවේශයක් වන්නේ වත්මන් ප්‍රශස්ත පිළිතුරක් ගබඩා කර කුඩා පිළිතුරක් සෙවීම, මෙම පරාමිතිය සොයාගත් විට වෙනස් කිරීමයි 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 හි සිරස් වලින් සම්පූර්ණ මාර්ග සොයා ගැනීම සහ එවැනි සිරස් වලින් චක්‍ර වැනි විශේෂ අවස්ථා සමූහයක් විශ්ලේෂණය කිරීම හෝ එකක් හැර එවැනි සියලුම සිරස් වලින් විශ්ලේෂණය කිරීම පිළිබඳව තීරණය කළෙමි.

මීට අමතරව, මෙම මෙහෙයුම ආපසු හැරවිය හැකි වීම අවශ්ය වේ, එසේ නම්, පුනරාවර්තනයෙන් ආපසු පැමිණෙන විට අපි ප්රස්ථාරය එහි මුල් ආකෘතියට ප්රතිෂ්ඨාපනය කරමු. මෙය සහතික කිරීම සඳහා, මම ඒකාබද්ධ කළ සිරස් වල දාර ලැයිස්තු ඉවත් නොකළ අතර, පසුව යා යුත්තේ කුමන දාරද යන්න මම දැන සිටියෙමි. මෙම ප්‍රස්ථාර ක්‍රියාත්මක කිරීම සඳහා නිරවද්‍යතාවයක් ද අවශ්‍ය වේ, නමුත් එය සාධාරණ රේඛීය කාලයක් සපයයි. දාර දස දහස් ගණනක ප්‍රස්ථාර සඳහා, එය ප්‍රොසෙසර හැඹිලියට ගැලපේ, එය වේගයෙන් විශාල වාසි ලබා දෙයි.

රේඛීය කර්නලය

අවසාන වශයෙන්, කර්නලයේ වඩාත්ම සිත්ගන්නා කොටස.

ආරම්භ කිරීමට, ද්විපාර්ශ්වික ප්‍රස්ථාරවල අවම ශීර්ෂ ආවරණයක් භාවිතා කළ හැකි බව මතක තබා ගන්න . මෙය සිදු කිරීම සඳහා ඔබ ඇල්ගොරිතම භාවිතා කළ යුතුය Hopcroft-Karp එහි ඇති උපරිම ගැලපීම සොයා ගැනීමට, පසුව ප්‍රමේයය භාවිතා කරන්න König-Egervari.

රේඛීය කර්නලය පිළිබඳ අදහස මෙයයි: පළමුව අපි ප්‍රස්ථාරය බෙදන්නෙමු, එනම් එක් එක් සිරස් වෙනුවට v අපි මුදුන් දෙකක් එකතු කරමු и , සහ එක් එක් දාරය වෙනුවට u - v අපි ඉළ ඇට දෙකක් එකතු කරමු и . ප්රතිඵලය වන ප්රස්ථාරය ද්විපාර්ශ්වික වනු ඇත. අපි එහි ඇති අවම ශීර්ෂ ආවරණය සොයා ගනිමු. මුල් ප්‍රස්ථාරයේ සමහර සිරස් දෙවතාවක් ලැබෙනු ඇත, සමහරක් එක් වරක් පමණක්, සමහරක් කිසිදා නොලැබේ. Nemhauser-Trotter theorem එකේ සඳහන් වෙනවා මේකෙදි එක පාරක්වත් වැදුනේ නැති vertices අයින් කරලා දෙපාරක් වැදුන ඒවා ආපහු ගන්න පුළුවන් කියලා. එපමණක් නොව, ඇය පවසන්නේ ඉතිරි සිරස් වලින් (එක් වරක් පහර දුන් ඒවා) ඔබ අවම වශයෙන් අඩක්වත් පිළිතුරක් ලෙස ගත යුතු බවයි.

ඊට වඩා යන්න එපා කියලා අපි ඉගෙනගෙන තියෙනවා 2k මුදුන් ඇත්ත වශයෙන්ම, ඉතිරි පිළිතුර අවම වශයෙන් සියලුම සිරස්වලින් අඩක් නම්, සමස්තයක් වශයෙන් ඊට වඩා වැඩි සිරස් නොමැත 2k.

මෙහිදී මට කුඩා පියවරක් ඉදිරියට තැබීමට හැකි විය. මේ ආකාරයෙන් ගොඩනගා ඇති කර්නලය ද්විපාර්ශ්වික ප්‍රස්ථාරයේ අප ගත් අවම ශීර්ෂ ආවරණයක් මත රඳා පවතින බව පැහැදිලිය. ඉතිරි සිරස් ගණන අවම වන පරිදි එකක් ගැනීමට මම කැමතියි. මීට පෙර, ඔවුන්ට මෙය කළ හැකි වූයේ නියමිත වේලාවට පමණි . මම කාලය තුළ මෙම ඇල්ගොරිතම ක්රියාත්මක කිරීමට ඉදිරිපත් විය , මේ අනුව, මෙම හරය එක් එක් ශාඛා අදියරේදී සිය දහස් ගණනක සිරස් ප්‍රස්ථාරවල සෙවිය හැක.

ප්රතිඵලය

ප්‍රායෝගිකව පෙන්නුම් කරන්නේ මගේ විසඳුම සිරස් සිය ගණනක සහ දාර දහස් ගණනක පරීක්ෂණ මත හොඳින් ක්‍රියා කරන බවයි. එවැනි පරීක්ෂණ වලදී පැය භාගයකින් විසඳුමක් ලැබෙනු ඇතැයි අපේක්ෂා කළ හැකිය. පිළිගත හැකි කාලයකදී පිළිතුරක් සෙවීමේ සම්භාවිතාව, ප්‍රතිපත්තිමය වශයෙන්, ප්‍රස්ථාරයේ ප්‍රමාණවත් තරම් ඉහළ මට්ටමේ සිරස් සංඛ්‍යාවක් තිබේ නම්, උදාහරණයක් ලෙස, අංශක 10 සහ ඊට වැඩි.

තරඟයට සහභාගී වීමට, විසඳුම් යැවීමට සිදු විය optil.io. එහි ඉදිරිපත් කර ඇති තොරතුරු අනුව විනිශ්චය කිරීම ලකුණ, විවෘත පරීක්ෂණ වලදී මගේ විසඳුම විස්සෙන් තුන්වන ස්ථානය, දෙවන සිට විශාල පරතරයක් සහිතව. සම්පුර්ණයෙන්ම අවංකව කිවහොත්, තරඟයේදීම විසඳුම් ඇගයීමට ලක් කරන්නේ කෙසේද යන්න සම්පූර්ණයෙන්ම පැහැදිලි නැත: උදාහරණයක් ලෙස, මගේ විසඳුම සිව්වන ස්ථානයේ විසඳුමට වඩා අඩු පරීක්ෂණ සමත් වේ, නමුත් සමත් වන ඒවා මත එය වේගයෙන් ක්‍රියා කරයි.

සංවෘත පරීක්ෂණවල ප්රතිඵල ජූලි XNUMX වනදා දැනගත හැකිය.

මූලාශ්රය: www.habr.com