एक बड़े ग्राफ़ (यात्रा विक्रेता समस्या) में हैमिल्टन चक्र की खोज करें। भाग 1

1. समस्या का विवरण

500 आवृत्तियों का एक पूर्ण भारित ग्राफ एक आसन्न मैट्रिक्स द्वारा दिया गया है।
इस ग्राफ में हैमिल्टनियन चक्र को कम से कम कुल लागत का पता लगाना आवश्यक है।

2. निर्णय

1. लालची एल्गोरिथ्म

यहां सब कुछ सरल है, हम किसी भी शीर्ष से शुरू करते हैं, उस किनारे की न्यूनतम लागत का चयन करें जिससे हम जा सकते हैं, शीर्ष पर जाएँ x, हमारे शीर्ष को पार करें, शीर्ष पर x, आदि।
सरल और तेज।
हालाँकि, उत्तर बहुत, सच्चाई से बहुत दूर हो सकता है।
Zhadina एक यादृच्छिक ग्राफ पर अच्छा काम करता है, लेकिन यहां हम ग्राफ़ के बारे में कुछ नहीं जानते हैं।
इसलिए, हम आगे बढ़ते हैं।

2. निष्पक्ष खोज

सेल्समैन का कार्य, यह न्यूनतम कुल लागत के हैमिल्टन चक्र की खोज भी है - एनपी-भारी है, इसलिए इस तरह के ग्राफ की पूरी खोज हमेशा के लिए रह सकती है, इसलिए यह विचार काम नहीं करता है।

3. शाखाओं और सीमाओं की विधि

दूसरा विचार जो मन में आया था वह एल्गोरिथ्म के प्रत्येक चरण में स्पष्ट रूप से गैर-इष्टतम समाधानों को त्यागने के लिए, सुगमता से उपयोग करने का था।

इस तरह के सबसे प्रभावी एल्गोरिदम में से एक शाखा-और-बाउंड विधि ("बैकट्रैकिंग") है जिसे लिटिल, मेर्टी, स्वीनी, केरल द्वारा 1963 में विकसित किया गया था।

बता दें कि S (0) n सेल्समैन और कॉस्ट मैट्रिक्स c के साथ ट्रैवलिंग सेल्समैन समस्या के सभी स्वीकार्य बंद मार्गों का समूह है।
लिटिल की विधि सेट को दो असंबद्ध सबसेट में विभाजित करने और उनमें से प्रत्येक के अनुमानों की गणना करने पर आधारित है। अगला, न्यूनतम अनुमान (लागत) के साथ सबसेट को दो सबसेट में विभाजित किया गया है और उनके अनुमानों की गणना की गई है। प्रत्येक चरण में, इस चरण में प्राप्त सभी अनुमानों में से सबसे छोटे के साथ एक सबसेट को चुना जाता है और इसे दो सबसेट में विभाजित किया जाता है। अंत में, हमें एक उपसमूह मिलता है जिसमें एक चक्र (एक बंद मार्ग जो लगाए गए प्रतिबंधों को संतुष्ट करता है), जिसकी लागत न्यूनतम है।

एल्गोरिथ्म में दो चरण होते हैं:

पहला चरण

लागत मैट्रिक्स लाना और मार्ग आर की लागत के निचले अनुमान की गणना करना।

1. प्रत्येक पंक्ति में सबसे छोटे तत्व की गणना करें (पंक्ति के लिए स्थिर रखें)
2. हम प्रत्येक पंक्ति से घटती निरंतरता को घटाकर नई लागत मैट्रिक्स में पास होते हैं
3. प्रत्येक स्तंभ में सबसे छोटे तत्व की गणना करें (स्तंभ के लिए स्थिर होना)
4. हम प्रत्येक कॉलम से इसकी कमी स्थिर से घटाकर नई लागत मैट्रिक्स पर आगे बढ़ते हैं।
नतीजतन, हमारे पास एक लागत मैट्रिक्स है जिसमें प्रत्येक पंक्ति और स्तंभ में कम से कम एक शून्य तत्व होता है।
5. कॉलम और पंक्तियों के लिए कास्टिंग स्थिरांक के योग के रूप में आर की गणना करें।

दूसरा (मुख्य) चरण

1. कम लागत मैट्रिक्स के प्रत्येक शून्य तत्व के लिए गैर-उपयोग के लिए दंड की गणना।
गैर-उपयोग के लिए जुर्माना का मतलब है कि मैट्रिक्स में सूचकांक (एच, के) के साथ एक तत्व का अर्थ है कि यह बढ़त हमारे मार्ग में शामिल नहीं है, और इसलिए "इस उपयोग नहीं करने" की न्यूनतम लागत पंक्ति एच और कॉलम के में न्यूनतम तत्वों का योग है।

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

अधिकतम क्यों है? क्योंकि इसका मतलब है कि इस किनारे के मार्ग से बहिष्करण से इष्टतम मार्ग की लागत में अधिकतम वृद्धि होगी, जिसे हम अभी देख रहे हैं।

2. अब हम अपने सेट S (0) को दो में विभाजित करते हैं - Sw (एज h, k) और Sw / o (एज h, k युक्त नहीं)
3. इनमें से प्रत्येक सेट में शामिल मार्गों के लिए लागत अनुमानों की गणना।
a) सेट Sw / o के लिए, सब कुछ सरल है: चूंकि हम बढ़त (h, k) को नहीं लेते हैं, तो इसके लिए लागत अनुमान सेट S (0) के दंड के मूल्य अनुमान के बराबर है। किनारे (h, k) का उपयोग नहीं करने के लिए जुर्माना
b) जब सेट स्व के लिए लागतों की गणना करते हैं, तो हम इस बात को ध्यान में रखते हैं कि चूंकि बढ़त (h, k) मार्ग में प्रवेश करती है, तो किनारे (k, h) मार्ग में प्रवेश नहीं कर सकते, इसलिए हम c (k, h) = लागत मैट्रिक्स में लिखते हैं अनंत, और चूँकि हम "पहले ही छोड़ चुके हैं" बिंदु h और "पहले ही आ चुके हैं" बिंदु k से, कोई भी बढ़त h से नहीं निकल रही है, और k में आने वाले किसी भी किनारे का उपयोग नहीं किया जा सकता है, इसलिए हम इससे हटा देते हैं लागत मेट्रिसेस पंक्ति h और कॉलम k। उसके बाद, हम मैट्रिक्स को प्रस्तुत करते हैं, और फिर स्वा के लिए लागत अनुमान एस (0) और आर (एच, के) के लिए लागत अनुमानों के योग के बराबर है, जहां आर (एच, के) संशोधित लागत मैट्रिक्स के लिए कमी स्थिरांक का योग है।
4. सेट्स से Sw और Sw / o, जिसकी उच्चतम रेटिंग है, का चयन किया जाता है।

इसलिए हम तब तक जारी रखते हैं जब तक कि खर्चों के मैट्रिक्स में कोई गैर-क्रॉस आउट पंक्ति और एक गैर-क्रॉस आउट कॉलम न हो।

अब परिणाम।
यदि प्रत्येक चरण में आप केवल दो सेट (स्व और स्वो) से चुनते हैं, तो एल्गोरिथ्म काफी समझदार समय काम करता है, हालांकि, सटीकता सिर्फ भयानक है (यह आइटम 1 से बहुत लालच खो देता है)

यदि हर कदम पर आप इस कदम से प्राप्त किए गए सबसे अच्छे सेट को चुनते हैं और पहले इस्तेमाल नहीं किया जाता है,
फिर छोटे रेखांकन (लगभग 40-50) लंबों के लिए, अच्छी सटीकता प्राप्त होती है, लेकिन 500 कोने के लिए इंतजार करना संभव नहीं था।

इसलिए, निम्नलिखित विचार मन में आता है:

4. उत्तराधिकार के साथ शाखाओं और सीमाओं की विधि

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

हेयुरिस्टिक कॉस्ट = मार्क का पहला और सरल संस्करण k * डेप्थ है। k हम पसलियों के औसत वजन के आधार पर चयन करते हैं ताकि, फिर भी, गहराई निर्णायक भूमिका नहीं निभाए। हम यह भी कहते हैं, उदाहरण के लिए, कि गहराई कम से कम बी है, अर्थात। यदि हमारा शीर्ष जड़ से q दूरी पर है, और q <b, तो गहराई = b, अन्यथा गहराई = q है। बी के रूप में, हम एक ऐसी संख्या चुनते हैं, जो शाखाओं और सीमाओं का एक ईमानदार एल्गोरिदम (बिना आंकड़ो के) पर्याप्त समय में इतनी गहराई तक पहुँच जाता है। मेरे मामले में यह b = 30 था।

हम शुरू करते हैं, हम इंतजार करते हैं।

काम की रात के लिए, हमें एक जवाब मिलता है कि लालची एल्गोरिथ्म ~ 2% से अधिक है।
कुछ, बहुत कम, यह देखते हुए कि लालची एल्गोरिथ्म कुछ सेकंड के लिए काम करता है और 5 मिनट में लिखा जाता है।

और अब विजेता:

स्थानीय सीमा और शाखा विधि के साथ एक लालची एल्गोरिथ्म

एल्गोरिथ्म इस प्रकार है:

1. लालची एल्गोरिथ्म चलाएँ, कुछ मार्ग प्राप्त करें।
2. मार्ग को कई भागों में विभाजित करें।
3. प्रत्येक भाग में हम एक काल्पनिक किनारा बनाते हैं - मार्ग के अंतिम शीर्ष से पहले तक, जिसे छूने से मना किया जाता है
4. इन भागों में से प्रत्येक पर, शाखा और बाउंड विधि को चलाने के लिए, बिना सांख्यिकी के।
5. शाखा और बाध्य विधि द्वारा अनुकूलित भागों को मिलाएं, डमी किनारों को खोलना और पहले एन भाग के साथ एन -1 भाग के अंतिम शीर्ष को जोड़ना।

यह समझना आसान है कि इस एल्गोरिथ्म के कई फायदे हैं।

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

परिणाम।
25 भागों पर परिचालन समय - 3 मिनट, हम लालची को हरा देते हैं ~ 7%
10 भाग - 4 घंटे, लाभ ~ 15%

विस्तार