प्यारामिटराइज्ड एल्गोरिदमको साथ NP-हार्ड समस्याहरू कसरी समाधान गर्ने

अनुसन्धान कार्य सायद हाम्रो प्रशिक्षणको सबैभन्दा रोचक भाग हो। विचार भनेको विश्वविद्यालयमा हुँदा पनि आफ्नो रोजेको दिशामा आफैलाई प्रयास गर्ने हो। उदाहरणका लागि, सफ्टवेयर इन्जिनियरिङ र मेसिन लर्निङका क्षेत्रका विद्यार्थीहरू प्राय: कम्पनीहरूमा अनुसन्धान गर्न जान्छन् (मुख्य रूपमा JetBrains वा Yandex, तर मात्र होइन)।

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

आजकल, NP-हार्ड समस्याहरूको लागि एक रोचक दृष्टिकोण धेरै चाँडै विकास भइरहेको छ - प्यारामिटराइज्ड एल्गोरिदम। म तपाईंलाई गतिमा ल्याउने प्रयास गर्नेछु, तपाईंलाई केही सरल प्यारामिटराइज्ड एल्गोरिदमहरू बताउनेछु र मलाई धेरै मद्दत गर्ने एउटा शक्तिशाली विधिको वर्णन गर्नेछु। मैले PACE च्यालेन्ज प्रतियोगितामा मेरो नतिजाहरू प्रस्तुत गरें: खुला परीक्षणको नतिजा अनुसार, मेरो समाधानले तेस्रो स्थान लिन्छ, र अन्तिम नतिजा जुलाई 1 मा थाहा हुनेछ।

मेरो बारेमा

मेरो नाम Vasily Alferov हो, म अहिले नेशनल रिसर्च युनिभर्सिटी हायर स्कूल अफ इकोनोमिक्स - सेन्ट पिटर्सबर्गमा तेस्रो वर्ष पूरा गर्दैछु। म मस्को स्कूल नम्बर 179 मा पढ्दा र कम्प्युटर विज्ञान ओलम्पियाडमा सफलतापूर्वक भाग लिएको बेलादेखि नै मलाई एल्गोरिदमहरूमा रुचि थियो।

प्यारामिटराइज्ड एल्गोरिदममा विशेषज्ञहरूको एक सीमित संख्या बारमा प्रवेश गर्दछ ...

पुस्तकबाट लिइएको उदाहरण "पैरामिटराइज्ड एल्गोरिदमहरू"

कल्पना गर्नुहोस् कि तपाईं एउटा सानो शहरमा बार सुरक्षा गार्ड हुनुहुन्छ। प्रत्येक शुक्रबार, आधा सहर आराम गर्न तपाईंको बारमा आउँछ, जसले तपाईंलाई धेरै समस्या दिन्छ: तपाईंले झगडा रोक्नको लागि डरलाग्दो ग्राहकहरूलाई बारबाट बाहिर फाल्नुपर्छ। अन्ततः, तपाईं थकित हुनुहुन्छ र निवारक उपायहरू लिने निर्णय गर्नुहुन्छ।

तपाईंको सहर सानो भएकोले, तपाईंलाई ठ्याक्कै थाहा छ कि कुन जोडा संरक्षकहरूले लड्न सक्ने सम्भावना छ यदि तिनीहरू सँगै बारमा समाप्त हुन्छन्। के तपाईंसँग सूची छ n मानिसहरू जो आज राती बारमा आउनेछन्। तपाइँ कसैलाई झगडा नगरी बारबाट केही नगरवासीहरूलाई बाहिर राख्ने निर्णय गर्नुहुन्छ। एकै समयमा, तपाइँका मालिकहरू नाफा गुमाउन चाहँदैनन् र यदि तपाइँ भन्दा बढी दिनुहुन्न भने दुखी हुनेछन्। k मान्छे।

दुर्भाग्यवश, तपाईको अगाडिको समस्या क्लासिक NP-हार्ड समस्या हो। तिमिले उनलाई चिन्नुहुन्छ होला वर्टेक्स कभर, वा शीर्ष आवरण समस्याको रूपमा। त्यस्ता समस्याहरूको लागि, सामान्य अवस्थामा, स्वीकार्य समयमा काम गर्ने कुनै एल्गोरिदमहरू छैनन्। सटीक हुनको लागि, अप्रमाणित र धेरै बलियो परिकल्पना ETH (एक्सपोनेन्शियल टाइम हाइपोथेसिस) ले यो समस्यालाई समयमै समाधान गर्न सकिँदैन भनेर बताउँछ। , त्यो हो, तपाईले पूर्ण खोजी भन्दा राम्रो केहि सोच्न सक्नुहुन्न। उदाहरण को लागी, मानौं कोही तपाईको बारमा आउँदैछ n = 1000 मानव। त्यसपछि पूर्ण खोज हुनेछ विकल्पहरू जुन त्यहाँ लगभग छन् - पागल रकम। सौभाग्य देखि, तपाइँको व्यवस्थापनले तपाइँलाई एक सीमा दिएको छ k = २, त्यसैले तपाईंले पुनरावृत्ति गर्न आवश्यक संयोजनहरूको संख्या धेरै सानो छ: दस तत्वहरूको उपसेटहरूको संख्या । यो राम्रो छ, तर यो अझै पनि शक्तिशाली क्लस्टरमा पनि एक दिनमा गणना गरिने छैन।

बारका आगन्तुकहरू बीचको तनावपूर्ण सम्बन्धको यो कन्फिगरेसनमा झगडाको सम्भावनालाई हटाउन, तपाईंले बब, डेनियल र फेडरलाई बाहिर राख्नु पर्छ। त्यहाँ कुनै समाधान छैन जसमा दुई मात्र पछाडि छोडिनेछ।

के यसको मतलब यो समय दिनु र सबैलाई भित्र जान दिनु हो? अन्य विकल्पहरू विचार गरौं। ठीक छ, उदाहरणका लागि, तपाईले धेरै संख्यामा मानिसहरूसँग लड्न सक्ने सम्भावना भएकाहरूलाई मात्र अनुमति दिन सक्नुहुन्न। यदि कोहीसँग लड्न सक्छ भने k + १ अर्को व्यक्ति, तब तपाइँ निश्चित रूपमा उसलाई भित्र जान दिन सक्नुहुन्न - अन्यथा तपाइँ सबैलाई बाहिर राख्नु पर्छ k + १ शहरवासीहरू, जससँग उसले लड्न सक्छ, जसले नेतृत्वलाई पक्कै निराश पार्छ।

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

यदि तपाइँ कुनै पनि द्वन्द्व नभएका व्यक्तिहरूलाई सुरक्षित रूपमा लिन सक्नुहुन्छ भने, त्यसोभए एक मात्र द्वन्द्वमा भाग लिनेहरूको बारेमा के हुन्छ? वास्तवमा, उनीहरूलाई उनीहरूको विपक्षीमाथि ढोका बन्द गरेर पनि भित्र जान दिइन्छ। वास्तवमा, यदि एलिस बबसँग मात्र द्वन्द्वमा छ भने, यदि हामीले एलिसलाई ती दुई मध्येबाट बाहिर दियौं भने, हामी हराउने छैनौं: बबसँग अन्य विवादहरू हुन सक्छन्, तर एलिससँग पक्कै छैन। यसबाहेक, हामी दुवैलाई भित्र जान नदिने कुनै अर्थ छैन। त्यस्ता अपरेशनहरू पछि त्यहाँ कुनै पनि बाँकी छैन एक अनसुलझे भाग्य संग अतिथिहरु: हामीसँग मात्र छ द्वन्द्वहरू, प्रत्येक दुई सहभागीहरू र प्रत्येक कम्तिमा दुईमा संलग्न छन्। त्यसैले बाँकी सबै मार्फत क्रमबद्ध गर्न हो विकल्पहरू, जुन सजिलै ल्यापटपमा आधा दिन मान्न सकिन्छ।

वास्तवमा, सरल तर्क संग तपाईं अझ आकर्षक अवस्था प्राप्त गर्न सक्नुहुन्छ। ध्यान दिनुहोस् कि हामीले निश्चित रूपमा सबै विवादहरू समाधान गर्न आवश्यक छ, अर्थात्, प्रत्येक विवादित जोडीबाट, कम्तिमा एक व्यक्ति छान्नुहोस् जसलाई हामी भित्र जान दिने छैनौं। निम्न एल्गोरिथ्मलाई विचार गरौं: कुनै पनि द्वन्द्व लिनुहोस्, जसबाट हामीले एउटा सहभागीलाई हटाउँछौं र बाँकीबाट पुनरावर्ती सुरु गर्छौं, त्यसपछि अर्को हटाउँछौं र पुनरावर्ती रूपमा पनि सुरु गर्छौं। हामीले प्रत्येक पाइलामा कसैलाई बाहिर निकाल्ने हुनाले, यस्तो एल्गोरिदमको पुनरावृत्ति रूख गहिराइको बाइनरी रूख हो। k, त्यसैले कुल मा एल्गोरिथ्म मा काम गर्दछ कहाँ n ठाडो संख्या हो, र m - रिब संख्या। हाम्रो उदाहरणमा, यो लगभग दस लाख हो, जुन ल्यापटपमा मात्र होइन, तर मोबाइल फोनमा पनि विभाजित सेकेन्डमा गणना गर्न सकिन्छ।

माथिको उदाहरण एउटा उदाहरण हो प्यारामिटराइज्ड एल्गोरिथ्म। प्यारामिटराइज्ड एल्गोरिदमहरू एल्गोरिदमहरू हुन् जुन समयमा चल्छन् f(k) poly(n)कहाँ p - बहुपद, f एक मनमानी कम्प्युटेबल प्रकार्य हो, र k - केहि प्यारामिटर, जुन, सम्भवतः, समस्या को आकार भन्दा धेरै सानो हुनेछ।

यो एल्गोरिदम अघि सबै तर्क एक उदाहरण दिन्छ कर्नेलाइजेशन प्यारामिटराइज्ड एल्गोरिदमहरू सिर्जना गर्ने सामान्य प्रविधिहरू मध्ये एक हो। कर्नेलाइजेशन भनेको मापदण्डको प्रकार्यद्वारा सीमित मानमा समस्याको आकार घटाउनु हो। परिणामस्वरूप समस्या अक्सर कर्नेल भनिन्छ। यसरी, vertices को डिग्री को बारे मा साधारण तर्क द्वारा, हामीले Vertex Cover समस्या को लागी एक quadratic कर्नेल प्राप्त गर्यौं, उत्तर को आकार द्वारा प्यारामिटराइज्ड। त्यहाँ अन्य सेटिङहरू छन् जुन तपाईंले यस कार्यको लागि छनोट गर्न सक्नुहुन्छ (जस्तै Vertex Cover Above LP), तर यो हामीले छलफल गर्ने सेटिङ हो।

गति चुनौती

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

प्रतियोगिता हरेक वर्ष लोकप्रिय हुँदै गइरहेको छ। यदि तपाइँ प्रारम्भिक तथ्याङ्कलाई विश्वास गर्नुहुन्छ भने, यो वर्ष 24 टोलीले भेर्टेक्स कभरिङ समस्या समाधान गर्न प्रतिस्पर्धामा भाग लिए। यो ध्यान दिन लायक छ कि प्रतियोगिता धेरै घण्टा वा एक हप्ता सम्म, तर धेरै महिना सम्म रहन्छ। टोलीहरूसँग साहित्य अध्ययन गर्ने, आफ्नै मौलिक विचार ल्याउने र त्यसलाई कार्यान्वयन गर्ने प्रयास गर्ने अवसर छ। संक्षेपमा, यो प्रतियोगिता एक अनुसन्धान परियोजना हो। सबैभन्दा प्रभावकारी समाधानका लागि विचारहरू र विजेताहरूको पुरस्कार सम्मेलनको संयोजनमा आयोजित गरिनेछ आईपेक (International Symposium on Parameterized and Exact Computation) युरोपको सबैभन्दा ठूलो वार्षिक एल्गोरिदमिक बैठकको भागको रूपमा algo। प्रतियोगिता बारे थप विस्तृत जानकारी मा पाउन सकिन्छ साइटर विगतका वर्षहरूको नतिजा झूटो हो यहाँ.

समाधान रेखाचित्र

भेर्टेक्स कभरिङ समस्या समाधान गर्न, मैले प्यारामिटराइज्ड एल्गोरिदमहरू प्रयोग गर्ने प्रयास गरें। तिनीहरू सामान्यतया दुई भागहरू हुन्छन्: सरलीकरण नियमहरू (जसले आदर्श रूपमा कर्नेलाइजेसनमा नेतृत्व गर्दछ) र विभाजन नियमहरू। सरलीकरण नियमहरू बहुपद समयमा इनपुटको पूर्व-प्रशोधन हो। त्यस्ता नियमहरू लागू गर्नुको उद्देश्य समस्यालाई बराबरको सानो समस्यामा कम गर्नु हो। सरलीकरण नियमहरू एल्गोरिदमको सबैभन्दा महँगो भाग हो, र यो भाग लागू गर्दा कुल चलिरहेको समय हुन्छ। साधारण बहुपद समयको सट्टा। हाम्रो अवस्थामा, विभाजन नियमहरू यस तथ्यमा आधारित छन् कि प्रत्येक शीर्षको लागि तपाईंले यसलाई वा यसको छिमेकीलाई जवाफको रूपमा लिन आवश्यक छ।

सामान्य योजना यो हो: हामी सरलीकरण नियमहरू लागू गर्छौं, त्यसपछि हामी केही vertex चयन गर्छौं, र दुई पुनरावर्ती कलहरू बनाउँछौं: पहिलोमा हामी यसलाई प्रतिक्रियामा लिन्छौं, र अर्कोमा हामी यसको सबै छिमेकीहरू लिन्छौं। जसलाई हामी यस शीर्षमा विभाजन (शाखाहरू) भन्छौं।

अर्को अनुच्छेदमा यस योजनामा ​​ठ्याक्कै एउटा थपिनेछ।

विभाजन (ब्रंचिङ) नियमहरूको लागि विचारहरू

टुक्राटुक्रा हुने माथिल्लो भाग कसरी छान्ने भनेर छलफल गरौं।
मुख्य विचार एल्गोरिथमिक अर्थमा धेरै लोभी छ: अधिकतम डिग्रीको शीर्ष लिनुहोस् र यसको साथ विभाजित गर्नुहोस्। यो किन राम्रो देखिन्छ? किनभने पुनरावर्ती कलको दोस्रो शाखामा हामी यस तरिकाले धेरै vertices हटाउनेछौं। तपाईंले बाँकी रहेको सानो ग्राफमा गणना गर्न सक्नुहुन्छ र हामी यसमा छिट्टै काम गर्न सक्छौं।

यो दृष्टिकोण, पहिले नै छलफल गरिएको सरल कर्नेलाइजेसन प्रविधिहरूसँग, आफैलाई राम्रोसँग देखाउँछ र आकारमा धेरै हजार शीर्षहरूका केही परीक्षणहरू समाधान गर्दछ। तर, उदाहरणका लागि, यसले क्यूबिक ग्राफहरूका लागि राम्रोसँग काम गर्दैन (अर्थात, ग्राफहरू जसको प्रत्येक शीर्षको डिग्री तीन हो)।
त्यहाँ एकदम सरल विचारमा आधारित अर्को विचार छ: यदि ग्राफ विच्छेद गरिएको छ भने, यसको जडान कम्पोनेन्टहरूमा समस्या स्वतन्त्र रूपमा समाधान गर्न सकिन्छ, अन्तमा जवाफहरू संयोजन गर्दै। यो, वैसे, योजनामा ​​​​एक सानो प्रतिज्ञा गरिएको परिमार्जन हो, जसले समाधानलाई महत्त्वपूर्ण रूपमा गति दिनेछ: पहिले, यस अवस्थामा, हामीले कम्पोनेन्टहरूको प्रतिक्रियाहरू गणना गर्नको लागि समयको उत्पादनको लागि काम गर्यौं, तर अब हामी काम गर्छौं। योगफल। र शाखाको गति बढाउनको लागि, तपाईंले जडान गरिएको ग्राफलाई विच्छेदनमा बदल्न आवश्यक छ।

यो कसरी गर्ने? यदि ग्राफमा एक अभिव्यक्ति बिन्दु छ भने, तपाइँ यसमा लड्न आवश्यक छ। एक आर्टिक्युलेसन बिन्दु एक शीर्ष हो जसलाई हटाइएमा, ग्राफले यसको जडान गुमाउँछ। ग्राफमा सबै जंक्शन बिन्दुहरू रैखिक समयमा शास्त्रीय एल्गोरिथ्म प्रयोग गरेर फेला पार्न सकिन्छ। यो दृष्टिकोणले महत्त्वपूर्ण रूपमा शाखा विस्तारलाई गति दिन्छ।

जब कुनै पनि चयन गरिएका ठाडोहरू हटाइन्छ, ग्राफ जडान गरिएका घटकहरूमा विभाजित हुनेछ।

हामी यो गर्नेछौं, तर हामी थप चाहन्छौं। उदाहरणका लागि, ग्राफमा सानो vertex cuts खोज्नुहोस् र यसबाट vertices सँगै विभाजित गर्नुहोस्। न्यूनतम ग्लोबल भेर्टेक्स काट फेला पार्ने सबैभन्दा प्रभावकारी तरिका भनेको गोमोरी-हु रूख प्रयोग गर्नु हो, जुन घन समयमा बनाइएको छ। PACE च्यालेन्जमा, सामान्य ग्राफ साइज धेरै हजार ठाडो हुन्छ। यस अवस्थामा, पुनरावृत्ति रूखको प्रत्येक शीर्षमा अरबौं अपरेशनहरू गर्न आवश्यक छ। यो आवंटित समयमा समस्या समाधान गर्न असम्भव छ भनेर बाहिर जान्छ।

समाधान अनुकूलन गर्न प्रयास गरौं। अधिकतम प्रवाह निर्माण गर्ने कुनै पनि एल्गोरिदमद्वारा ठाडोको जोडीको बीचमा काटिएको न्यूनतम vertex फेला पार्न सकिन्छ। तपाइँ यसलाई यस्तो नेटवर्कमा दिन सक्नुहुन्छ Dinitz एल्गोरिथ्म, व्यवहार मा यो धेरै छिटो काम गर्दछ। मलाई शङ्का छ कि सैद्धान्तिक रूपमा सञ्चालन समयको लागि अनुमान प्रमाणित गर्न सम्भव छ , जुन पहिले नै धेरै स्वीकार्य छ।

मैले अनियमित ठाडोहरूका जोडीहरू बीचको कटौती खोज्न र सबैभन्दा सन्तुलित एउटा लिन धेरै पटक प्रयास गरें। दुर्भाग्यवश, यसले खुला PACE चुनौती परीक्षणमा खराब नतिजाहरू उत्पादन गर्‍यो। मैले यसलाई एल्गोरिथ्मसँग तुलना गरें जसले अधिकतम डिग्रीको शीर्षहरू विभाजित गर्दछ, तिनीहरूलाई वंशको गहिराइमा सीमितताको साथ चलाउँछ। एउटा एल्गोरिथ्मले यस तरिकाले ठूला ग्राफहरू पछाडि छोडेर काट्ने प्रयास गरिरहेको छ। यो तथ्यको कारण हो कि कटौती धेरै असंतुलित भयो: 5-10 ठाडोहरू हटाएपछि, यो 15-20 मात्र विभाजित गर्न सम्भव थियो।

यो ध्यान दिन लायक छ कि सैद्धान्तिक रूपमा छिटो एल्गोरिदमको बारेमा लेखहरूले विभाजनको लागि ठाडोहरू चयन गर्न धेरै उन्नत प्रविधिहरू प्रयोग गर्दछ। त्यस्ता प्रविधिहरूसँग धेरै जटिल कार्यान्वयन हुन्छ र समय र मेमोरीको सन्दर्भमा अक्सर खराब प्रदर्शन हुन्छ। मैले अभ्यासका लागि स्वीकार्य हुनेहरू पहिचान गर्न असमर्थ थिएँ।

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

हामीसँग पहिले नै कर्नेलाइजेशनका लागि विचारहरू छन्। मलाई तपाईलाई सम्झाउन दिनुहोस्:

1. यदि त्यहाँ एक अलग ठाडो छ भने, यसलाई मेटाउनुहोस्।
2. यदि त्यहाँ डिग्री 1 को शीर्ष छ भने, यसलाई हटाउनुहोस् र प्रतिक्रियामा यसको छिमेकी लिनुहोस्।
3. यदि त्यहाँ कम्तिमा डिग्री को शीर्ष छ k + १, फिर्ता लिनुहोस्।

पहिलो दुई संग सबै कुरा स्पष्ट छ, तेस्रो संग त्यहाँ एक चाल छ। यदि पट्टीको बारेमा हास्य समस्यामा हामीलाई माथिल्लो सीमा दिइएको थियो k, त्यसपछि PACE चुनौतीमा तपाईंले भर्खरै न्यूनतम आकारको भेर्टेक्स कभर फेला पार्न आवश्यक छ। यो निर्णय समस्याहरूमा खोज समस्याहरूको एक विशिष्ट रूपान्तरण हो; प्रायः दुई प्रकारका समस्याहरू बीच कुनै भिन्नता हुँदैन। अभ्यासमा, यदि हामीले भेर्टेक्स कभर गर्ने समस्याको लागि समाधानकर्ता लेखिरहेका छौं भने, त्यहाँ फरक हुन सक्छ। उदाहरण को लागी, तेस्रो बिन्दु मा।

कार्यान्वयनको दृष्टिकोणबाट, अगाडि बढ्ने दुई तरिकाहरू छन्। पहिलो दृष्टिकोणलाई पुनरावृत्ति गहिरो भनिन्छ। यो निम्नानुसार छ: हामी जवाफमा तलबाट केही उचित अवरोधको साथ सुरु गर्न सक्छौं, र त्यसपछि यस बाधाभन्दा पुनरावृत्तिमा तल नजाइकन, माथिबाट जवाफमा बाधाको रूपमा यो अवरोध प्रयोग गरेर हाम्रो एल्गोरिदम चलाउन सक्छौं। यदि हामीले केही जवाफ फेला पारेका छौं भने, यो इष्टतम हुने ग्यारेन्टी छ, अन्यथा हामी यो सीमा एकले बढाएर फेरि सुरु गर्न सक्छौं।

अर्को दृष्टिकोण केहि हालको इष्टतम जवाफ भण्डारण गर्ने र सानो जवाफ खोज्ने हो, फेला पर्दा यो प्यारामिटर परिवर्तन गर्नुहोस् k खोजीमा अनावश्यक शाखाहरू काट्नको लागि।

धेरै राती प्रयोगहरू सञ्चालन गरेपछि, मैले यी दुई विधिहरूको संयोजनमा बसेँ: पहिले, म खोजको गहिराइमा केही प्रकारको सीमाको साथ मेरो एल्गोरिदम चलाउँछु (यसलाई चयन गर्ने ताकि यसले मुख्य समाधानको तुलनामा नगण्य समय लिन्छ) र उत्तम प्रयोग गर्नुहोस्। उत्तरको माथिल्लो सीमाको रूपमा समाधान फेला पर्यो - त्यो हो, एउटै कुरामा k.

डिग्री 2 को ठाडो

हामीले डिग्री ० र १ को ठाडोसँग व्यवहार गरेका छौं। यो बाहिर जान्छ कि यो डिग्री 0 को ठाडो को साथ गर्न सकिन्छ, तर यो ग्राफ देखि अधिक जटिल अपरेशन आवश्यक हुनेछ।

यसलाई व्याख्या गर्न, हामीले कुनै न कुनै रूपमा ठाडोहरू निर्दिष्ट गर्न आवश्यक छ। डिग्री २ को भेर्टेक्सलाई भेर्टेक्स भनिन्छ v, र यसको छिमेकीहरू - ठाडो x и y। अर्को हामीसँग दुईवटा केसहरू हुनेछन्।

1. कहिले x и y - छिमेकि। त्यसपछि तपाईं जवाफ दिन सक्नुहुन्छ x и yर v मेटाउन। वास्तवमा, यस त्रिकोणबाट कम्तिमा दुईवटा ठाडोहरू बदलामा लिन आवश्यक छ, र यदि हामीले लियौं भने हामी निश्चित रूपमा हराउने छैनौं। x и y: तिनीहरूका अन्य छिमेकीहरू छन्, र v त्यहाँ तिनीहरू कोही पनि छैनन्।
2. कहिले x и y - छिमेकी होइन। त्यसपछि यो भनिएको छ कि सबै तीन ठाडो एक मा टाँसिएको हुन सक्छ। विचार यो छ कि यस अवस्थामा त्यहाँ एक इष्टतम जवाफ छ, जसमा हामी या त लिन्छौं v, वा दुवै ठाडो x и y। यसबाहेक, पहिलो अवस्थामा हामीले सबै छिमेकीहरूलाई प्रतिक्रियामा लिनुपर्छ x и y, तर दोस्रो मा यो आवश्यक छैन। यो ठ्याक्कै ती केसहरूसँग मेल खान्छ जब हामी प्रतिक्रियामा टाँसिएको भेर्टेक्स लिदैनौं र जब हामी गर्छौं। यो ध्यान दिन मात्र बाँकी छ कि दुबै अवस्थामा यस्तो अपरेशनबाट प्रतिक्रिया एकले घट्छ।

यो ध्यान दिन लायक छ कि यो दृष्टिकोण उचित रैखिक समयमा सही रूपमा लागू गर्न धेरै गाह्रो छ। Gluing ठाडो एक जटिल कार्य हो; तपाईंले छिमेकीहरूको सूची प्रतिलिपि गर्न आवश्यक छ। यदि यो लापरवाहीपूर्वक गरिएको छ भने, तपाइँ asymptotically suboptimal चलिरहेको समयको साथ समाप्त गर्न सक्नुहुन्छ (उदाहरणका लागि, यदि तपाइँ प्रत्येक gluing पछि धेरै किनाराहरू प्रतिलिपि गर्नुहुन्छ)। मैले डिग्री 2 को भेर्टिसहरूबाट सम्पूर्ण मार्गहरू फेला पार्न र विशेष केसहरूको गुच्छाको विश्लेषण गर्नमा बसेँ, जस्तै त्यस्ता ठाडोहरूबाट चक्रहरू वा एउटा बाहेक सबै त्यस्ता शीर्षहरूबाट।

थप रूपमा, यो आवश्यक छ कि यो अपरेशन उल्टाउन मिल्छ, ताकि पुनरावृत्तिबाट फर्कँदा हामी ग्राफलाई यसको मूल रूपमा पुनर्स्थापित गर्छौं। यो सुनिश्चित गर्न, मैले मर्ज गरिएका ठाडोहरूको किनारा सूचीहरू खाली गरिन, र त्यसपछि मलाई कुन किनारहरू कहाँ जान आवश्यक छ भन्ने थाहा थियो। ग्राफको यो कार्यान्वयनलाई पनि शुद्धता चाहिन्छ, तर यसले उचित रैखिक समय प्रदान गर्दछ। र धेरै दसौं हजार किनाराहरूको ग्राफहरूको लागि, यो प्रोसेसर क्यासमा फिट हुन्छ, जसले गतिमा ठूलो फाइदाहरू दिन्छ।

रैखिक कर्नेल

अन्तमा, कर्नेल को सबै भन्दा रोचक भाग।

सुरु गर्नको लागि, सम्झनुहोस् कि द्विपक्षीय ग्राफहरूमा न्यूनतम भेर्टेक्स कभर प्रयोग गरी फेला पार्न सकिन्छ। । यो गर्न को लागी तपाईले एल्गोरिथ्म प्रयोग गर्न आवश्यक छ Hopcroft-Karp त्यहाँ अधिकतम मिल्दो फेला पार्नको लागि, र त्यसपछि प्रमेय प्रयोग गर्नुहोस् König-Egervari.

रैखिक कर्नेलको विचार यो हो: पहिले हामी ग्राफलाई विभाजित गर्छौं, त्यो हो, प्रत्येक vertex को सट्टा v दुई चोटी थपौं и , र प्रत्येक किनाराको सट्टा u - वि दुई रिबहरू थपौं и । नतिजा ग्राफ द्विपक्षीय हुनेछ। यसमा न्यूनतम vertex cover फेला पारौं। मूल ग्राफका केही ठाडोहरू त्यहाँ दुई पटक, केही मात्र एक पटक, र केही कहिल्यै प्राप्त हुनेछन्। Nemhauser-Trotter प्रमेय बताउँछ कि यस अवस्थामा एक चोटि एक चोटि हिट नभएको ठाडो हटाउन र दुई चोटि हिट फिर्ता लिन सक्छ। यसबाहेक, उनी भन्छिन् कि बाँकी vertices मध्ये (एक पटक हिट) तपाईंले जवाफको रूपमा कम्तिमा आधा लिन आवश्यक छ।

हामीले भर्खरै छोड्न सिकेका छौं 2k चुचुराहरू साँच्चै, यदि बाँकी उत्तर कम्तिमा सबै vertices को आधा हो भने, त्यहाँ कुल मा कुनै पनि vertices भन्दा 2k.

यहाँ मैले एउटा सानो कदम अगाडि बढाउन सक्षम भएँ। यो स्पष्ट छ कि यस तरिकाले बनाइएको कर्नेल हामीले द्विपक्षीय ग्राफमा कस्तो प्रकारको न्यूनतम भेर्टेक्स कभर लियौं भन्ने कुरामा निर्भर गर्दछ। म एउटा लिन चाहन्छु ताकि बाँकी ठेगानाहरूको संख्या न्यूनतम होस्। पहिले, तिनीहरूले यो समय मा मात्र गर्न सक्षम थिए । मैले यो एल्गोरिथ्मको कार्यान्वयनको साथ समय मा आए , यसरी, यस कोरलाई प्रत्येक शाखाको चरणमा सयौं हजार ठाडोको ग्राफमा खोज्न सकिन्छ।

परिणाम

अभ्यासले देखाउँछ कि मेरो समाधानले धेरै सय ठाडो र धेरै हजार किनारहरूको परीक्षणमा राम्रोसँग काम गर्छ। त्यस्ता परीक्षणहरूमा यो आशा गर्न सम्भव छ कि आधा घण्टामा समाधान फेला पर्नेछ। स्वीकार्य समयमा जवाफ फेला पार्ने सम्भावना, सिद्धान्तमा, यदि ग्राफमा पर्याप्त मात्रामा उच्च डिग्रीको शीर्षहरू छन् भने, उदाहरणका लागि, डिग्री 10 र उच्च।

प्रतियोगितामा भाग लिनको लागि समाधान पठाउनु पर्ने थियो optil.io। त्यहाँ प्रस्तुत जानकारी द्वारा न्याय चिन्ह, खुला परीक्षणहरूमा मेरो समाधान दोस्रो बाट ठूलो अन्तरको साथ बीस मध्ये तेस्रो स्थानमा छ। पूर्ण रूपमा इमानदार हुनको लागि, यो पूर्ण रूपमा स्पष्ट छैन कि कसरी समाधानहरू प्रतिस्पर्धामा नै मूल्याङ्कन गरिनेछ: उदाहरणका लागि, मेरो समाधानले चौथो स्थानमा रहेको समाधान भन्दा कम परीक्षणहरू पास गर्छ, तर पास हुनेहरूमा, यसले छिटो काम गर्छ।

बन्द परीक्षणको नतिजा जुलाई १ मा थाहा हुनेछ।

स्रोत: www.habr.com