ऑनलाइन एल्गोरिदम: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{confuse|online and offline}} | {{confuse|online and offline}} | ||
{{Short description|Algorithm that begins on possibly incomplete inputs}} | {{Short description|Algorithm that begins on possibly incomplete inputs}} | ||
[[कंप्यूटर विज्ञान]] में, एक ऑनलाइन | [[कंप्यूटर विज्ञान|संगणक विज्ञान]] में, एक ऑनलाइन एल्गोरिथम<ref name="karp92" />वह एक है जो अपने इनपुट को एक-एक करके क्रमिक कार्य प्रणाली में प्रक्रिया कर सकता है, अर्थात्, इस क्रम में कि इनपुट एल्गोरिथम को फीड जाता है, बिना पूरे इनपुट को प्रारंभ से उपलब्ध कराए। | ||
इसके विपरीत, एक ऑफ़लाइन | इसके विपरीत, एक ऑफ़लाइन एल्गोरिथम को प्रारंभ से ही पूरी समस्या का डेटा दिया जाता है और एक उत्तर को आउटपुट करने की आवश्यकता होती है जो समस्या को हल करता है। [[संचालन अनुसंधान]] में, जिस क्षेत्र में ऑनलाइन एल्गोरिथम विकसित किए जाते हैं, उसे [[ऑनलाइन अनुकूलन]] कहा जाता है। | ||
एक उदाहरण के रूप में, [[छँटाई एल्गोरिदम]] चयन छँटाई और सम्मिलन छँटाई पर विचार करें: चयन छँटाई बार-बार अवर्गीकृत शेष से न्यूनतम तत्व का चयन करता है और इसे सामने रखता है, जिसके लिए पूरे इनपुट तक पहुँच की आवश्यकता होती है; इस प्रकार यह एक ऑफ़लाइन [[कलन विधि]] है। दूसरी ओर, सम्मिलन क्रम प्रति पुनरावृत्ति एक इनपुट तत्व पर विचार करता है और भविष्य के तत्वों पर विचार किए बिना आंशिक समाधान उत्पन्न करता है। इस प्रकार सम्मिलन छँटाई एक ऑनलाइन एल्गोरिथम है। | एक उदाहरण के रूप में, [[छँटाई एल्गोरिदम|छँटाई एल्गोरिथम]] चयन छँटाई और सम्मिलन छँटाई पर विचार करें: चयन छँटाई बार-बार अवर्गीकृत शेष से न्यूनतम तत्व का चयन करता है और इसे सामने रखता है, जिसके लिए पूरे इनपुट तक पहुँच की आवश्यकता होती है; इस प्रकार यह एक ऑफ़लाइन [[कलन विधि|एल्गोरिथम]] है। दूसरी ओर, सम्मिलन क्रम प्रति पुनरावृत्ति एक इनपुट तत्व पर विचार करता है और भविष्य के तत्वों पर विचार किए बिना आंशिक समाधान उत्पन्न करता है। इस प्रकार सम्मिलन छँटाई एक ऑनलाइन एल्गोरिथम है। | ||
ध्यान दें कि सम्मिलन प्रकार का अंतिम परिणाम सर्वोत्कृष्ट है, अर्थात, सही संरचना से क्रमबद्ध सूची। कई समस्याओं के लिए, ऑनलाइन एल्गोरिथम ऑफ़लाइन एल्गोरिथम के प्रदर्शन के समान नहीं हो सकता हैं। यदि एक ऑनलाइन एल्गोरिथम और एक सर्वोत्कृष्ट ऑफ़लाइन एल्गोरिथम के प्रदर्शन के बीच का अनुपात सीमित है, तो ऑनलाइन एल्गोरिथम को प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिथम) कहा जाता है।<ref name=karp92>{{cite journal|last1=Karp|first1=Richard M.|title=ऑन-लाइन एल्गोरिदम बनाम ऑफ-लाइन एल्गोरिदम: भविष्य जानने के लिए कितना लायक है?|journal=IFIP Congress (1)|date=1992|volume=12|pages=416–429|url=http://www.icsi.berkeley.edu/pubs/techreports/TR-92-044.pdf|access-date=17 August 2015}}</ref> | |||
प्रत्येक ऑफ़लाइन एल्गोरिथम का एक कुशल ऑनलाइन प्रतिरूप नहीं होता है। | प्रत्येक ऑफ़लाइन एल्गोरिथम का एक कुशल ऑनलाइन प्रतिरूप नहीं होता है। | ||
== परिभाषा == | == परिभाषा == | ||
क्योंकि यह पूरे इनपुट को नहीं जानता है, एक ऑनलाइन | क्योंकि यह पूरे इनपुट को नहीं जानता है, एक ऑनलाइन एल्गोरिथम निर्णय लेने के लिए मजबूर होता है जो बाद में इष्टतम नहीं हो सकता है, और ऑनलाइन एल्गोरिथम के अध्ययन ने निर्णय लेने की गुणवत्ता पर ध्यान केंद्रित किया है जो इस सेटिंग में संभव है। प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिथम) समान समस्या उदाहरण के लिए एक ऑनलाइन और ऑफलाइन एल्गोरिथम के सापेक्ष प्रदर्शन की तुलना करके इस विचार को औपचारिक रूप देता है। विशेष रूप से, एक एल्गोरिथम का प्रतिस्पर्धी अनुपात, इसकी लागत के सबसे खराब-मामले के अनुपात के रूप में परिभाषित किया गया है, जो सभी संभावित इनपुट पर इष्टतम लागत से विभाजित है। एक ऑनलाइन समस्या का प्रतिस्पर्धी अनुपात एक ऑनलाइन एल्गोरिथम द्वारा प्राप्त सर्वोत्तम प्रतिस्पर्धी अनुपात है। सहज रूप से, एक एल्गोरिथम का प्रतिस्पर्धी अनुपात इस एल्गोरिथम द्वारा उत्पादित समाधानों की गुणवत्ता पर एक माप देता है, जबकि किसी समस्या का प्रतिस्पर्धी अनुपात इस समस्या के भविष्य को जानने के महत्व को दर्शाता है। | ||
=== अन्य व्याख्याएं === | === अन्य व्याख्याएं === | ||
एल्गोरिथम के ऑनलाइन इनपुट पर अन्य दृष्टिकोणों के लिए, देखें | |||
* [[स्ट्रीमिंग एल्गोरिदम]]: पिछले इनपुट का सटीक रूप से प्रतिनिधित्व करने के लिए आवश्यक मेमोरी की मात्रा पर ध्यान केंद्रित करना; | * [[स्ट्रीमिंग एल्गोरिदम|स्ट्रीमिंग एल्गोरिथम]]: पिछले इनपुट का सटीक रूप से प्रतिनिधित्व करने के लिए आवश्यक मेमोरी की मात्रा पर ध्यान केंद्रित करना; | ||
* [[गतिशील एल्गोरिदम]]: ऑनलाइन इनपुट के साथ समस्याओं के समाधान को बनाए रखने की समय जटिलता पर ध्यान केंद्रित करना। | * [[गतिशील एल्गोरिदम|गतिशील एल्गोरिथम]]: ऑनलाइन इनपुट के साथ समस्याओं के समाधान को बनाए रखने की समय जटिलता पर ध्यान केंद्रित करना। | ||
=== उदाहरण === | === उदाहरण === | ||
कुछ ऑनलाइन | कुछ ऑनलाइन एल्गोरिथम: | ||
*सम्मिलन सॉर्ट | *सम्मिलन सॉर्ट | ||
* [[परसेप्ट्रॉन]] | * [[परसेप्ट्रॉन]] | ||
*जलाशय नमूनाकरण | *जलाशय नमूनाकरण | ||
<!-- check: --> | <!-- check: --> | ||
* [[लालची एल्गोरिदम]] | * [[लालची एल्गोरिदम|लालची एल्गोरिथम]] | ||
* प्रतिकूल (ऑनलाइन एल्गोरिथम) | * प्रतिकूल (ऑनलाइन एल्गोरिथम) | ||
* [[मीट्रिक कार्य प्रणाली]] | * [[मीट्रिक कार्य प्रणाली]] | ||
* [[ऑड्स एल्गोरिथम]] | * [[ऑड्स एल्गोरिथम]] | ||
* पृष्ठ प्रतिस्थापन | * पृष्ठ प्रतिस्थापन एल्गोरिथम | ||
* [[विचरण की गणना के लिए एल्गोरिदम]] | * [[विचरण की गणना के लिए एल्गोरिदम|विचरण की गणना के लिए एल्गोरिथम]] | ||
* उकोनेन का | * उकोनेन का एल्गोरिथम | ||
== ऑनलाइन समस्याएं == | == ऑनलाइन समस्याएं == | ||
ऑनलाइन एल्गोरिथम की अवधारणाओं को उदाहरण देने वाली एक समस्या [[कनाडाई यात्री समस्या]] है। इस समस्या का लक्ष्य एक भारित ग्राफ़ में लक्ष्य तक पहुँचने की लागत को कम करना है जहाँ कुछ किनारे अविश्वसनीय हैं और ग्राफ़ से हटा दिए गए हैं। हालांकि, एक किनारे को हटा दिया गया है (विफल) केवल यात्री को पता चलता है जब वह किनारे के अंत बिंदुओं में से एक तक पहुंचता है। इस समस्या के लिए सबसे खराब स्थिति बस यह है कि सभी अविश्वसनीय किनारे विफल हो जाते हैं और समस्या सामान्य शॉर्टेस्ट पाथ समस्या में कम हो जाती है। प्रतिस्पर्धी विश्लेषण की मदद से समस्या का वैकल्पिक विश्लेषण किया जा सकता है। विश्लेषण की इस पद्धति के लिए, ऑफ़लाइन | ऑनलाइन एल्गोरिथम की अवधारणाओं को उदाहरण देने वाली एक समस्या [[कनाडाई यात्री समस्या]] है। इस समस्या का लक्ष्य एक भारित ग्राफ़ में लक्ष्य तक पहुँचने की लागत को कम करना है जहाँ कुछ किनारे अविश्वसनीय हैं और ग्राफ़ से हटा दिए गए हैं। हालांकि, एक किनारे को हटा दिया गया है (विफल) केवल यात्री को पता चलता है जब वह किनारे के अंत बिंदुओं में से एक तक पहुंचता है। इस समस्या के लिए सबसे खराब स्थिति बस यह है कि सभी अविश्वसनीय किनारे विफल हो जाते हैं और समस्या सामान्य शॉर्टेस्ट पाथ समस्या में कम हो जाती है। प्रतिस्पर्धी विश्लेषण की मदद से समस्या का वैकल्पिक विश्लेषण किया जा सकता है। विश्लेषण की इस पद्धति के लिए, ऑफ़लाइन एल्गोरिथम पहले से जानता है कि कौन से किनारे विफल होंगे और लक्ष्य ऑनलाइन और ऑफ़लाइन एल्गोरिथम के प्रदर्शन के बीच के अनुपात को कम करना है। यह समस्या पीएसपीएसीई-पूर्ण है। | ||
कई औपचारिक समस्याएं हैं जो समाधान के रूप में एक से अधिक ऑनलाइन एल्गोरिथम प्रदान करती हैं: | कई औपचारिक समस्याएं हैं जो समाधान के रूप में एक से अधिक ऑनलाइन एल्गोरिथम प्रदान करती हैं: | ||
| Line 47: | Line 48: | ||
== यह भी देखें == | == यह भी देखें == | ||
* गतिशील | * गतिशील एल्गोरिथम | ||
* [[पैगंबर असमानता]] | * [[पैगंबर असमानता]] | ||
* [[रीयल-टाइम कंप्यूटिंग]] | * [[रीयल-टाइम कंप्यूटिंग]] | ||
* स्ट्रीमिंग | * स्ट्रीमिंग एल्गोरिथम | ||
* [[अनुक्रमिक एल्गोरिदम]] | * [[अनुक्रमिक एल्गोरिदम|अनुक्रमिक एल्गोरिथम]] | ||
* [[ऑनलाइन मशीन लर्निंग]]/ऑफलाइन लर्निंग | * [[ऑनलाइन मशीन लर्निंग]]/ऑफलाइन लर्निंग | ||
Revision as of 13:12, 19 December 2022
संगणक विज्ञान में, एक ऑनलाइन एल्गोरिथम[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.
