अनुकूलन खोजें

डिस्क्लेमर: इस लेख को समझने के लिए ग्राफ थ्योरी के शुरुआती ज्ञान, विशेष रूप से गहराई से खोज, चौड़ाई-पहली खोज और बेलमैन-फोर्ड एल्गोरिथ्म की आवश्यकता होती है ।

परिचय

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

इस पोस्ट में, मैं आपको बताऊंगा कि अधिकांश खोजों को कैसे अनुकूलित किया जाए, ताकि वे परिमाण के आदेशों को तेजी से काम करेंगे

पाशविक बल के बारे में अधिक

उदाहरण

ग्राफ जी में स्वयं-चौराहों के बिना अधिकतम लंबाई का रास्ता खोजने की समस्या के एक भोले समाधान पर विचार करें ।

हम गहराई से थोड़ा संशोधित ट्रैवर्सल लॉन्च करते हैं। अर्थात्, यह जाँचने के बजाय कि क्या हम एक शीर्ष पर गए हैं या नहीं, हम इस बात की जाँच करते हैं कि क्या शिखर वर्तमान पथ से संबंधित है। और अब, यदि वर्तमान वैश्विक परिणाम प्रत्येक पुनरावृत्ति पर अद्यतन किया जाता है, तो समस्या का उत्तर इस चर में होगा।

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

अधिकांश खोजों को राज्य ग्राफ पर खोज के रूप में दर्शाया जा सकता है।

और हम वास्तव में क्या देख रहे हैं

खोजें तीन प्रकार की होती हैं:

1) अस्तित्व का सत्यापन।
2) अधिकतम भार रहित ग्राफ पर अधिकतमकरण / न्यूनतमकरण।
3) भारित ग्राफ पर अधिकतमकरण / न्यूनतमकरण।

पहले दो समस्याओं को हल करने की भोली विधि के लिए, एक गहराई खोज या एक चौड़ाई-पहली खोज का उपयोग किया जाता है, और तीसरे के लिए - राज्य ग्राफ एस के अनुसार बेलमैन-फोर्ड एल्गोरिथ्म ।

और अब अनुकूलन स्वयं।

अनुकूलन संख्या 1: संस्मरण , या आलस्य

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

यदि राज्य का ग्राफ एस छोटा है, तो हम भाग्यशाली हैं - आप एक बूलियन सरणी बना सकते हैं, अन्यथा मेथोडिज़्म को एक हैश तालिका द्वारा कार्यान्वित किया जाता है।

यह आमतौर पर लागू करने के लिए मुश्किल नहीं है। हमें 2 पंक्तियों को जोड़ने की आवश्यकता है: शुरुआत में जाँच करें कि हम यहाँ नहीं थे, और अंत में लिखिए कि हम यहाँ थे।

अनुकूलन नंबर 2: उत्तर द्वारा क्लिपिंग

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

इस अनुकूलन का एक अच्छा उदाहरण ग्राफ जी में स्वयं-चौराहों के बिना अधिकतम लंबाई का एक रास्ता खोजना है । यह कार्य एनपी-पूर्ण है।

मान लीजिए कि हम ग्राफ एस के कुछ राज्य में हैं । यदि हम, जो कुछ भी कह सकते हैं, वह परिणाम में सुधार करने में विफल रहता है, तो यह वापसी के लायक है। अब हमें यह जानने की आवश्यकता है कि इसे कैसे जांचें। उदाहरण के लिए, आप राज्य पथ के अंतिम शीर्ष से ग्राफ G के पहुंच योग्य संख्याओं की संख्या की गणना कर सकते हैं और पहले से प्राप्त पथ की लंबाई जोड़ सकते हैं, फिर परिणामी संख्या s से प्राप्त होने वाले अधिकतम उत्तर की ऊपरी सीमा होगी। इसलिए, यदि यह वर्तमान परिणाम से कम है, तो आप इस राज्य से खोज शुरू नहीं कर सकते हैं।

यदि हम किसी विशिष्ट कार्य को अनदेखा करते हैं, तो हमें इस तरह के कार्य को चुनने की आवश्यकता है को जहां से प्राप्त होने वाली प्रतिक्रिया का अनुमान था, जहां राज्य की वर्तमान प्रतिक्रिया है।

यदि कार्य वास्तविकता को अच्छी तरह से प्रतिबिंबित करेगा, फिर यह अनुकूलन एल्गोरिथ्म को परिमाण के आदेशों द्वारा गति प्रदान कर सकता है।

उत्तर द्वारा क्लिपिंग शायद सबसे महत्वपूर्ण अनुकूलन है, क्योंकि इसका उपयोग कई अन्य अनुकूलन और विधियों द्वारा किया जाता है।

अनुकूलन # 3: लालच

लालच तब होता है जब हम वह सब कुछ हासिल कर लेते हैं जो पहली नज़र में अच्छा होता है। यही है, हम किनारे के साथ जाते हैं, जो हमें दूसरों की तुलना में अधिक आशाजनक लगता था। समस्या यह है कि लालच का जो उत्तर मिलता है वह जरूरी नहीं कि सबसे अच्छा हो, लेकिन हमारी रेटिंग जितनी अच्छी होगी, परिणाम उतना ही बेहतर होगा। मूल्यांकन समारोह के लिए, आप ले सकते हैं जवाब से कतरन से।

और अब क्रम में।

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

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

भारित रेखांकन के बारे में कुछ शब्द

आमतौर पर, बेलमैन-फोर्ड एल्गोरिथम कुछ इस तरह लिखा जाता है:

for v in vertices: for e in edges: relaxation(e) 

या आप इसे थोड़ा अलग तरीके से लिख सकते हैं: जैसे कि चौड़ाई-पहली खोज, लेकिन यह जाँचते हुए कि क्या हम इस राज्य में पहले गए हैं, वर्तमान और ज्ञापन की तुलना करें, और यदि याद रखना बेहतर है, तो इस जानवर-बल शाखा को काट दें।

"खराब" गहराई की खोज और चौड़ाई-पहली खोज से

कुछ तस्वीरें:

ग्राफ एस के विज़िट किए गए राज्यों के लाल सेट को क्रमशः गहराई और चौड़ाई में खोज के कुछ समय बाद हाइलाइट किया जाता है।

ये दोनों क्षेत्र एक स्थान पर बहुत मजबूती से स्थानीयकृत हैं। हमें किसी प्रकार के तंत्र की आवश्यकता है जो उत्तर को बेहतर बनाने के लिए ग्राफ एस भर में लाल क्षेत्र को वितरित करेगा, जिससे पुनरावृत्ति की बुरी शाखाओं को बंद करने में मदद मिलेगी।

यदि हम कम से कम समस्या का समाधान करते हैं, तो चौड़ाई-प्रथम खोज क्रियाएं तर्कसंगत लगती हैं, लेकिन, दुर्भाग्य से, कतरन के लिए इसका कोई जवाब मिलने की संभावना नहीं है।

खोज क्षेत्र चयन तंत्र

लालच

और फिर से लालच हमारे पास आया, लेकिन अब थोड़ी अलग नस में। पिछली बार, हमने किनारों को क्रमबद्ध किया और उन पर सभी क्रमिक रूप से क्लिक किया, लेकिन यह हमें ऊपर की तस्वीरों की तुलना में विश्व स्तर पर बहुत अधिक मदद नहीं करेगा।

हर कोई याद करता है कि एक नंबर 1 है और एक नंबर N है , लेकिन कई लोग यह भूल जाते हैं कि उनके बीच नंबर भी हैं। लालच एक किनारे की पसंद है, और एक गहरी खोज एन किनारों की पसंद है। आइए एक लालची गहराई की खोज लिखें जो पहले k किनारों पर जाएगी।

यदि इस पद्धति का उपयोग किया जाता है, तो एन्यूमरेशन ग्राफ़ एस के बहुत बड़े उप-योगों को बायपास करेगा ।

समस्या यह है कि यदि आप बहुत छोटी कश्मीर लेते हैं, तो उत्तर गलत हो सकता है, और यदि बहुत बड़ा है, तो पर्याप्त समय नहीं हो सकता है। समाधान काफी सरल है: आपको सभी संभव कश्मीर का चयन करना होगा। यही है, एक बाहरी लूप लिखें जो कश्मीर से 1 तक अनंत तक जाता है जब तक कि समय समाप्त नहीं हो जाता है, और लूप के शरीर में, एक समाधान की खोज करना शुरू करें।

यह समझना सार्थक है कि चूंकि ग्राफ के स्कैन किए गए राज्यों की संख्या कश्मीर के विकास के संबंध में तेजी से बढ़ती है, इसलिए इस चर पर 1 से k- 1 तक चलने से असममित जटिलता नहीं बढ़ेगी। सबसे खराब स्थिति में, ऑपरेटिंग समय लगातार समय से अधिक नहीं बढ़ेगा, लेकिन व्यवहार में यह एक अच्छे उत्तर के लिए क्लिपिंग के कारण काफी कम हो जाएगा।

Iterative गहरा होना

यह विधि, जैसा कि यह थी, गहरी खोज को उन कार्यों को करने के लिए मजबूर करती है जो यह आमतौर पर करता है।

विधि का सार एक वैश्विक चर बनाना है - अधिकतम गहराई जिसमें गहराई की खोज नीचे जानी चाहिए। के साथ के रूप में , हम इस गहराई पर बाहरी लूप शुरू करते हैं।

अब, एक गहरी खोज एक चौड़ाई-पहली खोज की तरह अधिक है, लेकिन इस अंतर के साथ कि यह क्लिपिंग के लिए तुरंत किसी तरह का जवाब देती है।

खोज कतार चौड़ाई सीमा

यह लालच भी है, लेकिन अब पहली खोज के लिए। नाम से यह स्पष्ट है कि हम कतार को सीमित करेंगे। ऐसा करने के लिए, हमारे पास फिर से एक वैश्विक चर है - कतार का आकार और 2 से अनंत तक पुनरावृति। लेकिन हम +1 के माध्यम से नहीं छांटेंगे, बल्कि एक स्थिर से गुणा करेंगे, उदाहरण के लिए, 2 से।

कुछ बिंदु पर, कतार का आकार चयनित अधिकतम आकार से अधिक होगा और किसी को ओवरबोर्ड पर फेंकना होगा। चयन करने के लिए, आपको कुछ विशेषता द्वारा सॉर्ट करने की आवश्यकता है। हम हमेशा की तरह, फंक्शन का उपयोग करेंगे शर्तों की तुलना के लिए।

अब इस सब से क्या लिखना

सर्वोत्तम परिणामों के लिए, लगभग सब कुछ और लगभग तुरंत लिखें।

सबसे पहले, हम संस्मरण के साथ थोड़ी देर के लिए एक गहरी खोज शुरू करते हैं, उत्तर द्वारा कतरन करते हैं, किनारों को छांटते हैं, और कश्मीर को छांटते हैं, लेकिन Iterative के बिना गहरा हो जाता है।
अगला, हम प्रतिक्रिया द्वारा कतरन के साथ चौड़ाई-पहली खोज शुरू करते हैं और कतार के आकार को सीमित करते हैं।

चौड़ाई-खोज में कतरन के लिए एक अच्छा उत्तर खोजने के लिए गहराई खोज की आवश्यकता होती है, और पहले से ही सबसे अच्छा उत्तर खोजने के लिए चौड़ाई-पहली खोज की आवश्यकता होती है। यह टीम हॉजपॉज कई धमाकेदार कार्यों में अच्छा प्रदर्शन करती है।

अब थोड़ा अभ्यास

ग्राफ में आत्म-चौराहों के बिना अधिकतम पथ का पता लगाना

रैंडम ग्राफ: 18 कोने, 54 किनारे।
काम का समय:
कोई अनुकूलन ~ 4 सेकंड।
संस्मरण, प्रतिक्रिया की कतरन ~ 0.2 मि।

रैंडम ग्राफ: 30 कोने, 90 किनारे।
कोई अनुकूलन नहीं> 1 घंटा (इंतजार नहीं किया)।
संस्मरण, प्रतिक्रिया कटऑफ ~ 0.5 s।
संस्मरण, प्रतिक्रिया क्लिपिंग, लालच ~ 10 एमएस।