Manoj Gupta ने तोड़ी 1996 से अटकी शॉर्टेस्ट-पाथ एल्गोरिदम की सीमा

IIT गांधीनगर (Indian Institute of Technology Gandhinagar) के शोधकर्ता Manoj Gupta ने कंप्यूटर साइंस की एक ऐसी सीमा को पार किया है, जो 1996 से बनी हुई थी। उनका एल्गोरिदम विशाल नेटवर्क में बिंदुओं के बीच की सबसे छोटी दूरी का अनुमान पहले से ज़्यादा सटीकता से लगाता है, वह भी गणना का समय बढ़ाए बिना।

क्या है APSP समस्या

नेटवर्क को ऐसे बिंदुओं का समूह समझा जा सकता है जो आपस में जुड़े होते हैं। ये बिंदु शहर, कंप्यूटर, रेलवे स्टेशन, यहाँ तक कि न्यूरॉन या जैविक संरचनाओं के हिस्से भी हो सकते हैं। नेविगेशन ऐप, परिवहन प्रणाली और इंटरनेट इंफ्रास्ट्रक्चर रोज़ ऐसी गणनाएँ करते हैं। मुश्किल तब बढ़ती है, जब बड़े नेटवर्क में हर संभव जोड़ी के बीच की दूरी निकालनी हो। कंप्यूटर साइंस में इसे APSP (All-Pairs Shortest Paths) कहा जाता है।

घने और बड़े नेटवर्क में सटीक नतीजे के लिए भारी कंप्यूटिंग संसाधन चाहिए। इसलिए शोधकर्ता ऐसे तरीके खोजते रहे हैं जो हर रास्ता जाँचे बिना भरोसेमंद अनुमान दे सकें। 1996 में Dor, Halperin और Zwick ने ऐसा एल्गोरिदम पेश किया, जिसमें अनुमानित दूरी असली सबसे छोटे रास्ते के दोगुने से ज़्यादा नहीं होती। इसे 2-गुना सन्निकटन (approximation) कहते हैं।

पुराने तरीके की कमज़ोरी

इस गारंटी का फ़ायदा मुख्यतः दूर-दूर स्थित बिंदुओं पर दिखता था। पास के बिंदुओं में त्रुटि बढ़ सकती थी। मसलन, असली रास्ते में दो कड़ियाँ हों और अनुमान पाँच बता दे, तो दोगुने की सीमा टूट जाती है।

Gupta का समाधान उन बिंदुओं को चुनने का तरीका सुधारता है, जिनके आधार पर दूरी आँकी जाती है। पहले का तरीका प्रतिनिधि बिंदुओं के अपेक्षाकृत छोटे समूह पर टिका था। नया एल्गोरिदम बहु-स्तरीय सैंपलिंग (multi-scale sampling) अपनाता है, यानी नेटवर्क की बनावट को कई स्तरों पर परखता है। इससे छोटी कड़ियाँ भी गिनती में आती हैं, जो पहले छूट सकती थीं।

सबसे अहम बात यह है कि सटीकता बढ़ाने के लिए एल्गोरिदम की कुल कम्प्यूटेशनल जटिलता नहीं बढ़ती। यानी ज़्यादा भरोसेमंद नतीजे मिलते हैं और चलने का समय नहीं बढ़ता।

इस उपलब्धि का असर दूरसंचार, परिवहन, सोशल मीडिया और AI सिस्टम जैसे क्षेत्रों में दिख सकता है, जहाँ नेटवर्क के हिस्सों के बीच दूरी का तेज़ और भरोसेमंद अनुमान निर्भरता के विश्लेषण और पूरे सिस्टम के ऑप्टिमाइज़ेशन में मदद करता है।