ऑनलाइन एल्गोरिदम

Not to be confused with online and offline.

संगणक विज्ञान में, एक ऑनलाइन एल्गोरिथमवह एक है जो अपने इनपुट को एक-एक करके क्रमिक कार्य प्रणाली में प्रक्रिया कर सकता है, अर्थात्, इस क्रम में कि इनपुट एल्गोरिथम को फीड जाता है, बिना पूरे इनपुट को प्रारंभ से उपलब्ध कराए।

इसके विपरीत, एक ऑफ़लाइन एल्गोरिथम को प्रारंभ से ही पूरी समस्या का डेटा दिया जाता है और एक उत्तर को आउटपुट करने की आवश्यकता होती है जो समस्या को हल करता है। संचालन अनुसंधान में, जिस क्षेत्र में ऑनलाइन एल्गोरिथम विकसित किए जाते हैं, उसे ऑनलाइन अनुकूलन कहा जाता है।

एक उदाहरण के रूप में, छँटाई एल्गोरिथम चयन छँटाई और सम्मिलन छँटाई पर विचार करें: चयन छँटाई बार-बार अवर्गीकृत शेष से न्यूनतम तत्व का चयन करता है और इसे सामने रखता है, जिसके लिए पूरे इनपुट तक पहुँच की आवश्यकता होती है; इस प्रकार यह एक ऑफ़लाइन एल्गोरिथम है। दूसरी ओर, सम्मिलन क्रम प्रति पुनरावृत्ति एक इनपुट तत्व पर विचार करता है और भविष्य के तत्वों पर विचार किए बिना आंशिक समाधान उत्पन्न करता है। इस प्रकार सम्मिलन छँटाई एक ऑनलाइन एल्गोरिथम है।

ध्यान दें कि सम्मिलन प्रकार का अंतिम परिणाम सर्वोत्कृष्ट है, अर्थात, सही संरचना से क्रमबद्ध सूची। कई समस्याओं के लिए, ऑनलाइन एल्गोरिथम ऑफ़लाइन एल्गोरिथम के प्रदर्शन के समान नहीं हो सकता हैं। यदि एक ऑनलाइन एल्गोरिथम और एक सर्वोत्कृष्ट ऑफ़लाइन एल्गोरिथम के प्रदर्शन के बीच का अनुपात सीमित है, तो ऑनलाइन एल्गोरिथम को प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिथम) कहा जाता है।

प्रत्येक ऑफ़लाइन एल्गोरिथम का एक कुशल ऑनलाइन प्रतिरूप नहीं होता है।

परिभाषा

क्योंकि यह पूरे इनपुट को नहीं जानता है, एक ऑनलाइन एल्गोरिथम निर्णय लेने के लिए बाध्य होता है जो बाद में सर्वोत्कृष्ट नहीं हो सकता है, और ऑनलाइन एल्गोरिथम के अध्ययन ने निर्णय लेने की गुणवत्ता पर ध्यान केंद्रित किया है जो इस सेटिंग में संभव है। प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिथम) समान समस्या उदाहरण के लिए एक ऑनलाइन और ऑफलाइन एल्गोरिथम के सापेक्ष प्रदर्शन की तुलना करके इस विचार को औपचारिक रूप देता है। विशेष रूप से, एक एल्गोरिथम का प्रतिस्पर्धी अनुपात, इसकी लागत के सबसे खराब-स्थियों के अनुपात के रूप में परिभाषित किया गया है, जो सभी संभावित इनपुट पर सर्वोत्कृष्ट लागत से विभाजित है। एक ऑनलाइन समस्या का प्रतिस्पर्धी अनुपात एक ऑनलाइन एल्गोरिथम द्वारा प्राप्त सर्वोत्तम प्रतिस्पर्धी अनुपात है। सहज रूप से, एक एल्गोरिथम का प्रतिस्पर्धी अनुपात इस एल्गोरिथम द्वारा उत्पादित समाधानों की गुणवत्ता पर एक माप देता है, जबकि किसी समस्या का प्रतिस्पर्धी अनुपात इस समस्या के भविष्य को जानने के महत्व को दर्शाता है।

अन्य व्याख्याएं

एल्गोरिथम के ऑनलाइन इनपुट पर अन्य दृष्टिकोणों के लिए, देखें

• स्ट्रीमिंग एल्गोरिथम: पिछले इनपुट का यथार्थ रूप से प्रतिनिधित्व करने के लिए आवश्यक मेमोरी की मात्रा पर ध्यान केंद्रित करना;
• गतिशील एल्गोरिथम: ऑनलाइन इनपुट के साथ समस्याओं के समाधान को बनाए रखने की समय जटिलता पर ध्यान केंद्रित करना।

उदाहरण

कुछ ऑनलाइन एल्गोरिथम:

• सम्मिलन सॉर्ट
• परसेप्ट्रॉन
• जलाशय नमूनाकरण
• लालची एल्गोरिथम
• प्रतिकूल (ऑनलाइन एल्गोरिथम)
• मीट्रिक कार्य प्रणाली
• ऑड्स एल्गोरिथम
• पृष्ठ प्रतिस्थापन एल्गोरिथम
• विचरण की गणना के लिए एल्गोरिथम
• उकोनेन का एल्गोरिथम

ऑनलाइन समस्याएं

ऑनलाइन एल्गोरिथम की अवधारणाओं को उदाहरण देने वाली एक समस्या कनाडाई यात्री समस्या है। इस समस्या का लक्ष्य एक भारित ग्राफ़ में लक्ष्य तक पहुँचने की लागत को कम करना है जहाँ कुछ किनारे अविश्वसनीय हैं और ग्राफ़ से हटा दिए गए हैं। चूंकि, एक किनारे को हटा दिया गया है (विफल) केवल यात्री को पता चलता है जब वह किनारे के अंत बिंदुओं में से एक तक पहुंचता है। इस समस्या के लिए सबसे खराब स्थिति बस यह है कि सभी अविश्वसनीय किनारे विफल हो जाते हैं और समस्या सामान्य शॉर्टेस्ट पाथ समस्या में कम हो जाती है। प्रतिस्पर्धी विश्लेषण की मदद से समस्या का वैकल्पिक विश्लेषण किया जा सकता है। विश्लेषण की इस पद्धति के लिए, ऑफ़लाइन एल्गोरिथम पहले से जानता है कि कौन से किनारे विफल होंगे और लक्ष्य ऑनलाइन और ऑफ़लाइन एल्गोरिथम के प्रदर्शन के बीच के अनुपात को कम करना है। यह समस्या पीएसपीएसीई-पूर्ण है।

कई औपचारिक समस्याएं हैं जो समाधान के रूप में एक से अधिक ऑनलाइन एल्गोरिथम प्रदान करती हैं:

• के-सर्वर प्रॉब्लम
• जॉब शॉप शेड्यूलिंग
• सूची अद्यतन समस्या
• बैंडिट समस्या
• सचिव समस्या
• खोज खेल
• स्की किराये की समस्या
• रैखिक खोज समस्या
• पोर्टफोलियो चयन समस्या

यह भी देखें

• गतिशील एल्गोरिथम
• पैगंबर असमानता
• रीयल-टाइम कंप्यूटिंग
• स्ट्रीमिंग एल्गोरिथम
• अनुक्रमिक एल्गोरिथम
• ऑनलाइन मशीन लर्निंग/ऑफलाइन लर्निंग

संदर्भ

• Borodin, A.; El-Yaniv, R. (1998). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5.

बाहरी संबंध

• Bibliography of papers on online algorithms