- टूर
- सबसे छोटा मिला
- शुरुआत
| विधि | लंबाई | सबसे छोटे से अधिक | चरण |
|---|---|---|---|
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - | |
| - | - | - |
ट्रैवलिंग सेल्समैन समस्या
एक सेल्समैन को हर शहर में एक बार जाकर घर लौटना है। किस क्रम से यात्रा सबसे छोटी होगी? सवाल पूछना आसान है, पर जैसे-जैसे शहरों की संख्या बढ़ती है, हर क्रम आज़माकर इसका जवाब देना नामुमकिन हो जाता है: 30 शहरों में ही लगभग 4.4 × 10³⁰ पूरे चक्कर संभव हैं। नक्शे पर शहर बिखेरें या क्लिक करके अपने शहर रखें, फिर देखें कि तेज़ अंगूठा-नियम, चतुर सुधार और एक सटीक विधि चरण-दर-चरण अपने टूर कैसे बनाते हैं, और देखें कि तेज़ विधियाँ कितने करीब पहुँचती हैं। चुनें कि शहर कैसे फैले हों और कितने हों, एक विधि चुनें और हल करें दबाएँ ताकि आप देख सकें कि वह चरण-दर-चरण एक पूरा चक्कर कैसे बनाती है, या एक-एक चाल आगे बढ़ने के लिए एक चरण दबाएँ। शहर जोड़ने के लिए नक्शे पर क्लिक करें, या किसी शहर को हटाने के लिए उस पर क्लिक करें। सबकी तुलना करें हर विधि को उन्हीं शहरों पर चलाता है और दिखाता है कि हर विधि अब तक मिले सबसे छोटे टूर से कितनी दूर है। लाल शहर वह जगह है जहाँ से यात्रा शुरू होती है।
यह कैसे काम करता है
- एक लेआउट और शहरों की संख्या चुनें, या अपने शहर रखने के लिए नक्शे पर क्लिक करें और किसी शहर को हटाने के लिए उस पर क्लिक करें।
- एक विधि चुनें और उसे चरण-दर-चरण देखने के लिए हल करें दबाएँ, या एक-एक चाल आगे बढ़ने के लिए एक चरण दबाएँ।
- हर विधि को उन्हीं शहरों पर चलाने के लिए सबकी तुलना करें दबाएँ और पढ़ें कि हर टूर अब तक मिले सबसे छोटे टूर से कितना लंबा है।
यह कठिन क्यों है
n शहरों के लिए (n − 1)! / 2 अलग-अलग पूरे चक्कर होते हैं, क्योंकि इससे फ़र्क नहीं पड़ता कि आप कहाँ से शुरू करते हैं या किस दिशा में घूमते हैं। यह 5 शहरों के लिए 12, 10 के लिए 181,440 और 20 के लिए लगभग 6 × 10¹⁶ है। ऐसी कोई विधि ज्ञात नहीं है जो हर नक्शे के लिए सबसे छोटा चक्कर ऐसे समय में खोज ले जो केवल n की किसी घात की तरह बढ़े; यह समस्या NP-हार्ड है। इस ऐप की सबसे अच्छी सटीक विधि, 1962 की हेल्ड–कार्प डायनेमिक प्रोग्रामिंग, को भी लगभग n² · 2ⁿ चरण चाहिए, इसलिए यहाँ इसे 12 शहरों तक सीमित रखा गया है।
तेज़ी से अच्छे टूर
व्यवहार में, लगभग सबसे छोटे टूर जल्दी मिल जाते हैं। निकटतम पड़ोसी हमेशा सबसे पास के बिना देखे शहर की ओर जाता है और आमतौर पर सबसे अच्छे टूर से लगभग 25% लंबे टूर पर खत्म होता है। सबसे सस्ता सम्मिलन एक लूप को बढ़ाता है और वह शहर जोड़ता है जो उसे सबसे कम लंबा करे। 2-opt कोई भी टूर लेकर बार-बार दो किनारों की जगह दो छोटे किनारे रखता है, जिससे हर क्रॉसिंग हट जाती है और आमतौर पर अंतर लगभग 5% के भीतर रह जाता है। सिम्युलेटेड एनीलिंग यादृच्छिक 2-opt चालें चलता है और जब तक वह अभी “गर्म” है, कुछ ऐसी चालें भी स्वीकार करता है जो टूर को लंबा करती हैं, ताकि स्थिर होने से पहले वह गतिरोध से बाहर निकल सके।
अक्सर पूछे जाने वाले प्रश्न
क्या सबसे छोटे रास्ते का कोई सूत्र है?
नहीं। सबसे छोटा टूर सभी शहरों की सटीक स्थितियों पर निर्भर करता है, और कोई ज्ञात विधि इसे हर नक्शे के लिए ऐसे नहीं खोजती कि सबसे बुरी स्थिति में काम की मात्रा घातांकीय रूप से न बढ़े। कुछ सौ या हज़ार शहरों के लिए, Concorde जैसे विशेष सटीक सॉल्वर रैखिक प्रोग्रामिंग को चतुर छँटाई के साथ मिलाकर फिर भी इष्टतम टूर सिद्ध कर देते हैं, और अब तक सटीक रूप से हल किए गए सबसे बड़े उदाहरण में 85,900 बिंदु हैं।
2-opt हर क्रॉसिंग क्यों हटा देता है?
अगर किसी टूर के दो किनारे एक-दूसरे को काटते हैं, तो वे जिन चार शहरों को जोड़ते हैं वे एक चतुर्भुज बनाते हैं जिसके विकर्ण यही दो किनारे हैं। इन्हें चतुर्भुज की दो आमने-सामने की भुजाओं से बदलना त्रिभुज असमिका के कारण हमेशा छोटा होता है, और इससे बीच का टूर का हिस्सा उलट जाता है। 2-opt तब तक ऐसी अदला-बदली करता रहता है जब तक कोई भी मदद न करे, इसलिए उसका अंतिम टूर कभी खुद को नहीं काटता।
सिम्युलेटेड एनीलिंग में तापमान क्या है?
यह तय करता है कि विधि टूर को लंबा करने वाली चाल को स्वीकार करने के लिए कितनी तैयार है। जो चाल लंबाई में d जोड़ती है, वह e^(−d/T) प्रायिकता से स्वीकार होती है। ऊँचे तापमान T पर लगभग कुछ भी चल जाता है, जिससे टूर किसी खराब व्यवस्था से निकल सकता है; जैसे-जैसे T घटता है, विधि लालची हो जाती है और स्थिर हो जाती है। यह नाम धातु को धीरे-धीरे ठंडा करने से आया है, ताकि उसके परमाणु कम ऊर्जा वाली व्यवस्था पा सकें।
सटीक विधि 12 शहरों तक सीमित क्यों है?
हेल्ड–कार्प शहरों के हर उपसमुच्चय और हर संभव अंतिम शहर के लिए सबसे छोटा रास्ता संग्रहीत करता है, जो लगभग n · 2ⁿ संख्याएँ हैं, और हर एक को n तुलनाओं से भरता है। 12 शहरों के लिए यह कुछ लाख चरण हैं; 25 शहरों के लिए यह अरबों होंगे। फिर भी यह सभी (n − 1)! / 2 टूर आज़माने से बहुत ज़्यादा तेज़ है: 12 शहरों के लिए वे लगभग 2 करोड़ होंगे।
क्या कुछ सर्वर पर भेजा जाता है?
नहीं। शहर और पाँचों विधियाँ आपके ब्राउज़र में चलती हैं। आप जो शहर क्लिक करके जोड़ते हैं, वे इसी ब्राउज़र के लोकल स्टोरेज में रहते हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ