एक पुनरावर्ती लालची एल्गोरिथ्म के साथ एक विमान पर यात्रा विक्रेता समस्या का समाधान

पिछले प्रकाशन में , हमने पुनरावर्ती संपूर्ण खोज के साथ एक विमान पर यात्रा सेल्समैन समस्या को हल करने के लिए एक एल्गोरिथ्म पर विचार किया। परिणाम उत्सुक था, लेकिन अंतिम मार्ग में स्पष्ट गैर-इष्टतम अनुभाग थे। प्रस्तावित लेख एक बेहतर एल्गोरिथ्म पर चर्चा करता है, जिसे मैंने "पुनरावर्ती लालची एल्गोरिथ्म" कहा है। मैं तुरंत स्वीकार करता हूं कि पुनरावर्ती संपूर्ण खोज की तुलना में अंतिम मार्ग, औसतन, 8% तक बेहतर होता है।

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

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

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

ऑब्जेक्ट पास्कल के लिए कार्यक्रम और स्रोत कोड यहां डाउनलोड किए जा सकते हैं ।

एल्गोरिथ्म के लाभ:
1. सादगी।
2. गति। क्वाड-कोर 2.67 गीगाहर्ट्ज प्रोसेसर वाली मशीन पर, 3 सेकंड में 1000 नोड्स की गणना (औसतन) की जाती है
27 सेकंड में 2000 नॉट
87 सेकंड में 3000 समुद्री मील
4000 नॉट - 207 सेकंड में
समय में वृद्धि घातीय है, लेकिन व्यावहारिक कार्यों के लिए यह वृद्धि काफी धीमी है।
3. पहले से प्रस्तावित एल्गोरिथ्म की तुलना में , परिणाम लगभग 8% से सबसे अच्छा है।
4. रैम का न्यूनतम उपयोग।
5. किसी भी सेटिंग्स का अभाव।
6. चौराहों की न्यूनतम संख्या बिना किसी जाँच के।

नुकसान , हमेशा की तरह, फायदे के फ्लिप पक्ष हैं:
1. सेटिंग्स की कमी, यदि आवश्यक हो, तो इसकी गणना करने के लिए समय को कम करके मार्ग की गुणवत्ता को नीचा दिखाने की अनुमति नहीं देता है।
2. अंतर बहुत दुर्लभ हैं, लेकिन फिर भी होते हैं।
3. घातीय वृद्धि अभी भी स्पष्ट नहीं है कि कैसे धीमा किया जाए। यह संभव है कि सभी किनारों के माध्यम से पुनरावृति हो, लेकिन केवल इस नोड के सबसे करीब।