تحقيق جو ڪم شايد اسان جي تربيت جو سڀ کان دلچسپ حصو آهي. اهو خيال آهي ته توهان پنهنجي چونڊيل هدايت ۾ پاڻ کي ڪوشش ڪريو جڏهن اڃا يونيورسٽي ۾. مثال طور، سافٽ ويئر انجنيئرنگ ۽ مشين لرننگ جي علائقن جا شاگرد اڪثر ڪري ڪمپنين ۾ تحقيق ڪرڻ لاءِ ويندا آهن (خاص ڪري JetBrains يا Yandex، پر نه رڳو).
هن پوسٽ ۾ آئون ڪمپيوٽر سائنس ۾ منهنجي منصوبي بابت ڳالهائيندس. منهنجي ڪم جي حصي جي طور تي، مون اڀياس ڪيو ۽ عملي طريقي سان عمل ڪيو ته جيئن مشهور NP-هارڊ مسئلن مان هڪ کي حل ڪيو وڃي: عمودي ڍڪڻ جو مسئلو.
اڄڪلهه، اين پي جي سخت مسئلن لاء هڪ دلچسپ طريقو تمام جلدي ترقي ڪري رهيو آهي - parameterized algorithms. مان ڪوشش ڪندس ته توھان کي تيزيءَ سان وٺي، توھان کي ٻڌايان ڪجھ سادو پيٽرولائزڊ الگورتھم ۽ ھڪڙو طاقتور طريقو بيان ڪريو جنھن مون کي تمام گھڻي مدد ڪئي. مون پنھنجا نتيجا پيش ڪيا PACE چيلنج مقابلي ۾: کليل ٽيسٽن جي نتيجن موجب، منھنجو حل ٽيون جڳھ وٺي ٿو، ۽ حتمي نتيجا 1 جولاءِ تي معلوم ڪيا ويندا.
پاڻ بابت
منهنجو نالو واسيلي الفروف آهي، مان هاڻي نيشنل ريسرچ يونيورسٽي هائر اسڪول آف اڪنامڪس - سينٽ پيٽرسبرگ ۾ ٽيون سال مڪمل ڪري رهيو آهيان. مون کي پنهنجي اسڪول جي ڏينهن کان الورورٿمز ۾ دلچسپي هئي، جڏهن مون ماسڪو اسڪول نمبر 179 ۾ پڙهيو ۽ ڪاميابيءَ سان ڪمپيوٽر سائنس اولمپياڊس ۾ حصو ورتو.
پيرا ميٽرائيز الگورٿمز ۾ ماهرن جو هڪ محدود تعداد بار ۾ داخل ٿيو ...
ڪتاب مان ورتل مثال
تصور ڪريو ته توهان هڪ ننڍڙي شهر ۾ بار سيڪيورٽي گارڊ آهيو. هر جمعه، اڌ شهر آرام ڪرڻ لاءِ توهان جي بار تي اچي ٿو، جيڪو توهان کي تمام گهڻي تڪليف ڏئي ٿو: توهان کي وڙهڻ کان بچڻ لاءِ سخت گراهڪ کي بار کان ٻاهر اڇلائڻ جي ضرورت آهي. آخرڪار، توهان تنگ ٿي وڃو ۽ احتياطي اپاء وٺڻ جو فيصلو ڪيو.
جيئن ته توهان جو شهر ننڍڙو آهي، توهان کي خبر آهي ته ڪهڙن سرپرستن جو جوڙو وڙهڻ جو امڪان آهي جيڪڏهن اهي هڪ بار ۾ گڏ ٿين. ڇا توھان وٽ ھڪڙي فهرست آھي n اهي ماڻهو جيڪي اڄ رات بار ۾ ايندا. توهان فيصلو ڪيو ته ڪجهه ڳوٺاڻن کي بار کان ٻاهر رکڻ کان سواءِ ڪنهن کي به ويڙهه ۾ نه. ساڳئي وقت، توهان جا مالڪ منافعو وڃائڻ نٿا چاهين ۽ ناخوش ٿي ويندا جيڪڏهن توهان کان وڌيڪ نه ڏيو k انسان.
بدقسمتي سان، توهان جي اڳيان مسئلو هڪ کلاسک NP-هارڊ مسئلو آهي. توهان شايد هن کي ڄاڻو ٿا ، يا عمدي ڍڪڻ واري مسئلي جي طور تي. اهڙين مسئلن لاء، عام صورت ۾، ڪو به الگورتھم نه آهن جيڪي قابل قبول وقت ۾ ڪم ڪن ٿيون. صحيح هجڻ لاء، غير ثابت ۽ ڪافي مضبوط مفروضو ETH (Exponential Time Hypothesis) چوي ٿو ته اهو مسئلو وقت ۾ حل نه ٿو ڪري سگهجي. ، اهو آهي، توهان مڪمل ڳولا کان بهتر طور تي ڪنهن به شيءِ بابت سوچي نٿا سگهو. مثال طور، اچو ته ڪو ماڻهو توهان جي بار ۾ اچڻ وارو آهي n = 1000 انسان. پوءِ مڪمل ڳولا ٿيندي اختيارات جيڪي تقريبا آهن - چريو رقم. خوشقسمتيء سان، توهان جي انتظام توهان کي هڪ حد ڏني آهي ڪ = 10, تنهنڪري مجموعن جو تعداد جيڪو توهان کي ٻيهر ڪرڻ جي ضرورت آهي تمام ننڍو آهي: ڏهن عناصر جي سبسٽس جو تعداد آهي . اهو بهتر آهي، پر اهو اڃا تائين هڪ ڏينهن ۾ شمار نه ڪيو ويندو جيتوڻيڪ هڪ طاقتور ڪلستر تي.
بار جي سياحن جي وچ ۾ ڇڪيل لاڳاپن جي هن ترتيب ۾ جنگ جي امڪان کي ختم ڪرڻ لاء، توهان کي باب، ڊينيئل ۽ فيڊر کي ٻاهر رکڻ جي ضرورت آهي. ڪو به حل نه آهي جنهن ۾ صرف ٻه پوئتي رهجي ويندا.
ڇا اهو مطلب آهي ته اهو وقت ڏيڻ جو وقت آهي ۽ سڀني کي اندر وڃڻ ڏيو؟ اچو ته ٻين اختيارن تي غور ڪريو. چڱو، مثال طور، توهان صرف انهن کي اجازت نه ٿا ڏئي سگهو جيڪي ماڻهن جي وڏي تعداد سان وڙهڻ جو امڪان آهن. جيڪڏهن ڪو ماڻهو گهٽ ۾ گهٽ جنگ ڪري سگهي ٿو ڪي +1 ٻيو ماڻهو، پوءِ توهان ضرور هن کي اندر اچڻ نه ٿا ڏئي سگهو - ٻي صورت ۾ توهان کي سڀني کي ٻاهر رکڻو پوندو ڪي +1 شهري، جن سان هو جنگ ڪري سگهي ٿو، جيڪو ضرور قيادت کي پريشان ڪندو.
اچو ته توهان سڀني کي ٻاهر ڪڍيو جيڪو توهان هن اصول مطابق ڪري سگهو ٿا. پوءِ هر ڪنهن سان وڙهجي سگهي ٿو ان کان وڌيڪ نه k ماڻهو. انهن کي ٻاهر اڇلائڻ k انسان، توهان کان وڌيڪ ڪجهه به روڪي نه ٿا سگهو تڪرار هن جو مطلب آهي ته جيڪڏهن ان کان وڌيڪ آهي جيڪڏهن ڪو ماڻهو گهٽ ۾ گهٽ هڪ تڪرار ۾ ملوث آهي، ته پوء توهان ضرور انهن سڀني کي روڪي نه ٿا سگهو. ڇو ته، يقيناً، توهان ضرور مڪمل طور تي غير تڪراري ماڻهن کي اجازت ڏينداسين، توهان کي ٻن سؤ ماڻهن مان ڏهه سائيز جي سڀني سبسٽس ذريعي وڃڻ جي ضرورت آهي. لڳ ڀڳ آهن , ۽ آپريشن جو هي تعداد اڳ ۾ ئي ڪلستر تي ترتيب ڏئي سگهجي ٿو.
جيڪڏهن توهان انهن ماڻهن کي محفوظ طور تي وٺي سگهو ٿا جن ۾ ڪوبه تڪرار ناهي، پوء انهن بابت ڇا آهي جيڪي صرف هڪ تڪرار ۾ حصو وٺندا آهن؟ حقيقت ۾، انهن کي پنهنجي مخالف تي دروازو بند ڪندي پڻ اجازت ڏئي سگهجي ٿو. درحقيقت، جيڪڏهن ايلس صرف باب سان تڪرار ۾ آهي، ته پوء جيڪڏهن اسان ايلس کي انهن مان ٻن مان نڪرڻ ڏيو، اسان نه وڃائينداسين: باب کي شايد ٻيا تڪرار هجن، پر ايلس کي يقيني طور تي نه آهي. ان کان علاوه، اهو اسان لاء ڪو به احساس ناهي ته اسان ٻنهي کي اندر وڃڻ نه ڏيو. اهڙي آپريشن کان پوء اتي ڪو به وڌيڪ نه آهي غير حل ٿيل قسمت سان مهمان: اسان وٽ ئي آهي تڪرار، هر هڪ ٻن شرڪت ڪندڙن سان ۽ هر هڪ گهٽ ۾ گهٽ ٻن ۾ ملوث. تنهن ڪري باقي رهي ٿو ترتيب ڏيڻ اختيارن، جنهن کي آساني سان سمجهي سگهجي ٿو اڌ ڏينهن هڪ ليپ ٽاپ تي.
حقيقت ۾، سادي دليل سان توهان اڃا به وڌيڪ پرڪشش حالتون حاصل ڪري سگهو ٿا. ياد رکو ته اسان کي ضرور سڀني تڪرارن کي حل ڪرڻ جي ضرورت آهي، اهو آهي، هر تڪراري جوڙي مان، گهٽ ۾ گهٽ هڪ شخص چونڊيو جنهن کي اسين اندر وڃڻ نه ڏينداسين. اچو ته هيٺ ڏنل الگورتھم تي غور ڪريون: ڪو به تڪرار وٺو، جنهن مان اسان هڪ حصو وٺندڙ کي هٽايو ۽ باقي کان ٻيهر شروع ڪيو، پوء ٻئي کي هٽائي ڇڏيو ۽ ٻيهر شروع ڪيو. جيئن ته اسان هر قدم تي ڪنهن کي ٻاهر اڇليندا آهيون، اهڙي الورورٿم جو ريڪرشن ٽري هڪ بائنري وڻ آهي. k، تنهنڪري مجموعي طور تي الگورتھم ڪم ڪري ٿو ڪٿي n عمودي جو تعداد آهي، ۽ m - رٻڙ جو تعداد. اسان جي مثال ۾، اهو اٽڪل ڏهه ملين آهي، جيڪو هڪ سيڪنڊ ۾ ورهائي سگهجي ٿو نه رڳو هڪ ليپ ٽاپ تي، پر موبائل فون تي پڻ.
مٿي ذڪر ڪيل هڪ مثال آهي parameterized algorithm. Parameterized algorithms algorithms آهن جيڪي وقت ۾ هلن ٿيون f(k) poly(n)ڪٿي p - پولينوميل، f هڪ خودمختيار ڪمپيوٽيبل فنڪشن آهي، ۽ k - ڪجھ پيٽرولر، جيڪو، ممڪن طور تي، مسئلو جي سائيز کان تمام ننڍو ٿيندو.
هن الگورتھم کان اڳ سڀ دليل هڪ مثال ڏئي ٿو kernelization parameterized algorithms ٺاهڻ لاء عام ٽيڪنالاجي مان هڪ آهي. ڪرنلائيزيشن هڪ پيراميٽر جي فنڪشن طرفان محدود قدر تائين مسئلي جي سائيز جي گھٽتائي آهي. نتيجو ڪندڙ مسئلو اڪثر ڪريل سڏيو ويندو آهي. اهڙيء طرح، عمودي جي درجي جي باري ۾ سادي استدلال جي ذريعي، اسان حاصل ڪيو هڪ quadratic kernel Vertex Cover جي مسئلي لاء، جواب جي ماپ جي مطابق. اتي ٻيون سيٽنگون آھن جيڪي توھان ھن ڪم لاءِ چونڊي سگھوٿا (جهڙوڪ Vertex Cover Above LP)، پر ھيءَ سيٽنگ آھي جنھن تي اسين بحث ڪنداسين.
رفتار چئلينج
مقابلي ۾ (The Parameterized Algorithms and Computational Experiments Challenge) 2015 ۾ پيدا ٿيو ته جيئن ڪمپيوٽيشنل مسئلن کي حل ڪرڻ لاءِ عملي طور استعمال ٿيندڙ پيراميٽرائزڊ الگورٿمز ۽ طريقن جي وچ ۾ رابطو قائم ڪيو وڃي. پهرين ٽي مقابلا هڪ گراف جي وڻ جي چوٽي کي ڳولڻ لاء وقف ڪيا ويا ()، هڪ اسٽائنر وڻ جي ڳولا ((). هن سال، انهن مسئلن مان هڪ جنهن ۾ توهان پنهنجي هٿ جي ڪوشش ڪري سگهو ٿا مٿي بيان ڪيل عمودي ڍڪڻ جو مسئلو هو.
مقابلو هر سال مقبوليت حاصل ڪري رهيو آهي. جيڪڏهن توهان ابتدائي انگن اکرن تي يقين رکون ٿا، هن سال 24 ٽيمن مقابلي ۾ حصو ورتو هو صرف عمودي ڍڪڻ واري مسئلي کي حل ڪرڻ لاء. اهو قابل ذڪر آهي ته مقابلو ڪيترن ئي ڪلاڪن يا هڪ هفتي کان نه، پر ڪيترن ئي مهينن تائين رهي ٿو. ٽيمن کي موقعو آهي ته هو ادب جو مطالعو ڪن، پنهنجو اصل خيال پيش ڪن ۽ ان تي عمل ڪرڻ جي ڪوشش ڪن. ذات ۾، هي مقابلو هڪ تحقيقي منصوبو آهي. سڀ کان وڌيڪ مؤثر حل لاء خيالن ۽ فاتحن کي انعام ڏيڻ ڪانفرنس سان گڏ گڏ ڪيو ويندو (International Symposium on Parameterized and Exact Computation) يورپ ۾ سڀ کان وڏي سالياني الگورٿمڪ اجلاس جي حصي طور . مقابلي جي باري ۾ وڌيڪ تفصيلي ڄاڻ حاصل ڪري سگهجي ٿو پاڻ تي ، ۽ گذريل سالن جا نتيجا ڪوڙ .
حل جو خاڪو
عمودي ڍڪڻ واري مسئلي کي حل ڪرڻ لاءِ، مون ڪوشش ڪئي پيراميٽرائزڊ الگورتھم. اهي عام طور تي ٻن حصن تي مشتمل آهن: آسان ڪرڻ جا ضابطا (جيڪي مثالي طور تي ڪنيلائيزيشن ڏانهن ويندا آهن) ۽ تقسيم جا ضابطا. آسانيءَ جا ضابطا پولينوميل وقت ۾ ان پٽ جي اڳڀرائي ڪرڻ وارا آهن. اهڙن قاعدن کي لاڳو ڪرڻ جو مقصد اهو آهي ته مسئلي کي گهٽ ڪرڻ برابر ننڍي مسئلي ڏانهن. آسانيءَ جا ضابطا الگورٿم جو سڀ کان مهانگو حصو آهن، ۽ هن حصي کي لاڳو ڪرڻ سان ڪل رننگ ٽائيم ٿئي ٿو. سادي polynomial وقت جي بدران. اسان جي صورت ۾، تقسيم جا ضابطا ان حقيقت تي ٻڌل آهن ته هر عمودي لاء توهان کي يا ته ان کي يا ان جي پاڙيسري کي جواب ڏيڻ جي ضرورت آهي.
عام اسڪيم هي آهي: اسان آسانيءَ جي ضابطن کي لاڳو ڪريون ٿا، پوءِ اسان ڪجهه عمودي چونڊون ٿا، ۽ ٻه بار بار ڪالون ڪيون ٿا: پهرين ۾ اسان ان کي جواب ۾ وٺون ٿا، ۽ ٻئي ۾ اسان ان جا سڀئي پاڙيسري وٺون ٿا. جنهن کي اسين هن چوٽيءَ سان ورهائڻ (برانچنگ) چوندا آهيون.
ايندڙ پيراگراف ۾ هن اسڪيم ۾ بلڪل هڪ اضافو ڪيو ويندو.
ورهائڻ جا خيال (برنچنگ) ضابطا
اچو ته بحث ڪريون ته ڪھڙيءَ ريت ھڪڙي عمدي کي چونڊيو جنھن سان ورهائجي.
بنيادي خيال الورورٿمڪ معنى ۾ تمام لالچي آهي: اچو ته وڌ ۾ وڌ درجي جو هڪ عموڪ وٺو ۽ ان سان گڏ ورهايو. اهو بهتر ڇو ٿو لڳي؟ ڇاڪاڻ ته ريٽرسو ڪال جي ٻئي برانچ ۾ اسان هن طريقي سان تمام گهڻيون چوٽيون ختم ڪنداسين. توهان هڪ ننڍڙي گراف تي ڳڻپ ڪري سگهو ٿا باقي اسان ان تي جلدي ڪم ڪري سگهون ٿا.
اهو طريقو، اڳ ۾ ئي بحث ڪيل سادي ڪنيلائيزيشن ٽيڪنڪ سان، پاڻ کي چڱي طرح ڏيکاري ٿو ۽ سائيز ۾ ڪيترن ئي هزار عمودي جا ڪجهه ٽيسٽ حل ڪري ٿو. پر، مثال طور، اهو ڪعبي گرافس لاءِ سٺو ڪم نٿو ڪري (يعني، گراف جن جي هر ويڪر جو درجو ٽي آهي).
ڪافي سادو خيال تي ٻڌل هڪ ٻيو خيال آهي: جيڪڏهن گراف ڊسڪ ڪيو ويو آهي، ان جي ڳنڍيل حصن تي مسئلو آزاديء سان حل ڪري سگهجي ٿو، آخر ۾ جوابن کي گڏ ڪندي. اهو، رستي ۾، اسڪيم ۾ هڪ ننڍڙي واعدو ڪيل ترميمي آهي، جيڪا خاص طور تي حل کي تيز ڪندي: اڳي، هن معاملي ۾، اسان اجزاء جي جوابن جي حساب لاء وقت جي پيداوار لاء ڪم ڪيو، پر هاڻي اسان ڪم ڪريون ٿا. رقم. ۽ برانچنگ کي تيز ڪرڻ لاء، توهان کي هڪ ڳنڍيل گراف کي هڪ منسلڪ ۾ تبديل ڪرڻ جي ضرورت آهي.
اهو ڪيئن ڪجي؟ جيڪڏهن گراف ۾ هڪ آرٽيڪل پوائنٽ آهي، توهان کي ان تي وڙهڻ جي ضرورت آهي. هڪ آرٽيڪوليشن پوائنٽ هڪ ويڪرو آهي جيئن ته هٽايو ويو، گراف پنهنجي رابطي کي وڃائي ٿو. گراف ۾ سڀ جنڪشن پوائنٽون ڳولهي سگهجن ٿيون ڪلاسيڪل الگورٿم استعمال ڪندي لڪير واري وقت ۾. اهو طريقو خاص طور تي برانچنگ کي تيز ڪري ٿو.
جڏهن ڪنهن به چونڊيل عمودي کي هٽايو ويندو آهي، گراف کي ڳنڍيل حصن ۾ ورهايو ويندو.
اسان اهو ڪنداسين، پر اسان وڌيڪ چاهيون ٿا. مثال طور، گراف ۾ ننڍڙا عمدي ڪٽ ڏسو ۽ ان مان عمودي چوڪن کي ورهايو. سڀ کان وڌيڪ ڪارائتو طريقو جيڪو مان ڄاڻان ٿو گھٽ ۾ گھٽ گلوبل ويڪرڪس ڪٽ کي ڳولڻ لاء هڪ Gomori-Hu وڻ استعمال ڪرڻ آهي، جيڪو ڪعبي وقت ۾ ٺهيل آهي. PACE چيلنج ۾، عام گراف جي سائيز ڪيترن ئي هزار چوٽي آهي. هن صورتحال ۾، بلين آپريشن ڪرڻ جي ضرورت آهي ريٽرنشن وڻ جي هر چوٽي تي. اهو ظاهر ٿئي ٿو ته ان کي مقرر وقت ۾ مسئلو حل ڪرڻ ناممڪن آهي.
اچو ته حل کي بهتر ڪرڻ جي ڪوشش ڪريو. عمودي جي ھڪڙي جوڙي جي وچ ۾ گھٽ ۾ گھٽ عمودي ڪٽ ڪنھن به الگورٿم ذريعي ڳولي سگھجي ٿو جيڪو وڌ ۾ وڌ وهڪري ٺاھي ٿو. توھان ان کي ھڪڙي نيٽ ورڪ تي ڇڏي سگھو ٿا عملي طور تي اهو تمام جلدي ڪم ڪري ٿو. مون کي هڪ شڪ آهي ته اهو نظرياتي طور تي ممڪن آهي ته آپريٽنگ وقت جو اندازو ثابت ڪرڻ ، جيڪو اڳ ۾ ئي قابل قبول آهي.
مون ڪيترائي ڀيرا ڪوشش ڪئي ته بي ترتيب عمودي جي جوڙن جي وچ ۾ ڪٽ ڳولڻ ۽ سڀ کان وڌيڪ متوازن وٺو. بدقسمتي سان، هن پيدا ڪئي غريب نتيجن کي کليل PACE چيلنج ٽيسٽ ۾. مون ان کي هڪ الگورٿم سان ڀيٽيو جيڪو وڌ کان وڌ درجي جي چوڪن کي ورهائي، انهن کي نزول جي کوٽائي تي هڪ حد سان هلائي ٿو. هڪ الورورٿم هن طريقي سان ڪٽي ڳولڻ جي ڪوشش ڪري رهيو آهي وڏن گرافن جي پويان. اهو ئي سبب آهي ته ڪٽ تمام غير متوازن ٿي ويا آهن: 5-10 عمودي کي هٽائي ڇڏيو، اهو صرف 15-20 کي ورهائڻ ممڪن هو.
اهو نوٽ ڪرڻ جي قابل آهي ته نظرياتي طور تي تيز ترين الگورتھم بابت آرٽيڪل ورهائڻ لاء عمودي چونڊڻ لاء وڌيڪ جديد ٽيڪنالاجي استعمال ڪن ٿا. اهڙيون ٽيڪنالاجيون تمام پيچيده عمل آهن ۽ اڪثر وقت ۽ ياداشت جي لحاظ کان خراب ڪارڪردگي آهن. مان انهن کي سڃاڻي نه سگهيو آهيان جيڪي عملي طور تي قابل قبول آهن.
ڪيئن لاڳو ڪجي سادگي جا ضابطا
اسان وٽ اڳ ۾ ئي kernelization لاء خيال آهن. مون کي توهان کي ياد ڏيارڻ ڏيو:
- جيڪڏهن ڪو اڪيلائي وارو عمودي آهي، ان کي ختم ڪريو.
- جيڪڏهن 1 درجي جو ڪو عمودي آهي، ان کي هٽايو ۽ ان جي پاڙيسري کي جواب ۾ وٺي.
- جيڪڏهن گهٽ ۾ گهٽ درجي جي ويڪر آهي ڪي +1، واپس وٺو.
پهرين ٻن سان سڀ ڪجهه واضح آهي، ٽئين سان گڏ هڪ چال آهي. جيڪڏهن هڪ بار جي باري ۾ هڪ مزاحيه مسئلو ۾ اسان کي هڪ مٿئين حد ڏني وئي هئي k، پوءِ PACE چيلنج ۾ توهان کي صرف گهٽ ۾ گهٽ سائيز جي هڪ عمدي ڍڪ ڳولڻ جي ضرورت آهي. هي هڪ عام تبديلي آهي ڳولا جي مسئلن جي فيصلي جي مسئلن ۾؛ اڪثر ڪري ٻن قسمن جي مسئلن جي وچ ۾ ڪو به فرق ناهي. عملي طور تي، جيڪڏهن اسان ورڪس کي ڍڪڻ واري مسئلي لاء حل ڪندڙ لکي رهيا آهيون، اتي هڪ فرق ٿي سگهي ٿو. مثال طور، جيئن ٽئين نقطي ۾.
عمل جي نقطي نظر کان، اڳتي وڌڻ جا ٻه طريقا آهن. پهرين طريقي کي سڏيو ويندو آهي Iterative Deepening. اهو هن ريت آهي: اسان جواب تي هيٺ ڏنل ڪجهه معقول رڪاوٽ سان شروع ڪري سگهون ٿا، ۽ پوءِ هن پابندي کي استعمال ڪندي پنهنجو الگورٿم مٿي کان جواب تي هڪ رڪاوٽ جي طور تي استعمال ڪري سگهون ٿا، بغير هن پابندي کان گهٽ ٿيڻ جي. جيڪڏھن اسان کي ڪجھ جواب مليو آھي، اھو بھتر ھوڻ جي ضمانت آھي، ٻي صورت ۾ اسين ھن حد کي ھڪ طرف وڌائي سگھون ٿا ۽ وري شروع ڪري سگھون ٿا.
ٻيو طريقو اهو آهي ته ڪجهه موجوده بهتر جواب کي ذخيرو ڪرڻ ۽ هڪ ننڍڙو جواب ڳولڻ لاء، هن پيٽرولر کي تبديل ڪندي جڏهن مليو k ڳولا ۾ غير ضروري شاخن کي وڌيڪ ڪٽڻ لاء.
رات جا ڪيترائي تجربا ڪرڻ کان پوءِ، مون انهن ٻن طريقن جي ميلاپ تي ٺهرايو: پهريون، مان ڳولا جي کوٽائي تي ڪجهه قسم جي حدن سان پنهنجو الگورٿم هلائيان ٿو (ان کي چونڊيو ته جيئن اهو بنيادي حل جي مقابلي ۾ گهٽ وقت وٺندو) ۽ بهترين استعمال ڪريو. حل مليو جواب جي مٿئين حد جي طور تي - اهو آهي، ساڳئي شيء ڏانهن k.
درجي جي چوٽي 2
اسان درجي 0 ۽ 1 جي چوٽي سان ڊيل ڪيو آهي. اهو ظاهر ٿئي ٿو ته اهو ٿي سگهي ٿو درجي 2 جي چوٽي سان، پر اهو گراف کان وڌيڪ پيچيده عملن جي ضرورت هوندي.
ان جي وضاحت ڪرڻ لاءِ، اسان کي ڪنهن به طرح عمودي کي مقرر ڪرڻ جي ضرورت آهي. اچو ته درجو 2 جي هڪ ويڪر کي هڪ vertex سڏين v، ۽ ان جا پاڙيسري - vertices x и y. اڳتي هلي اسان وٽ ٻه ڪيس هوندا.
- جڏهن x и y - پاڙيسري. پوء توهان جواب ڪري سگهو ٿا x и y۽ v حذف ڪريو. درحقيقت، هن ٽڪنڊي مان گهٽ ۾ گهٽ ٻه چوڪيون موٽڻ ۾ وٺڻ گهرجن، ۽ جيڪڏهن اسان وٺون ته ضرور نه وڃنداسين. x и y: اهي شايد ٻيا پاڙيسري آهن، ۽ v انهن مان ڪوبه ناهي.
- جڏهن x и y - نه پاڙيسري. ان کان پوء اهو بيان ڪيو ويو آهي ته سڀني ٽنهي چوڪن کي هڪ ۾ چپ ڪري سگهجي ٿو. خيال اهو آهي ته هن معاملي ۾ هڪ بهترين جواب آهي، جنهن ۾ اسين يا ته وٺون ٿا v، يا ٻئي چوٽيون x и y. ان کان علاوه، پهرين صورت ۾ اسان کي جواب ۾ سڀني پاڙيسرين کي کڻڻو پوندو x и y، پر سيڪنڊ ۾ اهو ضروري ناهي. اهو بلڪل انهن ڪيسن سان ملندو آهي جڏهن اسان جواب ۾ گلو ٿيل عمودي نه وٺندا آهيون ۽ جڏهن اسان ڪندا آهيون. اهو صرف ياد رکڻ لاء رهي ٿو ته ٻنهي صورتن ۾ اهڙي آپريشن جو ردعمل هڪ طرف گهٽجي ٿو.
اها ڳالهه نوٽ ڪرڻ جي قابل آهي ته هن نقطه نظر ڪافي لڪير وقت ۾ صحيح طور تي لاڳو ڪرڻ ڏکيو آهي. گلونگ عمودي هڪ پيچيده آپريشن آهي؛ توهان کي پاڙيسرين جي فهرستن کي نقل ڪرڻ جي ضرورت آهي. جيڪڏهن اهو لاپرواهي سان ڪيو ويو آهي، توهان ختم ڪري سگهو ٿا asymptotically suboptimal رننگ ٽائيم (مثال طور، جيڪڏهن توهان هر گلونگ کان پوء ڪيترن ئي ڪنڊن کي نقل ڪريو). مون درجي 2 جي چوڪن مان سمورو رستا ڳولڻ ۽ خاص ڪيسن جي ھڪڙي گروپ جو تجزيو ڪرڻ تي ٺھيو آھي، جھڙوڪ اھڙن چوڪن مان چڪر يا ھڪڙي کان سواءِ سڀني اهڙن چوڪن مان.
ان کان علاوه، اهو ضروري آهي ته اهو آپريشن واپس موٽڻ لائق هجي، انهي ڪري ته جڏهن واپسي کان واپسي اسان گراف کي ان جي اصل شڪل ۾ بحال ڪريون. انهي کي يقيني بڻائڻ لاءِ، مون ضم ٿيل ڪنارن جي فهرستن کي صاف نه ڪيو، ۽ پوءِ مون کي خبر پئي ته ڪهڙن ڪنڊن کي ڪٿي وڃڻو آهي. گراف جي هن عمل کي پڻ درستگي جي ضرورت آهي، پر اهو مناسب لڪير وارو وقت مهيا ڪري ٿو. ۽ ڪيترن ئي هزارين ڪنارن جي گرافس لاء، اهو پروسيسر ڪيش ۾ ٺهڪي اچي ٿو، جيڪو رفتار ۾ وڏو فائدو ڏئي ٿو.
لڪير وارو دٻو
آخرڪار، ڪتن جو سڀ کان دلچسپ حصو.
شروع ڪرڻ لاءِ، ياد رکو ته ٻه طرفي گرافس ۾ گھٽ ۾ گھٽ ورٽيڪس ڍڪ ڳولهي سگھجي ٿو . هن کي ڪرڻ لاء، توهان کي الورورٿم استعمال ڪرڻ جي ضرورت آهي وڌ ۾ وڌ ميلاپ ڳولڻ لاءِ اتي، ۽ پوءِ نظريو استعمال ڪريو .
هڪ لڪير ڪنييل جو خيال هي آهي: پهرين اسان گراف کي جدا ڪريون ٿا، يعني هر عمدي جي بدران. v اچو ته ٻه چوٽيون شامل ڪريون и ، ۽ هر ڪنڊ جي بدران u - v اچو ته ٻه رٻڙ شامل ڪريون и . نتيجو گراف ٻه طرفي ٿيندو. اچو ته ان ۾ گھٽ ۾ گھٽ عمودي ڍڪ ڳوليون. اصل گراف جا ڪجهه چوڪيدار اتي ٻه ڀيرا ملندا، ڪجهه صرف هڪ ڀيرو، ۽ ڪجهه ڪڏهن به نه. Nemhauser-Trotter Theorem چوي ٿو ته ھن حالت ۾ ھڪڙو انھن ڪنارن کي ختم ڪري سگھي ٿو جيڪي ھڪ ڀيرو به نه ماريا آھن ۽ جيڪي ٻه ڀيرا مارا آھن تن کي واپس وٺي سگھن ٿا. ان کان علاوه، هوء چوي ٿي ته باقي عمودي مان (جيڪي هڪ ڀيرو مارا ويندا آهن) توهان کي گهٽ ۾ گهٽ اڌ جواب ڏيڻ جي ضرورت آهي.
اسان صرف ايترو ئي سکيو آهي جو وڌيڪ نه ڇڏڻ 2k چوٽيون درحقيقت، جيڪڏهن باقي جواب گهٽ ۾ گهٽ سڀني چوڪن جو اڌ آهي، ته پوءِ مجموعي طور تي ان کان وڌيڪ ڪو به چوڪو نه هوندو. 2k.
هتي مون کي هڪ ننڍڙو قدم اڳتي وڌڻ جي قابل ٿي ويو. اهو واضح آهي ته هن طريقي سان ٺهيل ڪنيال تي منحصر آهي ته ڪهڙي قسم جي گهٽ ۾ گهٽ عمودي ڪپڙا اسان بائيپارٽائيٽ گراف ۾ ورتو آهي. مان هڪ وٺڻ چاهيان ٿو ته جيئن باقي چوڪن جو تعداد گهٽ ۾ گهٽ هجي. اڳي، اهي صرف وقت ۾ ائين ڪرڻ جي قابل هئا . مون وقت ۾ هن الگورتھم جي عمل درآمد سان آيو اهڙيءَ طرح، هي ڪور هر شاخ جي اسٽيج تي سوين هزارين عمودي جي گراف ۾ ڳولهي سگهجي ٿو.
نتيجي ۾
مشق ڏيکاري ٿو ته منهنجو حل ڪيترن ئي سؤ عمودي ۽ ڪيترن ئي هزار کنارن جي تجربن تي سٺو ڪم ڪري ٿو. اهڙين تجربن ۾ اهو ممڪن آهي ته اميد آهي ته هڪ حل اڌ ڪلاڪ ۾ ملي ويندو. هڪ قابل قبول وقت ۾ جواب ڳولڻ جو امڪان، اصولي طور تي، وڌندو آهي جيڪڏهن گراف ۾ ڪافي وڏي تعداد ۾ اعليٰ درجي جي چوٽيون آهن، مثال طور، درجا 10 ۽ ان کان وڌيڪ.
مقابلي ۾ حصو وٺڻ لاء، حل موڪليا ويندا هئا . اتي پيش ڪيل معلومات جي مطابق ، اوپن ٽيسٽ ۾ منهنجو حل ويهن مان ٽيون نمبر تي آهي، ٻئي کان وڏي خال سان. مڪمل طور تي ايماندار ٿيڻ لاء، اهو مڪمل طور تي واضح ناهي ته ڪيئن حل جو جائزو ورتو ويندو مقابلي ۾ پاڻ کي: مثال طور، منهنجو حل چوٿين جاء تي حل کان گهٽ ٽيسٽ پاس ڪري ٿو، پر انهن تي جيڪي پاس ڪن ٿا، اهو تيزيء سان ڪم ڪري ٿو.
بند ٿيل ٽيسٽن جا نتيجا پهرين جولاءِ تي معلوم ٿيندا.
جو ذريعو: www.habr.com