संक्षिप्त बुलेटेड सूची में यात्रा विक्रेता समस्या का इतिहास क्या है?ट्रैवलिंग सेल्समैन समस्या की उत्पत्ति स्पष्ट नहीं है। 1832 से यात्रा करने वाले सेल्समेन के लिए एक हैंडबुक में समस्या का उल्लेख किया गया है और इसमें जर्मनी और स्विटज़रलैंड के माध्यम से उदाहरण के दौरे शामिल हैं, लेकिन इसमें कोई गणितीय उपचार नहीं है। [2]


विलियम रोवन हैमिल्टन
TSP को 19वीं शताब्दी में आयरिश गणितज्ञ विलियम रोवन हैमिल्टन और ब्रिटिश गणितज्ञ थॉमस किर्कमैन द्वारा गणितीय रूप से तैयार किया गया था। हैमिल्टन का आइकोसियन गेम हैमिल्टनियन चक्र की खोज पर आधारित एक मनोरंजक पहेली थी। [3] ऐसा प्रतीत होता है कि TSP के सामान्य रूप का पहली बार 1930 के दशक के दौरान विएना और हार्वर्ड में गणितज्ञों द्वारा अध्ययन किया गया था, विशेष रूप से कार्ल मेन्जर द्वारा, जो समस्या को परिभाषित करते हैं, स्पष्ट पशु-बल एल्गोरिथ्म पर विचार करते हैं, और निकटतम की गैर-इष्टतमता का निरीक्षण करते हैं। पड़ोसी अनुमानी:

हम संदेशवाहक समस्या से निरूपित करते हैं (चूंकि व्यवहार में यह प्रश्न प्रत्येक डाकिया द्वारा हल किया जाना चाहिए, वैसे भी कई यात्रियों द्वारा भी) कार्य को खोजने के लिए, बहुत से बिंदुओं के लिए जिनकी जोड़ीदार दूरी ज्ञात है, बिंदुओं को जोड़ने वाला सबसे छोटा मार्ग। बेशक, यह समस्या बहुत से परीक्षणों द्वारा हल करने योग्य है। नियम जो दिए गए बिंदुओं के क्रमपरिवर्तन की संख्या के नीचे परीक्षणों की संख्या को आगे बढ़ाएंगे, ज्ञात नहीं हैं। यह नियम कि किसी को पहले प्रारंभिक बिंदु से निकटतम बिंदु तक जाना चाहिए, फिर इसके निकटतम बिंदु तक जाना चाहिए, आदि, सामान्य तौर पर सबसे छोटा रास्ता नहीं देता है। [4]

इसे पहली बार 1930 के दशक में मेरिल एम. फ्लड द्वारा गणितीय रूप से माना गया था, जो एक स्कूल बस रूटिंग समस्या को हल करना चाह रहे थे। [5] प्रिंसटन यूनिवर्सिटी में हस्लर व्हिटनी ने इस समस्या में रुचि पैदा की, जिसे उन्होंने "48 राज्यों की समस्या" कहा। "ट्रैवलिंग सेल्समैन प्रॉब्लम" वाक्यांश का उपयोग करने वाला सबसे पहला प्रकाशन जूलिया रॉबिन्सन द्वारा 1949 की रैंड कॉर्पोरेशन रिपोर्ट थी, "ऑन द हैमिल्टनियन गेम (ए ट्रैवलिंग सेल्समैन प्रॉब्लम)।" [6] [7]

1950 और 1960 के दशक में, यह समस्या यूरोप और संयुक्त राज्य अमेरिका में वैज्ञानिक हलकों में तेजी से लोकप्रिय हुई जब सांता मोनिका में रैंड कॉर्पोरेशन ने समस्या को हल करने के लिए कदमों के लिए पुरस्कार की पेशकश की। [5] रैंड कॉर्पोरेशन से जॉर्ज डेंटजिग, डेलबर्ट रे फुलकर्सन और सेल्मर एम. जॉनसन द्वारा उल्लेखनीय योगदान दिया गया, जिन्होंने समस्या को एक पूर्णांक रैखिक कार्यक्रम के रूप में व्यक्त किया और इसके समाधान के लिए कटिंग प्लेन विधि विकसित की। उन्होंने लिखा कि इस विषय पर सेमिनल पेपर क्या माना जाता है जिसमें इन नए तरीकों से उन्होंने एक दौरे का निर्माण करके 49 शहरों के साथ इष्टतमता के उदाहरण को हल किया और यह साबित किया कि कोई अन्य दौरा छोटा नहीं हो सकता। हालांकि, डेंटजिग, फुलकर्सन और जॉनसन ने अनुमान लगाया कि निकट इष्टतम समाधान दिए जाने पर हम कुछ अतिरिक्त असमानताओं (कटौती) को जोड़कर इष्टतमता खोजने या इष्टतमता साबित करने में सक्षम हो सकते हैं। उन्होंने स्ट्रिंग मॉडल का उपयोग करके अपनी शुरुआती 49 शहर की समस्या को हल करने के लिए इस विचार का उपयोग किया। उन्होंने पाया कि उन्हें अपनी 49 शहर की समस्या के समाधान के लिए केवल 26 कटौती की आवश्यकता थी। हालांकि इस पेपर ने टीएसपी समस्याओं के लिए एल्गोरिथम दृष्टिकोण नहीं दिया, लेकिन इसके भीतर मौजूद विचार टीएसपी के लिए सटीक समाधान विधियों को बाद में बनाने के लिए अनिवार्य थे, हालांकि इन कटौती को बनाने में एल्गोरिथम दृष्टिकोण खोजने में 15 साल लगेंगे। [5] कटिंग प्लेन विधियों के साथ-साथ, डेंटजिग, फुलकर्सन और जॉनसन ने शायद पहली बार ब्रांच और बाउंड एल्गोरिदम का इस्तेमाल किया। [5]

1959 में, जिलियन बियर्डवुड, जे.एच. हाल्टन और जॉन हैमरस्ले ने कैम्ब्रिज फिलोसोफिकल सोसाइटी के जर्नल में "द शॉर्टेस्ट पाथ थ्रू मेनी पॉइंट्स" शीर्षक से एक लेख प्रकाशित किया। [8] बियर्डवुड-हॉल्टन-हैमरस्ले प्रमेय ट्रैवलिंग सेल्समैन समस्या का एक व्यावहारिक समाधान प्रदान करता है। लेखकों ने एक सेल्समैन के लिए सबसे छोटे मार्ग की लंबाई निर्धारित करने के लिए एक स्पर्शोन्मुख सूत्र निकाला, जो घर या कार्यालय से शुरू होता है और शुरुआत में लौटने से पहले निश्चित स्थानों पर जाता है।

बाद के दशकों में, गणित, कंप्यूटर विज्ञान, रसायन विज्ञान, भौतिकी और अन्य विज्ञानों के कई शोधकर्ताओं द्वारा समस्या का अध्ययन किया गया। 1960 के दशक में, हालांकि, एक नया दृष्टिकोण बनाया गया था, कि इष्टतम समाधान खोजने के बजाय एक ऐसा समाधान तैयार किया जाएगा, जिसकी लंबाई इष्टतम लंबाई के गुणक से सिद्ध हो, और ऐसा करने से समस्या के लिए निचली सीमा बन जाएगी; इन निचली सीमाओं का उपयोग शाखा और बाध्य दृष्टिकोणों के साथ किया जाएगा। ऐसा करने का एक तरीका यह था कि ग्राफ़ का एक न्यूनतम फैले हुए पेड़ का निर्माण किया जाए और फिर इसके सभी किनारों को दोगुना किया जाए, जो इस सीमा को उत्पन्न करता है कि एक इष्टतम दौरे की लंबाई एक न्यूनतम फैले हुए पेड़ के वजन का अधिकतम दुगुना है। [5]

1976 में, क्रिस्टोफ़ाइड्स और सेरड्यूकोव ने एक-दूसरे से स्वतंत्र रूप से इस दिशा में एक बड़ी प्रगति की: [9] क्रिस्टोफ़ाइड्स-सर्ड्यूकोव एल्गोरिथम एक समाधान देता है, जो सबसे खराब स्थिति में, इष्टतम समाधान से अधिकतम 1.5 गुना अधिक लंबा होता है। जैसा कि एल्गोरिथ्म सरल और त्वरित था, बहुतों को उम्मीद थी कि यह निकट इष्टतम समाधान पद्धति का रास्ता देगा। हालांकि, सुधार की यह उम्मीद तुरंत पूरी नहीं हुई, और क्रिस्टोफाइड्स-सेरड्यूकोव 2011 तक सबसे खराब स्थिति वाला तरीका बना रहा, जब "ग्राफिकल" टीएसपी के सबसेट के लिए एक (बहुत) थोड़ा बेहतर सन्निकटन एल्गोरिथम विकसित किया गया था। [10] ] 2020 में इस छोटे से सुधार को पूर्ण (मीट्रिक) टीएसपी तक बढ़ा दिया गया था। [11] [12]

रिचर्ड एम. कार्प ने 1972 में दिखाया कि हैमिल्टन चक्र की समस्या एनपी-पूर्ण थी, जिसका तात्पर्य टीएसपी की एनपी-कठोरता से है। इसने इष्टतम पर्यटन खोजने की स्पष्ट कम्प्यूटेशनल कठिनाई के लिए एक गणितीय व्याख्या प्रदान की।

1970 और 1980 के दशक के अंत में महान प्रगति हुई, जब ग्रोत्शेल, पैडबर्ग, रिनाल्डी और अन्य ने 2,392 शहरों तक के उदाहरणों को सटीक रूप से हल करने में कामयाबी हासिल की, जिसमें कटिंग प्लेन और ब्रांच और बाउंड का उपयोग किया गया था।

1990 के दशक में, Applegate, Bixby, Chvátal, और Cook ने कॉनकॉर्ड प्रोग्राम विकसित किया जिसका उपयोग हाल के कई रिकॉर्ड समाधानों में किया गया है। गेरहार्ड रेनेल्ट ने 1991 में TSPLIB को प्रकाशित किया, जो अलग-अलग कठिनाई के बेंचमार्क उदाहरणों का एक संग्रह है, जिसका उपयोग कई शोध समूहों द्वारा परिणामों की तुलना करने के लिए किया गया है। 2006 में, कुक और अन्य ने एक माइक्रोचिप लेआउट समस्या द्वारा दिए गए 85,900-शहर के उदाहरण के माध्यम से एक इष्टतम दौरे की गणना की, जो वर्तमान में सबसे बड़ी हल की गई TSPLIB उदाहरण है। लाखों शहरों वाले कई अन्य उदाहरणों के लिए, ऐसे समाधान खोजे जा सकते हैं जो इष्टतम दौरे के 2-3% के भीतर होने की गारंटी है। [13]
्या की सुलझाई के लिए बेहतरीन तरीके मौजू