A Surface-Based Formulation of the Traveling Salesman Problem
यह शोधपत्र सममित ट्रैवलिंग सेल्समैन समस्या (Traveling Salesman Problem) के लिए एक सटीक, सतह-आधारित मिश्रित-पूर्णांक रैखिक प्रोग्रामिंग (mixed-integer linear programming) सूत्रीकरण प्रस्तुत करता है जो जुड़े हुए त्रिभुजों का चयन करके और ट्री बाधाओं (tree constraints) एवं यूलर विशेषता (Euler characteristic) की शर्तों के माध्यम से वैश्विक कनेक्टिविटी को लागू करके एक टूर का निर्माण करता है, जो डेलाउनी त्रिकोणीकरण (Delaunay triangulations) जैसे विरल उम्मीदवार सेटों तक सीमित होने पर एक व्यावहारिक ह्यूरिस्टिक (heuristic) प्रदान करता है।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक शहर के योजनाकार (city planner) हैं जो 50 अलग-अलग घरों और वापस घर लौटने के लिए एक डिलीवरी ट्रक के लिए सबसे छोटा संभव रास्ता खोजने की कोशिश कर रहे हैं। यह प्रसिद्ध ट्रैवलिंग सेल्समैन प्रॉब्लम (TSP) है।
आमतौर पर, गणितज्ञ इसे इस तरह हल करते हैं जैसे वे सड़कों के एक जाल (web of roads) को देख रहे हों। वे एक एकल लूप बनाने के लिए सड़कों (edges) के सही संयोजन को चुनने की कोशिश करते हैं। लेकिन यह ईंटों को एक-एक करके चुनने और यह उम्मीद करने जैसा है कि वे आपस में जुड़कर एक छत बना लें। यह बहुत उलझन भरा हो जाता है क्योंकि आपको लगातार यह जांचना पड़ता है कि, "क्या मैंने गलती से एक छोटा सा लूप बना दिया है जिसमें कोई घर छूट गया है?" या "क्या ट्रक किसी डेड-एंड (बंद रास्ते) में फंस गया है?"
यह शोध पत्र सोचने का एक बिल्कुल अलग तरीका प्रस्तावित करता है। सड़कों को देखने के बजाय, आइए पड़ोस (neighborhoods) को देखें।
नया विचार: एक "पैचवर्क क्विल्ट" (रजाई के टुकड़ों) का निर्माण करना
कल्पना कीजिए कि डिलीवरी रूट एक रेखा नहीं, बल्कि एक पैचवर्क क्विल्ट (रजाई के टुकड़ों) का किनारा है।
- त्रिभुज (कपड़ा): सड़कों को चुनने के बजाय, कंप्यूटर त्रिभुजों (तीन जुड़े हुए घर) को चुनता है ताकि एक ठोस, जुड़ा हुआ कपड़ा बनाया जा सके।
- सतह (क्विल्ट): कंप्यूटर इन त्रिभुजों को एक बड़े, जुड़े हुए आकार (एक सतह) में सिलने की कोशिश करता है।
- द टूर (बॉर्डर): एक बार जब क्विल्ट सिल जाता है, तो उस क्विल्ट का बाहरी किनारा ही आपका डिलीवरी रूट होता है!
जादुई ट्रिक:
कंप्यूटर को यह चिंता करने की ज़रूरत नहीं है कि रूट एक एकल लूप होगा या नहीं। उसे बस यह सुनिश्चित करना है कि "क्विल्ट" कपड़े का एक एकल, ठोस टुकड़ा है जिसमें बीच में कोई छेद नहीं है और न ही कोई अजीब फटन है। यदि कपड़ा एक आदर्श, ठोस आकार है, तो उसका बॉर्डर अपने आप एक आदर्श लूप बन जाता है जो हर घर में ठीक एक बार जाता है।
यह कैसे काम करता है ( "कैंसलिंग आउट" का रूपक)
यहाँ वह चतुर हिस्सा है कि कंप्यूटर लागत (cost) की गणना कैसे करता है:
- आंतरिक किनारे (सीम/टांके): जब दो त्रिभुजों को एक साथ सिला जाता है, तो वे एक तरफ साझा करते हैं। गणित में, कंप्यूटर इस साझा किनारे की लंबाई को दो बार गिनता है: एक पहले त्रिभुज के लिए और एक दूसरे के लिए। लेकिन क्योंकि वे क्विल्ट के "अंदर" हैं, गणित उन्हें एक दूसरे को रद्द (cancel out) कर देता है (जैसे +1 और -1)। वे अंतिम लागत से गायब हो जाते हैं।
- बॉर्डर किनारे (किनारे): त्रिभुजों के वे पक्ष जो किसी और के साथ साझा नहीं किए गए हैं, वे ही बाहर निकले हुए होते हैं। केवल वे ही हैं जो गणना में शेष रहते हैं। वे ही अंतिम गणना में बचते हैं।
इसलिए, कंप्यूटर मूल रूप से एक ऐसा क्विल्ट बनाने की कोशिश कर रहा है जिसका बॉर्डर की कुल लंबाई जितनी संभव हो उतनी कम हो। वह अंदर के उलझे हुए टांकों को अनदेखा करता है और केवल बाहरी रूपरेखा पर ध्यान देता है।
यह बेहतर क्यों है?
1. कोई "सबटूर" नहीं (कोई डेड एंड नहीं):
पुराने तरीके में, कंप्यूटर को यह रोकने के लिए जटिल नियम लिखने पड़ते हैं कि ट्रक 3 घरों के छोटे घेरे में न फंस जाए और बाकी घरों को छोड़ दे। इस नए तरीके में, कंप्यूटर को बस यह सुनिश्चित करना है कि "क्विल्ट" एक ठोस टुकड़ा है। यदि कपड़ा जुड़ा हुआ है, तो बॉर्डर अपने आप एक बड़ा लूप बन जाता है। इसमें गलती होने की संभावना बहुत कम है!
2. "डेलाने" (Delaunay) शॉर्टकट:
100 घरों वाले शहर के लिए हर संभावित त्रिभुज की गणना करना असंभव है (इसमें सुपरकंप्यूटर को भी अनंत समय लग जाएगा)।
- समाधान: लेखक सुझाव देते हैं कि केवल "निकटतम पड़ोसियों" (जैसे डेलाने ट्राइएंगुलेशन) द्वारा बनाए गए त्रिभुजों को ही देखा जाए।
- परिणाम: यह ऐसा है जैसे यह कहना कि, "हमें केवल उन घरों को जोड़ने की आवश्यकता है जो एक-दूसरे के बिल्कुल बगल में हैं।" यह समस्या को जल्दी हल करने के लिए पर्याप्त छोटा बना देता है, जबकि फिर भी एक बहुत अच्छा रूट ढूंढ लेता है।
"बो-टाई" (Bowtie) की समस्या
यह शोध पत्र एक अजीब आकार का भी उल्लेख करता है जिसे "बो-टाई" (जहां दो त्रिभुज केवल एक बिंदु पर मिलते हैं, जैसे कि एक आव्रूप/hourglass) कहा जाता है। यदि कंप्यूटर इसे चुनता है, तो रूट टूट जाता है।
- समाधान: यह पेपर एक सरल "यूलर फ़िल्टर" (Euler Filter) नियम जोड़ता है। यह एक गुणवत्ता नियंत्रण निरीक्षक की तरह है जो हर घर की जांच करता है और कहता है, "इस घर के चारों ओर का कपड़ा एक एकल, अखंड घेरा होना चाहिए।" यदि किसी घर के आसपास कपड़ा फटा हुआ या अलग-थलग है, तो कंप्यूटर उस क्विल्ट को खारिज कर देता है और फिर से प्रयास करता है।
सारांश
पुराने तरीके को एक पूर्ण वृत्त बनाने की कोशिश के रूप में सोचें जहाँ आप बिंदुओं को एक-एक करके जोड़ते हैं और लगातार जांचते हैं कि क्या आपने लूप बंद किया है।
यह नया तरीका एक कुकी कटर (cookie cutter) के सांचे की तरह है। आप आटे पर एक आकार (क्विल्ट) छापते हैं। आपको कुकी के अंदर की परवाह नहीं है; आपको बस यह परवाह है कि कुकी कटर एक एकल, ठोस टुकड़ा है। उसका किनारा अपने आप आपका एक आदर्श रूट बन जाता है।
यह दृष्टिकोण एक उलझे हुए, कठिन समस्या को एक ठोस सतह बनाने की एक साफ, ज्यामितीय समस्या में बदल देता है, जिससे कंप्यूटर के लिए सबसे अच्छा रास्ता खोजना बहुत आसान हो जाता है।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।