ऑनलाइन एल्गोरिदम
कंप्यूटर विज्ञान में, एक ऑनलाइन एल्गोरिदम[1]वह एक है जो अपने इनपुट को एक-एक करके सीरियल फैशन में प्रोसेस कर सकता है, यानी, इस क्रम में कि इनपुट एल्गोरिथ्म को फीड किया जाता है, शुरू से ही पूरे इनपुट को उपलब्ध कराए बिना।
इसके विपरीत, एक ऑफ़लाइन एल्गोरिथ्म को शुरुआत से ही पूरी समस्या का डेटा दिया जाता है और एक उत्तर को आउटपुट करने की आवश्यकता होती है जो समस्या को हल करता है। संचालन अनुसंधान में, जिस क्षेत्र में ऑनलाइन एल्गोरिदम विकसित किए जाते हैं, उसे ऑनलाइन अनुकूलन कहा जाता है।
एक उदाहरण के रूप में, छँटाई एल्गोरिदम चयन छँटाई और सम्मिलन छँटाई पर विचार करें: चयन छँटाई बार-बार अवर्गीकृत शेष से न्यूनतम तत्व का चयन करता है और इसे सामने रखता है, जिसके लिए पूरे इनपुट तक पहुँच की आवश्यकता होती है; इस प्रकार यह एक ऑफ़लाइन कलन विधि है। दूसरी ओर, सम्मिलन क्रम प्रति पुनरावृत्ति एक इनपुट तत्व पर विचार करता है और भविष्य के तत्वों पर विचार किए बिना आंशिक समाधान उत्पन्न करता है। इस प्रकार सम्मिलन छँटाई एक ऑनलाइन एल्गोरिथम है।
ध्यान दें कि सम्मिलन प्रकार का अंतिम परिणाम इष्टतम है, अर्थात, सही ढंग से क्रमबद्ध सूची। कई समस्याओं के लिए, ऑनलाइन एल्गोरिदम ऑफ़लाइन एल्गोरिदम के प्रदर्शन से मेल नहीं खा सकते हैं। यदि एक ऑनलाइन एल्गोरिथम और एक इष्टतम ऑफ़लाइन एल्गोरिथम के प्रदर्शन के बीच का अनुपात सीमित है, तो ऑनलाइन एल्गोरिथम को प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिथम) कहा जाता है।[1] प्रत्येक ऑफ़लाइन एल्गोरिथम का एक कुशल ऑनलाइन प्रतिरूप नहीं होता है।
परिभाषा
क्योंकि यह पूरे इनपुट को नहीं जानता है, एक ऑनलाइन एल्गोरिदम निर्णय लेने के लिए मजबूर होता है जो बाद में इष्टतम नहीं हो सकता है, और ऑनलाइन एल्गोरिदम के अध्ययन ने निर्णय लेने की गुणवत्ता पर ध्यान केंद्रित किया है जो इस सेटिंग में संभव है। प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिथम) समान समस्या उदाहरण के लिए एक ऑनलाइन और ऑफलाइन एल्गोरिदम के सापेक्ष प्रदर्शन की तुलना करके इस विचार को औपचारिक रूप देता है। विशेष रूप से, एक एल्गोरिथम का प्रतिस्पर्धी अनुपात, इसकी लागत के सबसे खराब-मामले के अनुपात के रूप में परिभाषित किया गया है, जो सभी संभावित इनपुट पर इष्टतम लागत से विभाजित है। एक ऑनलाइन समस्या का प्रतिस्पर्धी अनुपात एक ऑनलाइन एल्गोरिथम द्वारा प्राप्त सर्वोत्तम प्रतिस्पर्धी अनुपात है। सहज रूप से, एक एल्गोरिथ्म का प्रतिस्पर्धी अनुपात इस एल्गोरिथम द्वारा उत्पादित समाधानों की गुणवत्ता पर एक माप देता है, जबकि किसी समस्या का प्रतिस्पर्धी अनुपात इस समस्या के भविष्य को जानने के महत्व को दर्शाता है।
अन्य व्याख्याएं
एल्गोरिदम के ऑनलाइन इनपुट पर अन्य दृष्टिकोणों के लिए, देखें
- स्ट्रीमिंग एल्गोरिदम: पिछले इनपुट का सटीक रूप से प्रतिनिधित्व करने के लिए आवश्यक मेमोरी की मात्रा पर ध्यान केंद्रित करना;
- गतिशील एल्गोरिदम: ऑनलाइन इनपुट के साथ समस्याओं के समाधान को बनाए रखने की समय जटिलता पर ध्यान केंद्रित करना।
उदाहरण
कुछ ऑनलाइन एल्गोरिदम:
- सम्मिलन सॉर्ट
- परसेप्ट्रॉन
- जलाशय नमूनाकरण
- लालची एल्गोरिदम
- प्रतिकूल (ऑनलाइन एल्गोरिथम)
- मीट्रिक कार्य प्रणाली
- ऑड्स एल्गोरिथम
- पृष्ठ प्रतिस्थापन एल्गोरिथ्म
- विचरण की गणना के लिए एल्गोरिदम
- उकोनेन का एल्गोरिदम
ऑनलाइन समस्याएं
ऑनलाइन एल्गोरिथम की अवधारणाओं को उदाहरण देने वाली एक समस्या कनाडाई यात्री समस्या है। इस समस्या का लक्ष्य एक भारित ग्राफ़ में लक्ष्य तक पहुँचने की लागत को कम करना है जहाँ कुछ किनारे अविश्वसनीय हैं और ग्राफ़ से हटा दिए गए हैं। हालांकि, एक किनारे को हटा दिया गया है (विफल) केवल यात्री को पता चलता है जब वह किनारे के अंत बिंदुओं में से एक तक पहुंचता है। इस समस्या के लिए सबसे खराब स्थिति बस यह है कि सभी अविश्वसनीय किनारे विफल हो जाते हैं और समस्या सामान्य शॉर्टेस्ट पाथ समस्या में कम हो जाती है। प्रतिस्पर्धी विश्लेषण की मदद से समस्या का वैकल्पिक विश्लेषण किया जा सकता है। विश्लेषण की इस पद्धति के लिए, ऑफ़लाइन एल्गोरिथ्म पहले से जानता है कि कौन से किनारे विफल होंगे और लक्ष्य ऑनलाइन और ऑफ़लाइन एल्गोरिदम के प्रदर्शन के बीच के अनुपात को कम करना है। यह समस्या पीएसपीएसीई-पूर्ण है।
कई औपचारिक समस्याएं हैं जो समाधान के रूप में एक से अधिक ऑनलाइन एल्गोरिथम प्रदान करती हैं:
- के-सर्वर प्रॉब्लम | के-सर्वर प्रॉब्लम
- जॉब शॉप शेड्यूलिंग
- सूची अद्यतन समस्या
- बैंडिट समस्या
- सचिव समस्या
- खोज खेल
- स्की किराये की समस्या
- रैखिक खोज समस्या
- पोर्टफोलियो चयन समस्या[2]
यह भी देखें
- गतिशील एल्गोरिदम
- पैगंबर असमानता
- रीयल-टाइम कंप्यूटिंग
- स्ट्रीमिंग एल्गोरिदम
- अनुक्रमिक एल्गोरिदम
- ऑनलाइन मशीन लर्निंग/ऑफलाइन लर्निंग
संदर्भ
- ↑ 1.0 1.1 Karp, Richard M. (1992). "ऑन-लाइन एल्गोरिदम बनाम ऑफ-लाइन एल्गोरिदम: भविष्य जानने के लिए कितना लायक है?" (PDF). IFIP Congress (1). 12: 416–429. Retrieved 17 August 2015.
- ↑ Dochow, Robert (2016). पोर्टफोलियो चयन समस्या के लिए ऑनलाइन एल्गोरिदम. Springer Gabler.
- Borodin, A.; El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5.
