“यो एक महान एल्गोरिथ्म हो,” भने एरिक डेमाइनम्यासाचुसेट्स इन्स्टिच्युट अफ टेक्नोलोजीका कम्प्युटर वैज्ञानिक। “यो धेरै छिटो, सरल र कार्यान्वयन गर्न सजिलो छ।”
यो प्रक्रियालाई व्यवहारमा राख्नको लागि, तपाइँले तपाइँको नोटहरू व्यवस्थित गर्नको लागि प्रणालीमा निर्णय गर्न आवश्यक छ – एक डाटा संरचना, कम्प्युटर विज्ञानको भाषामा। त्यो एउटा सानो प्राविधिक विवरण जस्तो लाग्न सक्छ, तर तपाईले कुनै प्रविष्टि सम्पादन गर्न वा हटाउन आवश्यक हुँदा तपाईको नोटहरू खोजी गर्दा समयले एल्गोरिदमको समग्र रनटाइममा ठूलो प्रभाव पार्न सक्छ।
Dijkstra को कागजले एक साधारण डेटा संरचना प्रयोग गर्यो जसले सुधारको लागि ठाउँ छोड्यो। त्यसपछिका दशकहरूमा, अन्वेषकहरूले अझ राम्रा वस्तुहरू विकास गरे, जसलाई मायालु रूपमा “हिप्स” भनिन्छ, जसमा केही वस्तुहरू अरूको तुलनामा फेला पार्न सजिलो हुन्छ। तिनीहरूले Dijkstra को एल्गोरिथ्मले सबैभन्दा नजिकको बाँकी भेर्टेक्सको लागि प्रविष्टि हटाउन आवश्यक छ भन्ने तथ्यको फाइदा उठाउँछन्। “एक ढेर मूलतया एक डाटा संरचना हो जसले तपाईंलाई यो धेरै छिटो गर्न अनुमति दिन्छ,” भन्यो Vaclav Rozhonसोफिया, बुल्गेरियाको कम्प्युटर विज्ञान, कृत्रिम बुद्धिमत्ता र प्रविधि (INSAIT) को लागि संस्थानका अनुसन्धानकर्ता।
1984 मा, दुई कम्प्युटर वैज्ञानिकहरूले विकास गरे चालाक ढेर डिजाइन जसले Dijkstra को एल्गोरिथ्मलाई एकल-स्रोत छोटो-पाथ समस्या समाधान गर्न आवश्यक समयमा सैद्धान्तिक सीमा, वा “तल्लो सीमा” मा पुग्न सक्षम बनायो। एक विशिष्ट अर्थमा, Dijkstra को एल्गोरिदम को यो संस्करण सबै भन्दा राम्रो सम्भव छ। त्यो लगभग 40 वर्षको लागि समस्याको मानक संस्करणमा अन्तिम शब्द थियो। केहि अनुसन्धानकर्ताहरूले “उत्तम” हुनुको अर्थ के हो भनेर नजिकबाट हेरेपछि मात्र चीजहरू परिवर्तन भयो।
उत्तम व्यवहार
अन्वेषकहरूले सामान्यतया एल्गोरिदमहरू सबैभन्दा खराब-केस परिदृश्यहरूमा कसरी भाडामा छन् भनेर अध्ययन गरेर तुलना गर्छन्। संसारको सबैभन्दा भ्रामक सडक ग्रिडको कल्पना गर्नुहोस्, त्यसपछि केही विशेष गरी अन्योलमा पार्ने ट्राफिक ढाँचाहरू थप्नुहोस्। यदि तपाइँ यी चरम परिस्थितिहरूमा द्रुत मार्गहरू खोज्न जोड दिनुहुन्छ भने, Dijkstra को एल्गोरिदमको 1984 संस्करण अपराजेय छ।
तर आशा छ, तपाईंको शहरमा संसारको सबैभन्दा खराब सडक ग्रिड छैन। र त्यसैले तपाईले सोध्न सक्नुहुन्छ: के त्यहाँ कुनै एल्गोरिदम छ जुन हरेक सडक नेटवर्कमा अपराजेय छ? यस प्रश्नको जवाफ दिनको लागि पहिलो चरण भनेको रूढ़िवादी धारणा बनाउनु हो कि प्रत्येक नेटवर्कमा सबैभन्दा खराब-केस ट्राफिक ढाँचाहरू छन्। त्यसोभए तपाइँ तपाइँको एल्गोरिथ्मले कुनै पनि सम्भावित ग्राफ लेआउट मार्फत छिटो मार्गहरू फेला पार्न चाहानुहुन्छ, सबैभन्दा खराब सम्भावित वजनहरू मान्दै। अनुसन्धानकर्ताहरूले यस अवस्थालाई “सार्वभौमिक इष्टतमता” भने। यदि तपाइँसँग ग्राफमा एक बिन्दुबाट अर्को बिन्दुमा पुग्ने सरल समस्याको लागि विश्वव्यापी रूपमा इष्टतम एल्गोरिदम छ भने, यसले तपाइँलाई संसारको हरेक शहरमा भीड घण्टाको ट्राफिकलाई हराउन मद्दत गर्न सक्छ।
