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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

• 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.