ट्रैवलिंग सेल्समैन समस्या की व्याख्या
किसी सेल्समैन को शहरों की एक सूची दें और उससे वह सबसे छोटी यात्रा पूछें जो हर शहर में एक बार जाए और घर लौट आए। प्रस्तावित रास्ते की जाँच कोई भी कर सकता है, और खराब रास्ते को कोई भी आँख से देखकर सुधार सकता है, फिर भी कोई ऐसी तेज़ विधि नहीं जानता जो हमेशा सबसे अच्छा रास्ता खोज ले। ट्रैवलिंग सेल्समैन समस्या कठिन समस्या का मानक उदाहरण बन गई है, और इसे सुलझाने के लिए बनाई गई विधियाँ आज डिलीवरी की योजना बनाती हैं, सर्किट बोर्ड में छेद करती हैं और जीनोम जोड़ती हैं।
समस्या
एक टूर हर शहर में ठीक एक बार जाता है और वहीं खत्म होता है जहाँ से शुरू हुआ था; उसकी लंबाई रास्ते की दूरियों का योग है। काम सबसे छोटा टूर खोजना है। यहाँ वाले संस्करण में दूरियाँ नक्शे पर सीधी रेखाएँ हैं, इसलिए A से C जाना B से होकर जाने से कभी लंबा नहीं होता: यह मीट्रिक ट्रैवलिंग सेल्समैन समस्या है। इस पहेली पर गणितज्ञ कार्ल मेंगर ने लगभग 1930 में चर्चा की थी, और यह नाम अगले दशकों में आम हुआ, जब RAND Corporation के गणितज्ञों ने इस पर काम शुरू किया।
रास्तों का विस्फोट
शुरुआती शहर तय कर लें। अगले शहर के लिए n − 1 विकल्प हैं, उसके बाद वाले के लिए n − 2, और इसी तरह आगे, और हर टूर दो दिशाओं में चलाया जा सकता है, इसलिए (n − 1)! / 2 टूर होते हैं। 10 शहरों के लिए यह 181,440 है, जो कंप्यूटर के लिए आसान है। 20 के लिए यह लगभग 6 × 10¹⁶ है, और 70 के लिए यह प्रेक्षणीय ब्रह्मांड के परमाणुओं की संख्या से भी ज़्यादा है। तेज़ कंप्यूटर ज़्यादा मदद नहीं करते: हर अतिरिक्त शहर काम को लगभग n गुना कर देता है।
NP-हार्ड
1972 में रिचर्ड कार्प ने दिखाया कि यह सवाल कि किसी ग्राफ में हर शीर्ष से होकर जाने वाला पूरा चक्कर, यानी हैमिल्टनी चक्र, है या नहीं, NP-पूर्ण समस्याओं के एक ऐसे परिवार में आता है जो सब बराबर कठिन हैं। ट्रैवलिंग सेल्समैन समस्या में यह सवाल शामिल है, इसलिए यह NP-हार्ड है। इसके लिए कोई तेज़ विधि शेड्यूलिंग, लॉजिस्टिक्स और क्रिप्टोग्राफी की हज़ारों दूसरी समस्याओं के लिए भी तेज़ विधियाँ दे देगी। ऐसी विधि मौजूद है या नहीं, यही P बनाम NP प्रश्न है, जो मिलेनियम प्राइज़ समस्याओं में से एक है।
एक सटीक विधि: हेल्ड–कार्प
1962 में माइकल हेल्ड और रिचर्ड कार्प ने, और स्वतंत्र रूप से रिचर्ड बेलमैन ने, डायनेमिक प्रोग्रामिंग का उपयोग किया। शहरों के हर समुच्चय S और S के हर शहर j के लिए, वह सबसे छोटा रास्ता निकालें जो घर वाले शहर से शुरू हो, ठीक S के शहरों में जाए और j पर खत्म हो। हर मान j के बिना S के मानों से निकलता है, इसलिए तालिका छोटे समुच्चयों से बड़े समुच्चयों की ओर भरी जाती है, और सबसे छोटा टूर अंत में निकल आता है। इसे n! के बजाय लगभग n² · 2ⁿ चरण चाहिए, जो 30 शहरों के लिए मिनटों और ब्रह्मांड की आयु का अंतर है, फिर भी यह घातांकीय रूप से बढ़ता है।
तेज़ निर्माण नियम
निकटतम पड़ोसी हमेशा सबसे पास के उस शहर की ओर जाता है जहाँ अभी तक नहीं गया। यह सरल और तेज़ है, पर यह कुछ शहरों को अलग-थलग छोड़ देता है जिन्हें अंत में लंबे चक्कर लगाकर समेटना पड़ता है, इसलिए इसके टूर आमतौर पर सबसे अच्छे से लगभग 25% लंबे होते हैं। इसके बजाय सम्मिलन विधियाँ एक बंद लूप बनाए रखती हैं और बचे हुए शहरों को एक-एक करके वहाँ जोड़ती हैं जहाँ उनकी लागत सबसे कम हो। 1976 में निकोस क्रिस्टोफ़ाइड्स ने एक ऐसी निर्माण विधि खोजी जो किसी भी मीट्रिक नक्शे पर इष्टतम के अधिकतम 1.5 गुना की गारंटी देती है, एक ऐसी सीमा जो चालीस से अधिक वर्षों तक लगभग अटूट रही।
टूर में सुधार: 2-opt
लोकल सर्च किसी भी टूर से शुरू होकर बार-बार छोटे बदलाव करता है जो उसे छोटा करते हैं। क्लासिक चाल, 2-opt, दो किनारे हटाती है और दोनों टुकड़ों को दूसरे तरीके से फिर जोड़ती है, जिससे उनके बीच का हिस्सा उलट जाता है। जब भी दो किनारे एक-दूसरे को काटते हैं, यह चाल उन्हें सुलझा देती है और लंबाई बचाती है, इसलिए जिस टूर को 2-opt और नहीं सुधार सकता, वह कभी खुद को नहीं काटता। यादृच्छिक नक्शों पर 2-opt के टूर आमतौर पर इष्टतम से लगभग 5% ऊपर होते हैं। तीन किनारे बदलने वाली ज़्यादा ताकतवर चालें, या 1973 की लिन और कर्निघन की परिवर्ती-गहराई विधि, और भी करीब पहुँचती हैं।
सिम्युलेटेड एनीलिंग
लोकल सर्च ऐसे टूर में अटक सकता है जहाँ हर एक चाल उसे और खराब करती है, भले ही कहीं ज़्यादा अच्छा टूर मौजूद हो। सिम्युलेटेड एनीलिंग, जिसे 1983 में स्कॉट किर्कपैट्रिक, डेनियल गेलैट और मारियो वेक्की ने इस समस्या पर लागू किया, धातुकर्म से विचार उधार लेता है: यह बदतर चाल को एक ऐसी प्रायिकता से स्वीकार करता है जो तापमान पर निर्भर करती है, जो शुरू में ऊँचा होता है और धीरे-धीरे घटाया जाता है। शुरुआत में टूर खुलकर भटकता है; अंत में केवल सुधार स्वीकार होते हैं। पर्याप्त धीमी ठंडक के साथ यह भरोसेमंद रूप से बहुत अच्छे टूर खोज लेता है।
खुद आज़माएँ
अधिकतम 200 शहरों को यादृच्छिक रूप से, वृत्त पर, समूहों में, ग्रिड पर या जहाँ भी आप क्लिक करें वहाँ रखने के लिए ट्रैवलिंग सेल्समैन डेमो खोलें। देखें कि निकटतम पड़ोसी अपने आखिरी शहरों को कैसे अलग-थलग छोड़ता है, देखें कि 2-opt हर क्रॉसिंग को कैसे सुलझाता है, ठंडा होते हुए सिम्युलेटेड एनीलिंग के तापमान पर नज़र रखें, और हेल्ड–कार्प को अधिकतम 12 शहरों के लिए सबसे छोटा टूर सिद्ध करने दें। सबकी तुलना करें हर विधि को एक ही नक्शे पर चलाता है और दिखाता है कि हर टूर अब तक मिले सबसे छोटे टूर से कितना लंबा है।
अक्सर पूछे जाने वाले प्रश्न
ट्रैवलिंग सेल्समैन समस्या का उपयोग कहाँ होता है?
जहाँ भी किसी चीज़ को कई जगहों पर कुशल क्रम में जाना हो: डिलीवरी और कलेक्शन के रास्ते, सर्किट बोर्ड पर ड्रिल या लेज़र का रास्ता, वह क्रम जिसमें कोई दूरबीन तारों का प्रेक्षण करती है, गोदाम में सामान उठाने का क्रम, और अलग तरह की दूरियों के साथ, DNA अनुक्रम जोड़ते समय टुकड़ों का क्रम।
अब तक सटीक रूप से हल की गई सबसे बड़ी समस्या कौन-सी है?
1954 में जॉर्ज डैंट्ज़िग, रे फुलकर्सन और सेल्मर जॉनसन ने संयुक्त राज्य अमेरिका के 49 शहरों से होकर जाने वाला सबसे छोटा टूर सिद्ध किया। 2006 में डेविड ऐपलगेट, रॉबर्ट बिक्सबी, वाशेक ख्वाटल और विलियम कुक के Concorde सॉल्वर ने वर्षों के कंप्यूटर समय के बाद एक चिप डिज़ाइन के 85,900 बिंदुओं से होकर जाने वाला इष्टतम टूर सिद्ध किया।
क्या सबसे छोटा टूर हमेशा क्रॉसिंग से मुक्त होता है?
हाँ, सीधी रेखा वाली दूरियों वाले समतल नक्शे पर। अगर दो किनारे एक-दूसरे को काटते, तो उन्हें उनसे बने चतुर्भुज की दो भुजाओं से बदलने पर टूर छोटा हो जाता, इसलिए क्रॉसिंग वाला टूर सबसे छोटा नहीं हो सकता।
क्या ह्यूरिस्टिक हर बार एक ही टूर देते हैं?
यहाँ जिस रूप में उपयोग किए गए हैं, उसमें निकटतम पड़ोसी, सबसे सस्ता सम्मिलन और 2-opt नियतात्मक हैं: उन्हीं शहरों पर वे वही टूर देते हैं। सिम्युलेटेड एनीलिंग एक यादृच्छिक टूर से शुरू होता है और यादृच्छिक चालें चलता है, इसलिए दो बार चलाने पर अलग-अलग टूर मिल सकते हैं, जिनकी लंबाई आमतौर पर लगभग बराबर होती है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
ट्रैवलिंग सेल्समैन डेमो खोलें