पुनरावर्ती संपूर्ण खोज द्वारा यात्रा विक्रेता समस्या का समाधान

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

राय है कि विक्रेता समस्या को दो अन्य तरीकों से तैयार किया जा सकता है:
1. सबसे छोटे हैमिल्टन चक्र का पता लगाना आवश्यक है।
2. किसी दिए गए नोड पर शुरू होने वाले सबसे छोटे रास्ते का पता लगाना आवश्यक है।

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

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

अंतिम स्थिति वास्तव में साइकिल को प्रतिबंधित करती है, क्योंकि यदि हम एक वास्तविक विक्रेता की जगह पर खुद की कल्पना करते हैं, तो किनारों का चौराहा (इस तथ्य के बावजूद कि केवल नोड्स का पुन: उपयोग कार्य में स्पष्ट रूप से निषिद्ध है) वास्तव में सेल्समैन की उस जगह पर वापसी का मतलब होगा जहां वह पहले से ही था, जो इष्टतम (सबसे कम) की परिभाषा का विरोध करता है रास्ता।

डेस्कटॉप ट्रैवलिंग सेल्समैन समस्या का एक इष्टतम समाधान संभव है। हालाँकि, जैसे-जैसे नोड्स की संख्या बढ़ती है, थकावट भरी खोज पर बिताया जाने वाला समय तेजी से बढ़ता है। इस प्रकार, 2.67 गीगाहर्ट्ज़ क्वाड-कोर प्रोसेसर वाली मशीन पर, 10 मिलीसेकेंड में औसतन 10 नोड्स की गणना की जाती है, 15 मिनट में 20 नोड्स, और 60 नोड्स के लिए इष्टतम पथ की गणना करने में 6 ट्रिलियन से अधिक साल लगेंगे ...

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

उस थकाऊ खोज में सादृश्य विधि खराब है, इष्टतम समाधान विधि के रूप में, पूरी तरह से खारिज कर दिया गया है और पूरी तरह से किसी अन्य विधि द्वारा प्रतिस्थापित किया गया है। मेरा मानना ​​है कि संपूर्ण खोज के साथ इतनी लापरवाही से कार्य करना असंभव है, क्योंकि यह एकमात्र तरीका है जो समस्या का सही समाधान देने की गारंटी है।

हम ट्रैवलिंग सेल्समैन की समस्या को केवल विस्तृत खोज द्वारा हल करने की कोशिश करेंगे, इसे किसी और चीज से बदल देंगे जहां यह समय की बचत के कारणों के लिए वास्तव में आवश्यक है।

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

यह स्पष्ट है कि स्वीकार्य समय में संपूर्ण खोज द्वारा इसे हल करने के लिए यात्रा सेल्समैन की समस्या को सरल बनाने के लिए, केवल एक ही रास्ता है - नोड्स की संख्या को कम करने के लिए। और यह केवल एक ही तरीके से किया जा सकता है - नोड्स को समूहों में संयोजित करने के लिए - ओवर-नोड्स, ओवर-टास्क (उप-कार्य)।

यात्रा करने वाले सेल्समैन को पुनरावर्ती रूप से सेट करने के लिए, आइए हम इसे पुनरावर्ती रूप से देखने का प्रयास करें।
इस कार्य में मुख्य तत्व वह नोड है जिसमें एक किनारे से प्रवेश होता है और एक किनारे से बाहर निकलता है:


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


इस प्रकार, पुनरावर्ती एल्गोरिदम का एक सामान्य दृश्य उभरता है।
1. नोड्स को परिभाषित करें एन।
2. Tmax समस्या को हल करने के लिए अधिकतम स्वीकार्य समय निर्धारित करें।
3. इस मशीन पर एक बेंचमार्क का संचालन करें और टी (एन) विकल्पों की पूरी गणना के साथ नोड्स की संख्या पर समाधान समय की निर्भरता निर्धारित करें।
4. नोड N, Tmax और T के लिए निर्भरता की दी गई संख्या के आधार पर, निर्धारित करें कि N नोड के सेट को कितने समूहों (ओवर-नोड) में विभाजित किया जाना चाहिए। या नोड्स की इस संख्या को मैन्युअल रूप से सेट करें (यह वास्तव में हम क्या करेंगे)।
5. N समूहों के समूह को M समूहों में विभाजित करें।
6. M समूहों की खोज को पूरा करें और इन समूहों को जोड़ने के लिए सबसे छोटा रास्ता खोजें।
7. चरण 6 के बाद, हम प्रत्येक समूह के लिए इनपुट और आउटपुट जानते हैं, इसलिए हम प्रत्येक समूह के लिए ट्रैवलिंग सेल्समैन समस्या का पुनरावृत्ति करते हैं, अर्थात चरण 4 पर जाएं, जहां एन प्रत्येक समूह में नोड्स की संख्या के बराबर है।
8. पुनरावृत्ति से बाहर निकलने के बाद, हम इस मशीन और इस Tmax (या समूह में नोड्स की दी गई संख्या) के लिए एक उप-अपनाने वाला मार्ग प्राप्त करते हैं।

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

चरण 5 में, स्पष्ट रूप से यथासंभव एम को प्राथमिकता देना सबसे अच्छा है। जब M, N के पास जाता है, तो हमें एक तेजी से सटीक समाधान मिलता है। हम जितनी कम खोज से जाते हैं, हमारा निर्णय उतना ही सटीक होता है। आप सरलतम क्रूड धारणा से बनी तालिका से एम चुन सकते हैं कि पुनरावृत्ति के प्रत्येक चरण में हम समूह में समान संख्या में नोड्स के साथ उप-कार्य को समूहों में विभाजित करेंगे।



जैसा कि तालिका से देखा जा सकता है, यहां तक ​​कि एक समूह में 18 नोड्स के साथ, हम 8 तक की पुनरावृत्ति गहराई के साथ 10 बिलियन से अधिक नोड्स संसाधित कर सकते हैं।

यदि हम इस तरह से मार्ग को सुधारना चाहते हैं, तो हमारे पास निम्नलिखित विकल्प हैं:
- अधिक उत्पादक कार चुनें
- अनुमेय समय Tmax बढ़ाएँ
- समूहों की संख्या में वृद्धि
- पुनरावृत्ति के घोंसले में वृद्धि। अर्थात्, चरण 6 पर, कार्य को समूहों की एक बड़ी संख्या (एन के आधार पर) में विभाजित करें, लेकिन यह उन्हें खोजने के लिए इष्टतम नहीं है, लेकिन उप-रूपी है। उदाहरण के लिए, 500 समूहों में 1000 नोड्स से एक कार्य को तोड़ने के लिए, लेकिन संपूर्ण खोज (उन्हें बहुत लंबा समय लगता है) से कनेक्ट करने के लिए सबसे छोटा तरीका नहीं है, लेकिन समूहों को उप-समूहों में तोड़ने के लिए, उदाहरण के लिए, 250 समूह और उनके बीच एक उप-पथ की खोज करें। और इसी तरह, जब तक हम उस स्तर तक नहीं जाते जहां मशीन पूरी खोज कर सकती है।

समूहों में समूह कैसे बनाएं?
अमूर्त उपमाओं को आकर्षित नहीं करने के लिए और धूमिल उत्तराधिकारियों का उपयोग नहीं करने के लिए, हम समस्या में ही उत्तर खोजने का प्रयास करेंगे। यह पूरी तरह से स्पष्ट है कि कार्य में शुरू में हमारे पास एक समूह है जिसके लिए Bx और Ox दिए गए हैं।

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

यदि हमें कार्य को समूहों की एक मनमानी संख्या में विभाजित करने की आवश्यकता है, तो हम इस विभाजन को पुनरावर्ती करते हैं। सबसे पहले, हम पाते हैं कि मध्यवर्ती इनपुट / आउटपुट प्रारंभिक इनपुट और आउटपुट के संबंध में पारस्परिक रूप से दूर है। तब हम दूसरे इंटरमीडिएट इनपुट / आउटपुट को पारस्परिक रूप से पहले तीन से दूर करते हैं, और इसी तरह।

जाहिर है, एन के बराबर समूहों की संख्या के साथ, इन समूहों के मध्यवर्ती इनपुट / आउटपुट शुरुआती नोड्स के साथ मेल खाएंगे। इस प्रकार, हमने समूहों में सभी नोड्स का एकमात्र सही विभाजन पाया।

आप यहां ग्रुपिंग के साथ प्रयोग कर सकते हैं (ऑब्जेक्ट पास्कल के लिए स्रोत कोड शामिल हैं)।
एक सेल्समैन कार्य बनाने के लिए, आपको नोड्स की संख्या दर्ज करने और Enter दबाने की आवश्यकता है। या फ़ाइल से कार्य लोड करें।
स्लाइडर को स्थानांतरित करके आप समूहों में विभाजित होने के सिद्धांत का पालन कर सकते हैं। "लिंक ग्रुप्स" बटन एक्ज़िटिव सर्च द्वारा वर्तमान समूहों को इष्टतम मार्ग के साथ जोड़ता है। बटन "लिंक नोड्स" संपूर्ण मार्ग के साथ सभी नोड्स को संपूर्ण खोज से जोड़ता है। इसलिए, आपको इन बटनों को नोड्स या समूहों की एक बड़ी (> 18) संख्या के साथ नहीं दबाना चाहिए।

यहां आप ऊपर वर्णित एल्गोरिदम का उपयोग करके यात्रा विक्रेता समस्या को हल करने के लिए कार्यक्रम और स्रोत कोड डाउनलोड कर सकते हैं।
शासी निकाय:
"लोड" बटन एक्सटेंशन * .txt वाली फ़ाइल से किसी कार्य को लोड करता है
Txt फ़ाइल प्रारूप निम्नानुसार है: प्रत्येक पंक्ति में, 1 स्थान इंगित करता है कि x और y कार्य में प्रत्येक नोड के लिए निर्देशांक है। पहली पंक्ति इनपुट नोड के निर्देशांक को दिखाती है। अंतिम पंक्ति में आउटपुट नोड के निर्देशांक होते हैं। यादृच्छिक क्रम में उनके बीच शेष नोड्स। निर्देशांक 6 दशमलव स्थानों की सटीकता के साथ 0-1 की सीमा में हैं। पूर्णांक और भिन्नात्मक भागों का विभाजक अल्पविराम होता है।

उत्पन्न बटन नोड क्षेत्र में संकेतित नोड्स की संख्या के साथ एक यादृच्छिक यात्रा सेल्समैन कार्य उत्पन्न करता है।

"सहेजें" बटन इस कार्य के नोड्स के निर्देशांक को बचाता है।

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

इस कार्यक्रम में, समूहों में टूटना इष्टतम नहीं है, इसलिए चौराहे होते हैं। लेकिन यह कमी मौलिक रूप से हटाने योग्य है।

एल्गोरिथ्म में सुधार करने के लिए, नोड पैरामीटर को दो स्वतंत्र मापदंडों में विभाजित किया जाना चाहिए:
Nmax - नोड्स की अधिकतम संख्या जिसके लिए समूहों में विभाजित किए बिना पूर्ण गणना की जाती है।
Gmax - विभाजन नोड्स के लिए समूहों की संख्या, जिनमें से संख्या Nmax से अधिक थी। और यह संख्या अलग-अलग तरीकों से सेट की जा सकती है। आप एक निरंतर द्वारा नोड की संख्या को विभाजित कर सकते हैं, आप नोड की वर्तमान संख्या से 1 घटा सकते हैं, आप "गोल्डन सेक्शन" के अनुपात में नोड की संख्या को विभाजित कर सकते हैं, आप एक निश्चित प्रतिशत ले सकते हैं। इस संबंध में, मैं अनुसंधान कर रहा हूं।
इस कार्यक्रम में, सरलता और स्पष्टता के लिए, Gmax = Nmax = समूह।

कार्यक्रम 5 सेकंड से कम समय में समूह = 13 पर एक हजार नोड्स की गणना करता है। संपूर्ण खोज के लिए, परिणाम बहुत अच्छा है।