Cutting-plane methodology via quantum optimization for solving the Traveling Salesman Problem
यह शोध पत्र एक पुनरावृत्ति ढांचे का प्रस्ताव करता है जो डायनेमिक सबटूर एलिमिनेशन, आर्क प्रीप्रोसेसिंग और क्लासिकल एवं क्वांटम (डी-वेव एनीलिंग और हाइब्रिड सहित) दोनों अनुकूलन विधियों को जोड़ता है ताकि ट्रैवलिंग सेल्समैन प्रॉब्लम को हल करने के लिए मॉडल के आकार को महत्वपूर्ण रूप से कम किया जा सके और कम्प्यूटेशनल प्रदर्शन में सुधार किया जा सके।
मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें
कल्पना कीजिए कि आप एक घूमते हुए सेल्समैन हैं जिसके पास 30 शहरों का एक नक्शा है। आपका लक्ष्य सरल है: हर शहर में ठीक एक बार जाना और वापस घर लौटना, लेकिन आप ईंधन बचाने के लिए सबसे कम दूरी वाला रास्ता चुनना चाहते हैं।
यह ट्रैवलिंग सेल्समैन प्रॉब्लम (TSP) है। हालांकि यह सुनने में आसान लगता है, लेकिन यह एक कुख्यात गणितीय दुःस्वप्न है। यदि आपके पास 10 शहर हैं, तो लाखों संभावित मार्ग होते हैं। यदि 30 शहर हैं, तो मार्गों की संख्या इतनी विशाल हो जाती है कि वह ब्रह्मांड में मौजूद परमाणुओं की संख्या से भी अधिक हो जाती है। हर एक मार्ग की जांच करना असंभव है।
यह शोध पत्र इस पहेली को हल करने के लिए क्वांटम कंप्यूटरों का उपयोग करके एक नए तरीके के बारे में है, लेकिन इसमें एक चतुर ट्रिक का उपयोग किया गया है ताकि क्वांटम कंप्यूटर का काम आसान हो सके।
यहाँ उनकी रणनीति का विवरण दिया गया है, सरल उपमाओं (analogies) का उपयोग करते हुए:
1. बड़ी समस्या: "सबटूर" (Subtour) का जाल
जब आप किसी कंप्यूटर को सबसे छोटा रास्ता खोजने के लिए कहते हैं, तो वह अक्सर आलसी हो जाता है। सभी शहरों का एक बड़ा चक्कर लगाने के बजाय, वह कुछ छोटे चक्कर ढूंढ सकता है।
- उपमा: कल्पना कीजिए कि आप एक रोबोट को एक सड़क के हर घर में जाने और वापस आने के लिए कहते हैं। पूरी सड़क पर चलने के बजाय, रोबट तीन घरों के चारों ओर एक घेरा बना सकता है, फिर रुक सकता है, और फिर तीन अन्य घरों के चारों ओर एक घेरा बना सकता है। उसने सभी के घर देखे, लेकिन उसने एक निरंतर यात्रा नहीं की।
- गणित: कंप्यूटर की भाषा में, इन्हें "सबटूर" कहा जाता है। कंप्यूटर को यह करने से रोकने के लिए, गणितज्ञों को नियम (constraints) जोड़ने पड़ते हैं, जैसे कि, "आप एक छोटा घेरा नहीं बना सकते; आपको चलते रहना होगा।"
- दुःस्वप्न: समस्या यह है कि 30 शहरों के लिए, हर संभव छोटे घेरे को रोकने के लिए आवश्यक नियमों की संख्या अत्यधिक है। यह वैसा ही है जैसे किसी बच्चे द्वारा खेल बिगाड़ने के हर संभावित तरीके के लिए एक नियम पुस्तिका लिखने की कोशिश करना। नियम पुस्तिका इतनी मोटी हो जाएगी कि उसे पढ़ा नहीं जा सकेगा, और कंप्यूटर क्रैश हो जाएगा।
2. समाधान: दो स्मार्ट ट्रिक्स
लेखकों ने महसूस किया कि एक साथ सभी नियम लिखना असंभव है। इसलिए, उन्होंने समस्या को इतना छोटा करने के लिए दो रणनीतियों का उपयोग किया कि एक क्वांटम कंप्यूटर इसे संभाल सके।
ट्रिक A: "कटिंग-प्लेन" विधि (जासूस)
शुरुआत में ही सारे नियम लिखने के बजाय, वे नियमों के एक बहुत ही सरल सेट के साथ शुरुआत करते हैं। वे कंप्यूटर को एक मार्ग का अनुमान लगाने देते हैं।
- यह कैसे काम करता है:
- कंप्यूटर एक मार्ग का अनुमान लगाता है।
- "जासूस" उस मार्ग की जांच करता है। "अरे, तुमने इन तीन शहरों के चारों ओर एक छोटा घेरा बनाया! यह मान्य नहीं है।"
- जासूस केवल उस विशिष्ट गलती को रोकने के लिए एक विशेष नियम जोड़ता है।
- कंप्यूटर फिर से प्रयास करता है।
- जब तक कंप्यूटर एक आदर्श, एकल लूप नहीं खोज लेता, तब तक यह प्रक्रिया दोहराई जाती है।
- लाभ: नियमों की लाइब्रेरी ले जाने के बजाय, कंप्यूटर केवल उन कुछ नियमों को साथ रखता है जिनकी उसे अपनी गलतियों को सुधारने के लिए वास्तव में आवश्यकता होती है। इसे कटिंग-प्लेन अप्रोच (CPA) कहा जाता है।
ट्रिक B: "आर्क फ़िल्टरिंग" (नक्शे को छोटा करना)
कंप्यूटर के अनुमान लगाने से पहले ही, लेखक खराब सड़कों को हटाने के लिए एक प्री-चेक का उपयोग करते हैं।
- उपमा: कल्पना कीजिए कि आप न्यूयॉर्क से लॉस एंजिल्स जा रहे हैं। आप जानते हैं कि आप कभी भी विपरीत दिशा में किसी शहर की ओर या किसी ऐसे छोटे, घुमावदार कच्चे रास्ते पर नहीं जाएंगे जो 100 मील अतिरिक्त जोड़ देता है। आप केवल मुख्य राजमार्गों की परवाह करते हैं।
- यह कैसे काम करता है: वे नक्शे को देखते हैं और किसी भी ऐसे रास्ते को हटा देते हैं जो स्पष्ट रूप से बहुत लंबा या अक्षम है। यदि शहर A से शहर B तक जाने के लिए कोई रास्ता 10वां सबसे अच्छा विकल्प है, तो वे मान लेते हैं कि सबसे अच्छे 5 विकल्प पर्याप्त हैं और उस रास्ते को हटा देते हैं।
- लाभ: यह नक्शे को काफी छोटा कर देता है। कम सड़कें मतलब कंप्यूटर के लिए कम विकल्प, जिससे पहेली बहुत छोटी हो जाती है।
3. क्वांटम वाला हिस्सा: जादुई मशीन
एक बार जब उन्होंने ऊपर दिए गए दो ट्रिक्स का उपयोग करके समस्या को छोटा कर दिया, तो उन्होंने इसे एक क्वांटम कंप्यूटर (विशेष रूप से एक D-Wave मशीन) में फीड किया।
- क्वांटम कंप्यूटर क्या है? एक क्लासिकल कंप्यूटर को एक भूलभुलैया से बाहर निकलने का रास्ता खोजने के लिए एक बार में एक रास्ता चलते हुए व्यक्ति के रूप में सोचें। एक क्वांटम कंप्यूटर एक भूत की तरह है जो एक ही समय में सभी रास्तों पर चल सकता है, और यह महसूस कर सकता है कि कौन सा रास्ता सबसे "हल्का" (छोटा) है।
- चुनौती: क्वांटम कंप्यूटर वर्तमान में छोटे और नाजुक हैं। वे उन विशाल, जटिल समस्याओं को नहीं संभाल सकते जो हम आमतौर पर उन पर थोपते हैं।
- परिणाम: क्योंकि लेखकों ने अपने "जासूस" (CPA) और "मैप श्रिंकर" (CAF) ट्रिक्स का उपयोग किया, वे 30 शहरों की समस्या के आकार को क्वांटम कंप्यूटर में डालने में सक्षम रहे जिसे उसने पहले कभी हल नहीं किया था।
4. परिणाम: क्लासिकल बनाम क्वांटम
लेखकों ने समस्या को हल करने के तीन तरीकों का परीक्षण किया:
- पुराना तरीका (क्लासिकल): एक मानक कंप्यूटर के साथ पूरी चीज़ को हल करने की कोशिश करना।
- परिणाम: यह छोटे नक्शों के लिए काम कर गया, लेकिन 30 शहरों के लिए, कंप्यूटर "नियम पुस्तिका" की समस्या में फंस गया और पूरा नहीं कर सका।
- डायरेक्ट क्वांटम तरीका: बिना "जासूस" ट्रिक के सीधे क्वांटम कंप्यूटर को समस्या भेजना।
- परिणाम: क्वांटम कंप्यूटर नियमों की भारी संख्या के कारण भ्रमित हो गया और एक अच्छा मार्ग खोजने में विफल रहा।
- हाइब्रिड तरीका (विजेता): "जासूस" और "मैप श्रिंकर" ट्रिक्स का उपयोग करना, और फिर एक हाइब्रिड सॉल्वर को काम करने देना।
- हाइब्रिड सॉल्वर क्या है? एक टीम की कल्पना करें जहाँ एक इंसान (क्लासिकल कंप्यूटर) भारी काम और योजना बनाना करता है, लेकिन सबसे आशाजनक रास्तों को जल्दी से जांचने के लिए एक भविष्यवक्ता (क्वांटम कंप्यूटर) को बुलाता है।
- परिणाम: इस टीम ने 30-शहर की समस्या को पूरी तरह से हल कर दिया! उन्होंने लगभग 2 मिनट में सबसे अच्छा मार्ग खोज लिया, जबकि पुराना तरीका शुरू भी नहीं कर पाया था।
सारांश
यह शोध पत्र मूल रूप से कह रहा है: "क्वांटम कंप्यूटर शक्तिशाली हैं, लेकिन वे वर्तमान में बड़े, जटिल कार्यों को संभालने के लिए बहुत छोटे हैं। हालांकि, यदि हम पहले समस्या को साफ करने के लिए स्मार्ट क्लासिकल ट्रिक्स का उपयोग करते हैं (खराब सड़कों को हटाना और केवल आवश्यकता होने पर ही नियम जोड़ना), तो हम क्वांटम कंप्यूटरों को उन वास्तविक दुनिया की पहेलियों को हल करने में सक्षम बना सकते हैं जो पहले असंभव थीं।"
उन्होंने केवल एक बेहतर इंजन नहीं बनाया; उन्होंने एक बेहतर नक्शा बनाया ताकि इंजन वास्तव में चल सके।
अपने क्षेत्र के पेपरों की भीड़ में उलझे हुए हैं?
आपके रिसर्च कीवर्ड से मेल खाने वाले सबसे नए और अलग सोच वाले पेपरों का रोज़ाना Digest पाएँ—तकनीकी सारांश के साथ, आपकी भाषा में।