41 साल बाद नया shortest path algorithm खोजा गया
(arxiv.org)चीन की Tsinghua University की शोध टीम ने Stanford University के साथ मिलकर पारंपरिक shortest path (single-source shortest path, SSSP) समस्या में computational complexity के लिहाज़ से बड़ी प्रगति हासिल की है। इस शोध को 2025 STOC सम्मेलन में Best Paper पुरस्कार मिला।
पारंपरिक रूप से सबसे अधिक इस्तेमाल किया जाने वाला तरीका Dijkstra algorithm है, जिसकी time complexity O(m + n log n) (n = nodes की संख्या, m = edges की संख्या) के रूप में होती है।
log n पद priority queue या sorting से जुड़े हिस्से से संबंधित है, और पिछले 40 वर्षों में इस हिस्से से आगे निकलने वाला कोई सुधार नहीं हुआ था.
नए algorithm ने time complexity को O(m · log^(2/3) n) तक घटा दिया है।
चूँकि log^(2/3) n, log n की तुलना में अधिक धीमी गति से बढ़ता है, इसलिए nodes की संख्या बहुत बड़ी होने पर यह अंतर काफी बढ़ जाता है.
18 टिप्पणियां
2000 के दशक के आखिर में वाहन navigation software कंपनी में काम करते हुए route search module डेवलप करने की यादें(?) ताज़ा हो गईं।
Dijkstra navigation route search के लिए बहुत धीमा था, इसलिए उसे इस्तेमाल नहीं करते थे और heuristic से बेहतर बनाया गया वर्जन A*(A Star) search इस्तेमाल करते थे। खोजने पर पता चला कि A* SSSP नहीं बल्कि SPSP(Single-Pair Shortest Path) algorithm है।
sparse केस में तेज़ एल्गोरिदम को पार कर गया है, ऐसा कहना थोड़ा अस्पष्ट लगता है।
CLRS को संशोधित हुए ज़्यादा समय नहीं हुआ होगा, फिर से नया संस्करण छाप रहे हैं क्या
ऐसा लगता है जैसे Beatles या Oasis जैसे पुराने लेकिन आज भी लोकप्रिय बैंड का 41 साल बाद नया एल्बम आ गया हो। पहले तो हैरानी होती है, फिर उत्सुकता बढ़ती है, हा हा
अमेरिका में शायद यह पहले से ही था? हाहाहा
बहुत खूबसूरत है, सच में कमाल
चीन आजकल काफ़ी तेज़ी से आगे बढ़ रहा है।
एल्गोरिदम का नाम कैसे तय होगा, यह दिलचस्प होगा
लगता है कोई जल्द ही उन constraints के साथ Baekjoon पर एक problem डाल देगा, सोचकर ही दिल धड़क रहा है
पुरानी यादों वाला Dijkstra..
वाह... कमाल है...
कमाल है।
वाह......
यह तो हो गया...
वाह~~
वाह....
लगता है algorithm class का syllabus अब बढ़ेगा, हाहा
अरे बाप रे...