पॅरामीटराइज्ड अल्गोरिदमसह NP-हार्ड समस्यांचे निराकरण कसे करावे

संशोधन कार्य हा कदाचित आमच्या प्रशिक्षणाचा सर्वात मनोरंजक भाग आहे. विद्यापीठात असतानाही तुमच्या निवडलेल्या दिशेने प्रयत्न करण्याची कल्पना आहे. उदाहरणार्थ, सॉफ्टवेअर अभियांत्रिकी आणि मशीन लर्निंग या क्षेत्रातील विद्यार्थी अनेकदा कंपन्यांमध्ये संशोधन करण्यासाठी जातात (प्रामुख्याने JetBrains किंवा Yandex, परंतु केवळ नाही).

या पोस्टमध्ये मी माझ्या संगणक विज्ञानातील प्रकल्पाबद्दल बोलणार आहे. माझ्या कामाचा एक भाग म्हणून, मी सर्वात प्रसिद्ध NP-हार्ड समस्यांपैकी एक सोडवण्याच्या पद्धतींचा अभ्यास केला आणि सराव केला: शिरोबिंदू कव्हरिंग समस्या.

आजकाल, एनपी-हार्ड समस्यांकडे एक मनोरंजक दृष्टीकोन फार लवकर विकसित होत आहे - पॅरामीटराइज्ड अल्गोरिदम. मी तुमचा वेग वाढवण्याचा प्रयत्न करेन, तुम्हाला काही सोप्या पॅरामीटराइज्ड अल्गोरिदम सांगेन आणि एका शक्तिशाली पद्धतीचे वर्णन करेन ज्याने मला खूप मदत केली. मी PACE चॅलेंज स्पर्धेत माझे निकाल सादर केले: खुल्या चाचण्यांच्या निकालांनुसार, माझे समाधान तिसरे स्थान घेते आणि अंतिम निकाल 1 जुलै रोजी कळेल.

माझ्याबद्दल

माझे नाव वसिली अल्फेरोव्ह आहे, मी आता नॅशनल रिसर्च युनिव्हर्सिटी हायर स्कूल ऑफ इकॉनॉमिक्स - सेंट पीटर्सबर्ग येथे माझे तिसरे वर्ष पूर्ण करत आहे. मला माझ्या शालेय दिवसांपासून अल्गोरिदममध्ये रस आहे, जेव्हा मी मॉस्को शाळा क्रमांक 179 मध्ये शिकलो आणि संगणक विज्ञान ऑलिम्पियाडमध्ये यशस्वीरित्या भाग घेतला.

पॅरामीटराइज्ड अल्गोरिदममधील तज्ञांची मर्यादित संख्या बारमध्ये प्रवेश करते...

पुस्तकातून घेतलेले उदाहरण "पॅरामीटराइज्ड अल्गोरिदम"

कल्पना करा की तुम्ही एका लहान शहरातील बार सुरक्षा रक्षक आहात. दर शुक्रवारी, अर्धे शहर आराम करण्यासाठी तुमच्या बारमध्ये येते, ज्यामुळे तुम्हाला खूप त्रास होतो: भांडणे टाळण्यासाठी तुम्हाला उग्र ग्राहकांना बारमधून बाहेर फेकणे आवश्यक आहे. अखेरीस, तुम्ही कंटाळलात आणि प्रतिबंधात्मक उपाय करण्याचे ठरवता.

तुमचे शहर लहान असल्याने, तुम्हाला माहीत आहे की संरक्षकांच्या कोणत्या जोड्या एकत्र बारमध्ये गेल्यास ते लढण्याची शक्यता आहे. तुमच्याकडे यादी आहे का n जे लोक आज रात्री बारमध्ये येतील. तुम्ही कोणाशीही भांडण न करता काही शहरवासीयांना बारमधून बाहेर ठेवण्याचे ठरवता. त्याच वेळी, तुमचे बॉस नफा गमावू इच्छित नाहीत आणि तुम्ही त्यापेक्षा जास्त नफा न दिल्यास ते नाखूष होतील k मानव

दुर्दैवाने, तुमच्यासमोरची समस्या ही क्लासिक NP-हार्ड समस्या आहे. तुम्ही तिला म्हणून ओळखत असाल व्हर्टेक्स कव्हर, किंवा शिरोबिंदू कव्हरिंग समस्या म्हणून. अशा समस्यांसाठी, सामान्य प्रकरणात, स्वीकार्य वेळेत कार्य करणारे कोणतेही अल्गोरिदम नाहीत. तंतोतंत सांगायचे तर, अप्रमाणित आणि जोरदार गृहीतक ETH (एक्सपोनेन्शिअल टाइम हायपोथिसिस) म्हणते की ही समस्या वेळेत सोडवली जाऊ शकत नाही. , म्हणजे, आपण संपूर्ण शोधापेक्षा लक्षणीयरीत्या कोणत्याही गोष्टीचा विचार करू शकत नाही. उदाहरणार्थ, आपल्या बारमध्ये कोणीतरी येणार आहे असे समजा एन = एक्सएनयूएमएक्स मानव. मग पूर्ण शोध होईल अंदाजे आहेत असे पर्याय - वेडा रक्कम. सुदैवाने, तुमच्या व्यवस्थापनाने तुम्हाला मर्यादा दिली आहे के = 10, त्यामुळे तुम्हाला पुनरावृत्ती करण्याची आवश्यकता असलेल्या संयोगांची संख्या खूपच लहान आहे: दहा घटकांच्या उपसंचांची संख्या . हे अधिक चांगले आहे, परंतु तरीही एका शक्तिशाली क्लस्टरवरही ते एका दिवसात मोजले जाणार नाही.

बारच्या अभ्यागतांमधील तणावपूर्ण संबंधांच्या या कॉन्फिगरेशनमध्ये भांडणाची शक्यता दूर करण्यासाठी, तुम्हाला बॉब, डॅनियल आणि फेडरला बाहेर ठेवणे आवश्यक आहे. असा कोणताही उपाय नाही ज्यात फक्त दोनच मागे राहतील.

याचा अर्थ हार मानण्याची आणि सर्वांना आत येऊ देण्याची वेळ आली आहे का? चला इतर पर्यायांचा विचार करूया. बरं, उदाहरणार्थ, ज्यांना मोठ्या संख्येने लोकांशी लढण्याची शक्यता आहे त्यांनाच तुम्ही आत येऊ देऊ शकत नाही. कुणाशी तरी लढता येत असेल तर k+1 दुसरी व्यक्ती, मग तुम्ही त्याला नक्कीच आत येऊ देऊ शकत नाही - अन्यथा तुम्हाला सर्वांना बाहेर ठेवावे लागेल k+1 शहरवासी, ज्यांच्याशी तो लढू शकतो, जे नेतृत्वाला नक्कीच अस्वस्थ करेल.

या तत्त्वानुसार तुम्हाला शक्य असलेल्या प्रत्येकाला बाहेर फेकून द्या. मग इतर प्रत्येकजण यापेक्षा जास्त नाहीशी लढू शकतो k लोक त्यांना बाहेर फेकणे k यार, आपण यापेक्षा अधिक काहीही रोखू शकत नाही संघर्ष पेक्षा जास्त असेल तर याचा अर्थ जर एखादी व्यक्ती कमीतकमी एका संघर्षात गुंतलेली असेल तर आपण त्या सर्वांना नक्कीच रोखू शकत नाही. अर्थातच, तुम्ही निश्चितपणे पूर्णपणे गैर-विरोधाभास लोकांना येऊ द्याल, तुम्हाला दोनशे लोकांपैकी दहा लोकांच्या आकाराच्या सर्व उपसमूहांमधून जाण्याची आवश्यकता आहे. अंदाजे आहेत , आणि ऑपरेशन्सची ही संख्या क्लस्टरवर आधीच सोडवली जाऊ शकते.

ज्यांच्यात अजिबात संघर्ष नाही अशा व्यक्तींना जर तुम्ही सुरक्षितपणे घेऊ शकत असाल, तर जे फक्त एकाच संघर्षात सहभागी होतात त्यांचे काय? किंबहुना, त्यांच्या प्रतिस्पर्ध्यावर दार बंद करूनही त्यांना आत जाऊ दिले जाऊ शकते. खरंच, जर अॅलिस फक्त बॉबशी संघर्ष करत असेल, तर जर आपण अॅलिसला त्या दोघांपैकी बाहेर सोडले तर आपण हरणार नाही: बॉबला इतर संघर्ष असू शकतात, परंतु अॅलिसमध्ये ते नक्कीच नाहीत. शिवाय, आम्हा दोघांना आत येऊ न देण्यास काही अर्थ नाही. अशा ऑपरेशन्सनंतर आणखी काही शिल्लक नाही निराकरण न झालेले नशीब असलेले अतिथी: आमच्याकडे फक्त आहे संघर्ष, प्रत्येक दोन सहभागी आणि प्रत्येक किमान दोन सहभागी. तर जे उरते ते क्रमवारी लावायचे आहे पर्याय, जे सहजपणे लॅपटॉपवर अर्धा दिवस मानले जाऊ शकतात.

खरं तर, साध्या तर्काने आपण आणखी आकर्षक परिस्थिती प्राप्त करू शकता. लक्षात घ्या की आम्हाला निश्चितपणे सर्व विवादांचे निराकरण करणे आवश्यक आहे, म्हणजे, प्रत्येक विवादित जोडीमधून, कमीतकमी एक व्यक्ती निवडा ज्याला आम्ही आत येऊ देणार नाही. चला खालील अल्गोरिदमचा विचार करूया: कोणताही विरोध घ्या, ज्यामधून आम्ही एक सहभागी काढून टाकतो आणि उर्वरित भागातून पुनरावृत्ती सुरू करतो, नंतर दुसरा काढून टाकतो आणि पुनरावृत्ती सुरू करतो. आपण प्रत्येक पायरीवर एखाद्याला बाहेर फेकत असल्याने, अशा अल्गोरिदमचे पुनरावृत्ती वृक्ष हे खोलीचे बायनरी ट्री आहे. k, त्यामुळे एकूण अल्गोरिदम मध्ये कार्य करते कुठे n शिरोबिंदूंची संख्या आहे, आणि m - फास्यांची संख्या. आमच्या उदाहरणात, हे सुमारे दहा दशलक्ष आहे, जे केवळ लॅपटॉपवरच नव्हे तर मोबाईल फोनवर देखील विभाजित सेकंदात मोजले जाऊ शकते.

वरील उदाहरण एक उदाहरण आहे पॅरामीटराइज्ड अल्गोरिदम. पॅरामीटराइज्ड अल्गोरिदम हे अल्गोरिदम आहेत जे वेळेत चालतात f(k) पॉली(n)कुठे p - बहुपदी, f एक अनियंत्रित गणना करण्यायोग्य कार्य आहे, आणि k - काही पॅरामीटर, जे, शक्यतो, समस्येच्या आकारापेक्षा खूपच लहान असेल.

या अल्गोरिदमच्या आधीचे सर्व तर्क एक उदाहरण देतात कर्नलीकरण पॅरामीटराइज्ड अल्गोरिदम तयार करण्यासाठी सामान्य तंत्रांपैकी एक आहे. कर्नलायझेशन म्हणजे पॅरामीटरच्या फंक्शनद्वारे मर्यादित मूल्यापर्यंत समस्या आकार कमी करणे. परिणामी समस्या अनेकदा कर्नल म्हणतात. अशाप्रकारे, शिरोबिंदूंच्या अंशांबद्दल साध्या तर्काने, आम्ही व्हर्टेक्स कव्हर समस्येसाठी एक चतुर्भुज कर्नल मिळवला, उत्तराच्या आकारानुसार पॅरामीटराइज्ड. या कार्यासाठी तुम्ही इतर सेटिंग्ज निवडू शकता (जसे की व्हर्टेक्स कव्हर अबव्ह एलपी), परंतु हीच सेटिंग आहे ज्याची आम्ही चर्चा करणार आहोत.

पेस चॅलेंज

स्पर्धा PACE आव्हान (The Parameterized Algorithms and Computational Experiments Challenge) चा जन्म 2015 मध्ये पॅरामीटराइज्ड अल्गोरिदम आणि संगणकीय समस्या सोडवण्यासाठी व्यवहारात वापरल्या जाणार्‍या पध्दतींमधील संबंध स्थापित करण्यासाठी झाला. पहिल्या तीन स्पर्धा ग्राफची झाडाची रुंदी शोधण्यासाठी समर्पित होत्या (झाडाची रुंदी, स्टीनर वृक्ष शोधत आहे (स्टेनर वृक्ष) आणि शिरोबिंदूंचा संच शोधत आहे जे चक्र कापतात (फीडबॅक व्हर्टेक्स सेट). या वर्षी, वर वर्णन केलेल्या शिरोबिंदू कव्हरिंग समस्यांपैकी एक समस्या ज्यामध्ये तुम्ही तुमचा हात आजमावू शकता.

दरवर्षी ही स्पर्धा लोकप्रिय होत आहे. तुमचा प्राथमिक डेटावर विश्वास असल्यास, या वर्षी 24 संघांनी केवळ शिरोबिंदू कव्हरिंगची समस्या सोडवण्यासाठी स्पर्धेत भाग घेतला. हे लक्षात घेण्यासारखे आहे की स्पर्धा कित्येक तास किंवा आठवडाभर नाही तर अनेक महिने चालते. संघांना साहित्याचा अभ्यास करण्याची, त्यांची स्वतःची मूळ कल्पना आणण्याची आणि ती लागू करण्याचा प्रयत्न करण्याची संधी आहे. थोडक्यात, ही स्पर्धा एक संशोधन प्रकल्प आहे. सर्वात प्रभावी उपायांसाठी कल्पना आणि विजेत्यांना पुरस्कार कॉन्फरन्सच्या संयोगाने आयोजित केले जातील आयपेक (इंटरनॅशनल सिम्पोजियम ऑन पॅरामीटराइज्ड अँड एक्सॅक्ट कॉम्प्युटेशन) युरोपमधील सर्वात मोठ्या वार्षिक अल्गोरिदमिक बैठकीचा भाग म्हणून ALGO. स्पर्धेबद्दल अधिक तपशीलवार माहिती येथे आढळू शकते साइट, आणि मागील वर्षांचे परिणाम खोटे आहेत येथे.

उपाय आकृती

शिरोबिंदू कव्हरिंग समस्येचे निराकरण करण्यासाठी, मी पॅरामीटराइज्ड अल्गोरिदम वापरण्याचा प्रयत्न केला. त्यामध्ये सामान्यत: दोन भाग असतात: सरलीकरण नियम (ज्यामुळे कर्नलीकरण होते) आणि विभाजन नियम. सरलीकरण नियम बहुपदी वेळेत इनपुटची प्रीप्रोसेसिंग आहेत. असे नियम लागू करण्याचा उद्देश हा समस्या कमी करून समतुल्य छोट्या समस्येवर आणणे आहे. सरलीकरण नियम हा अल्गोरिदमचा सर्वात महाग भाग आहे आणि हा भाग लागू केल्याने एकूण धावण्याची वेळ येते साध्या बहुपदी वेळेऐवजी. आमच्या बाबतीत, विभाजनाचे नियम या वस्तुस्थितीवर आधारित आहेत की प्रत्येक शिरोबिंदूसाठी तुम्हाला ते किंवा त्याच्या शेजारी उत्तर म्हणून घेणे आवश्यक आहे.

सर्वसाधारण योजना अशी आहे: आम्ही सरलीकरण नियम लागू करतो, नंतर आम्ही काही शिरोबिंदू निवडतो आणि दोन पुनरावृत्ती कॉल करतो: प्रथम आम्ही ते प्रतिसादात घेतो आणि दुसर्‍यामध्ये आम्ही त्याचे सर्व शेजारी घेतो. या शिरोबिंदूला आपण स्प्लिटिंग (शाखा काढणे) म्हणतो.

पुढील परिच्छेदात या योजनेत नेमकी एक भर टाकली जाईल.

स्प्लिटिंग (ब्रंचिंग) नियमांसाठी कल्पना

विभाजीत होणारे शिरोबिंदू कसे निवडायचे यावर चर्चा करूया.
मुख्य कल्पना अल्गोरिदमिक अर्थाने खूप लोभी आहे: चला जास्तीत जास्त पदवीचा शिरोबिंदू घेऊ आणि त्यास विभाजित करू. ते चांगले का दिसते? कारण रिकर्सिव्ह कॉलच्या दुस-या शाखेत आपण अशा प्रकारे बरेच शिरोबिंदू काढून टाकू. तुम्ही उरलेल्या छोट्या आलेखावर विश्वास ठेवू शकता आणि आम्ही त्यावर त्वरीत काम करू शकतो.

हा दृष्टीकोन, आधीच चर्चा केलेल्या सोप्या कर्नलायझेशन तंत्रांसह, स्वतःला चांगले दाखवते आणि आकारात अनेक हजार शिरोबिंदूंच्या काही चाचण्या सोडवते. परंतु, उदाहरणार्थ, ते क्यूबिक आलेखांसाठी चांगले काम करत नाही (म्हणजे आलेख ज्यांच्या प्रत्येक शिरोबिंदूची डिग्री तीन आहे).
अगदी सोप्या कल्पनेवर आधारित आणखी एक कल्पना आहे: जर आलेख डिस्कनेक्ट केला असेल, तर त्याच्या कनेक्ट केलेल्या घटकांवरील समस्या स्वतंत्रपणे सोडवता येईल, शेवटी उत्तरे एकत्र करून. हे, तसे, योजनेतील एक लहान वचन दिलेले बदल आहे, जे समाधानास लक्षणीय गती देईल: पूर्वी, या प्रकरणात, आम्ही घटकांच्या प्रतिसादांची गणना करण्यासाठी वेळेच्या उत्पादनासाठी काम केले, परंतु आता आम्ही यासाठी कार्य करतो बेरीज आणि ब्रँचिंगला गती देण्यासाठी, तुम्हाला कनेक्ट केलेला आलेख डिस्कनेक्ट केलेल्यामध्ये बदलण्याची आवश्यकता आहे.

ते कसे करायचे? आलेखामध्ये एक उच्चार बिंदू असल्यास, आपल्याला त्यावर संघर्ष करणे आवश्यक आहे. आर्टिक्युलेशन पॉईंट हा एक शिरोबिंदू आहे की काढल्यावर आलेख त्याची कनेक्टिव्हिटी गमावतो. रेखीय वेळेत शास्त्रीय अल्गोरिदम वापरून आलेखामधील सर्व जंक्शन बिंदू शोधले जाऊ शकतात. हा दृष्टीकोन लक्षणीयरीत्या शाखा वाढवितो.

जेव्हा निवडलेले कोणतेही शिरोबिंदू काढले जातात, तेव्हा आलेख कनेक्ट केलेल्या घटकांमध्ये विभाजित होईल.

आम्ही हे करू, परंतु आम्हाला आणखी हवे आहे. उदाहरणार्थ, आलेखामध्ये लहान शिरोबिंदू कट शोधा आणि त्यातील शिरोबिंदूंसह विभाजित करा. किमान ग्लोबल व्हर्टेक्स कट शोधण्याचा सर्वात प्रभावी मार्ग म्हणजे गोमोरी-हू वृक्ष वापरणे, जे घन वेळेत तयार केले जाते. PACE चॅलेंजमध्ये, ठराविक आलेखाचा आकार अनेक हजार शिरोबिंदूंचा असतो. या परिस्थितीत, पुनरावृत्ती वृक्षाच्या प्रत्येक शिरोबिंदूवर कोट्यवधी ऑपरेशन्स करणे आवश्यक आहे. असे दिसून आले की वाटप केलेल्या वेळेत समस्या सोडवणे अशक्य आहे.

चला समाधान ऑप्टिमाइझ करण्याचा प्रयत्न करूया. शिरोबिंदूंच्या जोडीमधील किमान शिरोबिंदू कापून जास्तीत जास्त प्रवाह तयार करणाऱ्या कोणत्याही अल्गोरिदमद्वारे आढळू शकतो. आपण ते अशा नेटवर्कवर सोडू शकता डिनिट्झ अल्गोरिदम, सराव मध्ये ते खूप लवकर कार्य करते. मला एक शंका आहे की ऑपरेटिंग वेळेसाठी अंदाज सिद्ध करणे सैद्धांतिकदृष्ट्या शक्य आहे , जे आधीच स्वीकार्य आहे.

यादृच्छिक शिरोबिंदूंच्या जोड्यांमधील कट शोधण्याचा आणि सर्वात संतुलित एक घेण्याचा मी अनेक वेळा प्रयत्न केला. दुर्दैवाने, यामुळे खुल्या PACE चॅलेंज चाचणीत खराब परिणाम आले. मी त्याची तुलना एका अल्गोरिदमशी केली आहे जी कमाल डिग्रीच्या शिरोबिंदूंना विभाजित करते, त्यांना उतरण्याच्या खोलीवर मर्यादा घालून चालवते. अशा प्रकारे कट शोधण्याचा प्रयत्न करणारा अल्गोरिदम मोठा आलेख मागे सोडतो. हे कट खूप असंतुलित असल्याचे कारण आहे: 5-10 शिरोबिंदू काढून टाकल्यानंतर, केवळ 15-20 विभाजित करणे शक्य झाले.

हे लक्षात घेण्यासारखे आहे की सैद्धांतिकदृष्ट्या वेगवान अल्गोरिदमबद्दलचे लेख विभाजनासाठी शिरोबिंदू निवडण्यासाठी अधिक प्रगत तंत्रे वापरतात. अशा तंत्रांमध्ये खूप जटिल अंमलबजावणी असते आणि वेळ आणि स्मरणशक्तीच्या बाबतीत अनेकदा खराब कामगिरी असते. सरावासाठी स्वीकारार्ह असलेल्यांना मी ओळखू शकलो नाही.

सरलीकरण नियम कसे लागू करावे

आमच्याकडे कर्नलायझेशनसाठी आधीच कल्पना आहेत. मी तुम्हाला आठवण करून देतो:

1. जर एक विलग शिरोबिंदू असेल तर ते हटवा.
2. जर डिग्री 1 चे शिरोबिंदू असेल तर ते काढून टाका आणि प्रतिसादात शेजारी घ्या.
3. जर पदवीचा शिरोबिंदू असेल तर k+1, ते परत घे.

पहिल्या दोनसह सर्वकाही स्पष्ट आहे, तिसऱ्यासह एक युक्ती आहे. बारबद्दल कॉमिक समस्या असल्यास आम्हाला ची वरची मर्यादा दिली गेली होती k, नंतर PACE चॅलेंजमध्ये तुम्हाला फक्त किमान आकाराचे शिरोबिंदू कव्हर शोधण्याची आवश्यकता आहे. हे शोध समस्यांचे ठराविक समस्यांमध्ये रूपांतर आहे; अनेकदा दोन प्रकारच्या समस्यांमध्ये फरक नसतो. व्यवहारात, जर आपण शिरोबिंदू कव्हरिंग समस्येसाठी सॉल्व्हर लिहित आहोत, तर फरक असू शकतो. उदाहरणार्थ, तिसऱ्या बिंदूप्रमाणे.

अंमलबजावणीच्या दृष्टिकोनातून, पुढे जाण्याचे दोन मार्ग आहेत. पहिल्या पद्धतीला पुनरावृत्ती सखोल म्हणतात. ते खालीलप्रमाणे आहे: आम्ही खालील उत्तरावर काही वाजवी मर्यादांसह सुरुवात करू शकतो, आणि नंतर या निर्बंधापेक्षा कमी पुनरावृत्ती न करता, वरून उत्तरावर मर्यादा म्हणून हा प्रतिबंध वापरून आमचे अल्गोरिदम चालवू शकतो. जर आम्हाला काही उत्तर सापडले असेल तर ते इष्टतम असण्याची हमी आहे, अन्यथा आम्ही ही मर्यादा एकाने वाढवू शकतो आणि पुन्हा सुरुवात करू शकतो.

आणखी एक दृष्टीकोन म्हणजे काही वर्तमान इष्टतम उत्तर संग्रहित करणे आणि लहान उत्तर शोधणे, जेव्हा सापडले तेव्हा हे पॅरामीटर बदलणे k शोधात अनावश्यक फांद्या अधिक कापण्यासाठी.

रात्रीचे अनेक प्रयोग केल्यानंतर, मी या दोन पद्धतींच्या संयोजनावर सेटल झालो: प्रथम, मी माझे अल्गोरिदम शोध खोलीवर काही मर्यादा घालून चालवतो (मुख्य उपायाच्या तुलनेत नगण्य वेळ लागतो म्हणून ते निवडणे) आणि सर्वोत्तम वापरतो. उत्तराची वरची मर्यादा म्हणून सापडलेला उपाय - म्हणजे त्याच गोष्टीसाठी k.

पदवी 2 चे शिरोबिंदू

आम्ही डिग्री 0 आणि 1 च्या शिरोबिंदूंचा सामना केला आहे. असे दिसून आले की हे पदवी 2 च्या शिरोबिंदूंसह केले जाऊ शकते, परंतु यासाठी आलेखावरून अधिक जटिल ऑपरेशन्स आवश्यक असतील.

हे स्पष्ट करण्यासाठी, आपल्याला कसे तरी शिरोबिंदू नियुक्त करणे आवश्यक आहे. डिग्री २ च्या शिरोबिंदूला शिरोबिंदू म्हणू v, आणि त्याचे शेजारी - शिरोबिंदू x и y. पुढे आपल्याकडे दोन प्रकरणे असतील.

1. जेव्हा x и y - शेजारी. मग तुम्ही उत्तर देऊ शकता x и yआणि v हटवा खरंच, या त्रिकोणातून कमीत कमी दोन शिरोबिंदू त्या बदल्यात घेणे आवश्यक आहे, आणि आम्ही घेतल्यास आम्ही निश्चितपणे गमावणार नाही x и y: त्यांचे कदाचित इतर शेजारी असतील, आणि v ते इथे नाहीत.
2. जेव्हा x и y - शेजारी नाही. मग असे सांगितले आहे की सर्व तीन शिरोबिंदू एकामध्ये चिकटवले जाऊ शकतात. कल्पना अशी आहे की या प्रकरणात एक इष्टतम उत्तर आहे, ज्यामध्ये आपण एकतर घेतो v, किंवा दोन्ही शिरोबिंदू x и y. शिवाय, पहिल्या प्रकरणात आपल्याला प्रतिसादात सर्व शेजाऱ्यांना घ्यावे लागेल x и y, परंतु दुसऱ्यामध्ये ते आवश्यक नाही. हे तंतोतंत अशा प्रकरणांशी जुळते जेव्हा आपण प्रतिसादात चिकट शिरोबिंदू घेत नाही आणि जेव्हा करतो. हे लक्षात घेण्यासारखे आहे की दोन्ही प्रकरणांमध्ये अशा ऑपरेशनचा प्रतिसाद एकाने कमी होतो.

हे लक्षात घेण्यासारखे आहे की योग्य रेखीय वेळेत हा दृष्टिकोन अचूकपणे अंमलात आणणे खूप कठीण आहे. शिरोबिंदूंना ग्लूइंग करणे हे एक जटिल ऑपरेशन आहे; आपल्याला शेजाऱ्यांच्या याद्या कॉपी करणे आवश्यक आहे. जर हे निष्काळजीपणे केले गेले असेल, तर तुम्ही असिम्प्टोटिकली सबऑप्टिमल रनिंग टाइमसह समाप्त करू शकता (उदाहरणार्थ, जर तुम्ही प्रत्येक ग्लूइंगनंतर बर्याच कडा कॉपी केल्यास). मी पदवी 2 च्या शिरोबिंदूंमधून संपूर्ण मार्ग शोधण्यात आणि अशा शिरोबिंदूंवरील चक्र किंवा एक वगळता अशा सर्व शिरोबिंदूंसारख्या विशिष्ट प्रकरणांच्या समूहाचे विश्लेषण करण्यात स्थिर झालो.

याव्यतिरिक्त, हे ऑपरेशन उलट करता येण्यासारखे असणे आवश्यक आहे, जेणेकरून पुनरावृत्तीवरून परत येताना आम्ही आलेख त्याच्या मूळ स्वरूपात पुनर्संचयित करू. हे सुनिश्चित करण्यासाठी, मी विलीन केलेल्या शिरोबिंदूंच्या किनारी याद्या साफ केल्या नाहीत आणि नंतर मला माहित होते की कोणत्या कडा कुठे जायच्या आहेत. आलेखांच्या या अंमलबजावणीसाठी देखील अचूकता आवश्यक आहे, परंतु ते योग्य रेखीय वेळ प्रदान करते. आणि अनेक हजारो कडांच्या आलेखांसाठी, ते प्रोसेसर कॅशेमध्ये बसते, जे वेगात चांगले फायदे देते.

रेखीय कर्नल

शेवटी, कर्नलचा सर्वात मनोरंजक भाग.

सुरुवातीला, आठवा की द्विपक्षीय आलेखांमध्ये किमान शिरोबिंदू कव्हर वापरून शोधले जाऊ शकते . हे करण्यासाठी आपल्याला अल्गोरिदम वापरण्याची आवश्यकता आहे हॉपक्रॉफ्ट-कार्प तेथे जास्तीत जास्त जुळणी शोधण्यासाठी आणि नंतर प्रमेय वापरा König-Egervari.

रेखीय कर्नलची कल्पना अशी आहे: प्रथम आपण आलेख विभाजित करतो, म्हणजेच प्रत्येक शिरोबिंदूऐवजी v दोन शिखरे जोडू и , आणि प्रत्येक काठाच्या ऐवजी u - वि दोन बरगड्या घालू и . परिणामी आलेख द्विपक्षीय असेल. त्यातील किमान शिरोबिंदू कव्हर शोधू. मूळ आलेखाचे काही शिरोबिंदू तेथे दोनदा मिळतील, काही फक्त एकदाच आणि काही कधीच नाहीत. Nemhauser-Trotter प्रमेय असे सांगते की या प्रकरणात एकदाही न आदळलेले शिरोबिंदू काढू शकतात आणि दोनदा आदळलेले शिरोबिंदू परत घेऊ शकतात. शिवाय, ती म्हणते की उर्वरित शिरोबिंदूंपैकी (जे एकदा आदळतात) तुम्हाला किमान अर्धे उत्तर म्हणून घेणे आवश्यक आहे.

पेक्षा जास्त नाही सोडायला आपण शिकलो आहोत 2k शिखरे खरंच, जर उर्वरित उत्तर सर्व शिरोबिंदूंपैकी किमान अर्धे असेल, तर एकूण पेक्षा जास्त शिरोबिंदू नाहीत 2k.

येथे मी एक लहान पाऊल पुढे टाकू शकलो. हे स्पष्ट आहे की अशा प्रकारे तयार केलेले कर्नल द्विपक्षीय आलेखामध्ये आपण कोणत्या प्रकारचे किमान शिरोबिंदू कव्हर घेतले यावर अवलंबून आहे. मी एक घेऊ इच्छितो जेणेकरून उर्वरित शिरोबिंदूंची संख्या कमीतकमी असेल. पूर्वी, ते केवळ वेळेतच हे करू शकत होते . मी वेळेत या अल्गोरिदमच्या अंमलबजावणीसह आलो , अशा प्रकारे, प्रत्येक शाखांच्या टप्प्यावर हा कोर शेकडो हजारो शिरोबिंदूंच्या आलेखांमध्ये शोधला जाऊ शकतो.

परिणाम

सराव दर्शवितो की माझे सोल्यूशन शेकडो शिरोबिंदू आणि हजारो कडांच्या चाचण्यांवर चांगले कार्य करते. अशा चाचण्यांमध्ये अर्ध्या तासात उपाय सापडेल अशी अपेक्षा करणे शक्य आहे. स्वीकारार्ह वेळेत उत्तर शोधण्याची संभाव्यता, तत्त्वतः, जर आलेखामध्ये उच्च पदवीचे शिरोबिंदू पुरेशा प्रमाणात असतील तर, उदाहरणार्थ, पदवी 10 आणि उच्च.

स्पर्धेत सहभागी होण्यासाठी सोल्युशन्स कडे पाठवावे लागले optil.io. तेथे सादर केलेल्या माहितीवरून न्यायनिवाडा करून डॉ चिन्ह, खुल्या चाचण्यांमधील माझे समाधान वीस पैकी तिसऱ्या क्रमांकावर आहे, दुसऱ्या क्रमांकापासून मोठ्या अंतरासह. पूर्णपणे प्रामाणिकपणे सांगायचे तर, स्पर्धेतच सोल्यूशन्सचे मूल्यांकन कसे केले जाईल हे पूर्णपणे स्पष्ट नाही: उदाहरणार्थ, माझे समाधान चौथ्या स्थानावरील सोल्यूशनपेक्षा कमी चाचण्या उत्तीर्ण करते, परंतु जे उत्तीर्ण होतात त्यांच्यासाठी ते जलद कार्य करते.

बंद झालेल्या चाचण्यांचे निकाल १ जुलै रोजी कळतील.

स्त्रोत: www.habr.com