शून्य-राशि गेम के रूप में यादृच्छिक एल्गोरिदम

यादृच्छिक एल्गोरिदम ऐसे एल्गोरिदम हैं जो अपने तर्क के हिस्से के रूप में यादृच्छिकता की एक डिग्री को नियोजित करते हैं। इन एल्गोरिदम का उपयोग उन समस्याओं के लिए अच्छे औसत केस जटिलता|औसत-केस परिणाम (जटिलता-वार) देने के लिए किया जा सकता है, जिन्हें नियतात्मक रूप से हल करना कठिन है, या खराब सबसे खराब स्थिति वाली जटिलता प्रदर्शित करते हैं। एक एल्गोरिथम खेल सिद्धांत दृष्टिकोण यह समझाने में मदद कर सकता है कि औसत मामले में यादृच्छिक एल्गोरिदम नियतात्मक एल्गोरिदम से बेहतर क्यों काम कर सकते हैं।

खेल को औपचारिक बनाना

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

लेकिन वास्तविक दुनिया में, इनपुट आमतौर पर किसी 'दुष्ट प्रतिद्वंद्वी' द्वारा नहीं चुने जाते हैं - बल्कि, वे इनपुट पर कुछ वितरण से आते हैं। चूँकि यह मामला है, यदि हम एल्गोरिदम को कुछ वितरण से भी तैयार करने की अनुमति देते हैं, तो हम खेल को एक ऐसे खेल के रूप में देख सकते हैं जो मिश्रित रणनीति की अनुमति देता है। अर्थात्, प्रत्येक खिलाड़ी अपनी रणनीतियों के स्थान पर वितरण चुनता है।

विश्लेषण

खेल में मिश्रित रणनीतियों को शामिल करने से हमें जॉन वॉन न्यूमैन|वॉन न्यूमैन के अल्पमहिष्ठ प्रमेय का उपयोग करने की अनुमति मिलती है:

$\min _{R}\max _{D}T(A,D)=\max _{D}\min _{A}T(A,D)\,$

जहां आर एल्गोरिदम पर एक वितरण है, डी इनपुट पर एक वितरण है, ए एक एकल नियतात्मक एल्गोरिदम है, और टी (ए, डी) इनपुट डी पर एल्गोरिदम ए का औसत चलने का समय है। अधिक विशेष रूप से:

$T(A,D)=\,{\underset {x\sim D}{\operatorname {E} }}[T(A,X)].\,$

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

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

श्रेणी:असहयोगी खेल श्रेणी:यादृच्छिक एल्गोरिदम