प्रतिस्पर्धी विश्लेषण (ऑनलाइन एल्गोरिदम)

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

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

प्रतिस्पर्धी विश्लेषण में, कोई ऐसे प्रतिद्वंद्वी की कल्पना करता है जो अध्ययन किए जा रहे एल्गोरिदम की सामान्यतः और कुछ इष्टतम एल्गोरिदम के अनुपात को अधिकतम करने के लिए साभिप्राय कठिन डेटा चुनता है। इस प्रकार यादृच्छिक एल्गोरिदम पर विचार करते समय, किसी को असावधान प्रतिद्वंद्वी के बीच अंतर करना चाहिए, जिसे इसके विरुद्ध स्थिति एल्गोरिदम द्वारा किए गए यादृच्छिक विकल्पों का कोई ज्ञान नहीं है, और अनुकूली प्रतिद्वंद्वी जिसे एल्गोरिदम का पूरा ज्ञान है इसके निष्पादन के समय किसी भी बिंदु पर आंतरिक स्थिति होती है। (एक नियतात्मक एल्गोरिदम के लिए, कोई अंतर नहीं है; कोई भी प्रतिद्वंद्वी बस यह गणना कर सकता है कि भविष्य में किसी भी समय उस एल्गोरिदम की क्या स्थिति होनी चाहिए, और तदनुसार कठिन डेटा चुन सकता है।)

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

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

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

यह भी देखें

• प्रतिद्वंद्वी (ऑनलाइन एल्गोरिदम)
• परिशोधन विश्लेषण
• K-सर्वर समस्या
• सूची अद्यतन समस्या
• ऑनलाइन एल्गोरिदम

संदर्भ

• Sleator, D.; Tarjan, R. (1985), "Amortized efficiency of list update and paging rules", Communications of the ACM, 28 (2): 202–208, doi:10.1145/2786.2793.
• Aspnes, James (1998), "Competitive analysis of distributed algorithms", in Fiat, A.; Woeginger, G. J. (eds.), Online Algorithms: The State of the Art, Lecture Notes in Computer Science, vol. 1442, pp. 118–146, doi:10.1007/BFb0029567.
• Borodin, A.; El-Yaniv, R. (1998), Online Computation and Competitive Analysis, Cambridge University Press, ISBN 0-521-56392-5.
• Awerbuch, B.; Kutten, S.; Peleg, D. (1992), "Competitive Distributed Job Scheduling", ACM STOC, Victoria, BC, Canada.