Randomized rounding
कंप्यूटर विज्ञान और संचालन अनुसंधान में, रैंडमाइज्ड राउंडिंग सन्निकटन एल्गोरिदम को डिजाइन और विश्लेषण करने के लिए एक व्यापक रूप से उपयोग किया जाने वाला दृष्टिकोण है। कई संयोजी अनुकूलन समस्याएं ठीक से (इष्टतमता के लिए) हल करने के लिए कम्प्यूटेशनल रूप से कठिन हैं। ऐसी समस्याओं के लिए, यादृच्छिक गोल का उपयोग तेज (बहुपद समय) सन्निकटन एल्गोरिदम को डिजाइन करने के लिए किया जा सकता है-यानी, एल्गोरिदम जो किसी भी इनपुट को देखते हुए लगभग इष्टतम समाधान देने की गारंटी देते हैं। रैंडमाइज्ड राउंडिंग का मूल विचार समस्या के एक इष्टतम समाधान को मूल समस्या के लगभग इष्टतम समाधान में बदलना है। परिणामी एल्गोरिथ्म का विश्लेषण आमतौर पर संभावित विधि का उपयोग करके किया जाता है। मूल दृष्टिकोण के तीन चरण हैंः एक पूर्णांक रैखिक कार्यक्रम (आईएलपी) के रूप में हल की जाने वाली समस्या को तैयार करें। आई. एल. पी. के रैखिक प्रोग्रामिंग विश्राम (एल. पी.) के लिए एक इष्टतम आंशिक समाधान की गणना करें। एल. पी. के आंशिक समाधान को आई. एल. पी. के पूर्णांक समाधान में गोल करें। (हालाँकि दृष्टिकोण को आमतौर पर रैखिक कार्यक्रमों के साथ लागू किया जाता है, लेकिन कभी-कभी अन्य प्रकार की छूट का भी उपयोग किया जाता है। उदाहरण के लिए, गोमैन और विलियमसन का सेमीडिफाइनाइट प्रोग्रामिंग-आधारित मैक्स-कट सन्निकटन एल्गोरिदम देखें।) पहले चरण में, चुनौती एक उपयुक्त पूर्णांक रैखिक कार्यक्रम का चयन करना है। रैखिक प्रोग्रामिंग के साथ परिचितता, विशेष रूप से रैखिक कार्यक्रमों और पूर्णांक रैखिक कार्यक्रमों का उपयोग करके मॉडलिंग में, आवश्यक है। कई समस्याओं के लिए, एक प्राकृतिक पूर्णांक रैखिक कार्यक्रम है जो अच्छी तरह से काम करता है, जैसे कि नीचे दिए गए सेट कवर उदाहरण में। (पूर्णांक रैखिक कार्यक्रम में एक छोटा समाकलन अंतराल होना चाहिए; वास्तव में यादृच्छिक गोल का उपयोग अक्सर समाकलन अंतराल पर सीमा साबित करने के लिए किया जाता है।) दूसरे चरण में, इष्टतम भिन्नात्मक समाधान की गणना आम तौर पर किसी भी मानक रैखिक प्रोग्रामिंग एल्गोरिथ्म का उपयोग करके बहुपद समय में की जा सकती है। तीसरे चरण में, आंशिक समाधान को एक पूर्णांक समाधान में परिवर्तित किया जाना चाहिए (और इस प्रकार मूल समस्या का समाधान)। इसे आंशिक समाधान को गोल करना कहा जाता है। परिणामी पूर्णांक समाधान की लागत (संभवतः) भिन्नात्मक समाधान की लागत से बहुत अधिक नहीं होनी चाहिए। यह सुनिश्चित करेगा कि पूर्णांक समाधान की लागत इष्टतम पूर्णांक समाधान की लागत से बहुत अधिक नहीं है। तीसरा चरण (राउंडिंग) करने के लिए उपयोग की जाने वाली मुख्य तकनीक यादृच्छिककरण का उपयोग करना है, और फिर राउंडिंग के कारण लागत में वृद्धि को बाध्य करने के लिए संभावित तर्कों का उपयोग करना है (संयोजन से संभावित विधि का पालन करना)। इसमें, संभावित तर्कों का उपयोग वांछित गुणों के साथ असतत संरचनाओं के अस्तित्व को दिखाने के लिए किया जाता है। इस संदर्भ में, निम्नलिखित को दिखाने के लिए इस तरह के तर्कों का उपयोग किया जाता हैः एल. पी. के किसी भी आंशिक समाधान को देखते हुए, सकारात्मक संभावना के साथ यादृच्छिक गोल प्रक्रिया एक पूर्णांक समाधान उत्पन्न करती है जो कुछ वांछित मानदंडों के अनुसार अनुमानित होती है। अंत में, तीसरे चरण को कम्प्यूटेशनल रूप से कुशल बनाने के लिए, एक या तो उच्च संभावना के साथ अनुमानित दिखाता है (ताकि चरण यादृच्छिक रह सके) या एक गोल चरण को विकृत कर देता है, आमतौर पर सशर्त संभावनाओं की विधि का उपयोग करते हुए। बाद की विधि यादृच्छिक गोल प्रक्रिया को एक कुशल नियतात्मक प्रक्रिया में परिवर्तित करती है जो एक अच्छे परिणाम तक पहुंचने की गारंटी है। उदाहरण के लिएः सेट कवर समस्या निम्नलिखित उदाहरण से पता चलता है कि सेट कवर समस्या के लिए एक सन्निकटन एल्गोरिथ्म तैयार करने के लिए यादृच्छिक गोल का उपयोग कैसे किया जा सकता है। एक ब्रह्मांड पर सेट कवर के किसी भी उदाहरण को ठीक करें। भिन्न समाधान की गणना चरण 1 के लिए, मान लीजिए कि आई. पी. इस उदाहरण के लिए सेट कवर के लिए मानक पूर्णांक रैखिक कार्यक्रम है। चरण 2 के लिए, LP को IP का रैखिक प्रोग्रामिंग विश्राम होने दें, और किसी भी मानक रैखिक प्रोग्रामिंग एल्गोरिथ्म का उपयोग करके LP के लिए एक इष्टतम समाधान की गणना करें। यह इनपुट आकार में बहुपद में समय लेता है। एलपी के लिए व्यवहार्य समाधान वेक्टर हैं जो प्रत्येक सेट को एक गैर-नकारात्मक वजन प्रदान करते हैं, जैसे कि, प्रत्येक तत्व के लिए, कवर-- कम से कम 1 वाले सेट को सौंपा गया कुल वजन, यानी, इष्टतम समाधान एक व्यवहार्य समाधान है जिसकी लागत यथासंभव कम है। ध्यान दें कि किसी भी सेट कवर के लिए एक व्यवहार्य समाधान देता है (जहां के लिए, अन्यथा)। इसकी लागत लागत के बराबर है, यानी, दूसरे शब्दों में, रैखिक कार्यक्रम एल. पी. दिए गए सेट-कवर समस्या की छूट है। चूंकि एल. पी. के लिए व्यवहार्य समाधानों में न्यूनतम लागत है, इसलिए लागत इष्टतम सेट कवर की लागत पर कम सीमा है। यादृच्छिक राउंडिंग चरण चरण 3 में, हमें न्यूनतम-लागत आंशिक सेट कवर को एक व्यवहार्य पूर्णांक समाधान (एक वास्तविक सेट कवर के अनुरूप) में बदलना चाहिए। गोल करने के चरण में, सकारात्मक संभावना के साथ, लागत की लागत के एक छोटे से कारक के भीतर लागत होनी चाहिए। फिर (चूंकि लागत इष्टतम सेट कवर की लागत पर कम सीमा है), लागत इष्टतम लागत के एक छोटे से कारक के भीतर होगी। एक प्रारंभिक बिंदु के रूप में, सबसे प्राकृतिक गोल योजना पर विचार करेंः बारी-बारी से प्रत्येक सेट के लिए, संभावना के साथ लें, अन्यथा लें। इस राउंडिंग योजना के साथ, चुने गए सेटों की अपेक्षित लागत अधिक से अधिक, आंशिक कवर की लागत है। यह अच्छी बात है। दुर्भाग्य से कवरेज अच्छा नहीं है। जब चर छोटे होते हैं, तो एक तत्व के शामिल नहीं होने की संभावना लगभग होती है इसलिए केवल तत्वों का एक स्थिर अंश अपेक्षा में शामिल किया जाएगा। प्रत्येक तत्व को उच्च संभावना के साथ कवर करने के लिए, मानक राउंडिंग योजना पहले एक उपयुक्त कारक द्वारा राउंडिंग संभावनाओं को बढ़ाती है। यहाँ मानक राउंडिंग योजना हैः एक पैरामीटर ठीक करें। बारी-बारी से प्रत्येक सेट के लिए, संभावना के साथ लें, अन्यथा लें। संभावनाओं को बढ़ाना अपेक्षित लागत को बढ़ाता है, लेकिन सभी तत्वों के कवरेज की संभावना बनाता है। विचार यह है कि जितना संभव हो उतना छोटा चुना जाए ताकि सभी तत्वों को गैर-शून्य संभावना के साथ कवर किया जा सके। यहाँ एक विस्तृत विश्लेषण है। लेम्मा (गोल योजना के लिए सन्निकटन गारंटी) ठीक करें। सकारात्मक संभावना के साथ, राउंडिंग योजना अधिक से अधिक लागत का एक सेट कवर प्रदान करती है (और इस प्रकार लागत इष्टतम सेट कवर की लागत से गुणा होती है)। (नोटः सावधानी से इसे कम किया जा सकता है।) सबूत यादृच्छिक गोल योजना के उत्पादन में वांछित गुण होते हैं जब तक कि निम्नलिखित "खराब" घटनाओं में से कोई भी नहीं होती हैः अधिक की लागत, या कुछ तत्व के लिए, कवर करने में विफल रहता है। प्रत्येक की अपेक्षा अधिक से अधिक है। अपेक्षा की रैखिकता से, अपेक्षा अधिक से अधिक होती है। इस प्रकार, मार्कोव की असमानता से, उपरोक्त पहली बुरी घटना की संभावना अधिक से अधिक है। शेष खराब घटनाओं के लिए (प्रत्येक तत्व के लिए एक), ध्यान दें कि, क्योंकि किसी भी दिए गए तत्व के लिए, संभावना जो शामिल नहीं है (यह असमानता का उपयोग करता है, जो इसके लिए सख्त है।) इस प्रकार, प्रत्येक तत्व के लिए, तत्व के शामिल नहीं होने की संभावना कम है। संघ बाध्य द्वारा, बुरी घटनाओं में से एक होने की संभावना कम है। इस प्रकार, सकारात्मक संभावना के साथ कोई बुरी घटना नहीं होती है और यह अधिक से अधिक लागत का एक सेट कवर है। सशर्त संभावनाओं की विधि का उपयोग करते हुए क्यू. ई. डी. अवमूल्यन ऊपर दिया गया संकेत लागत के एक सेट कवर के अस्तित्व को दर्शाता है)। इस संदर्भ में हमारा लक्ष्य एक कुशल सन्निकटन एल्गोरिथ्म है, न कि केवल एक अस्तित्व प्रमाण, इसलिए हम पूरा नहीं कर पाए हैं। एक तरीका यह होगा कि थोड़ा बढ़ाएँ, फिर दिखाएँ कि सफलता की संभावना कम से कम 1/4 है। इस संशोधन के साथ, यादृच्छिक गोल चरण को कुछ बार दोहराना उच्च संभावना के साथ एक सफल परिणाम सुनिश्चित करने के लिए पर्याप्त है। यह दृष्टिकोण सन्निकटन अनुपात को कमजोर कर देता है। इसके बाद हम एक अलग दृष्टिकोण का वर्णन करते हैं जो एक निर्धारक एल्गोरिथ्म प्रदान करता है जो उपरोक्त अस्तित्व प्रमाण के सन्निकटन अनुपात से मेल खाने की गारंटी देता है। इस दृष्टिकोण को सशर्त संभावनाओं की विधि कहा जाता है। निर्धारक एल्गोरिथ्म यादृच्छिक गोल योजना का अनुकरण करता हैः यह बारी-बारी से प्रत्येक सेट पर विचार करता है, और चुनता है। लेकिन प्रत्येक विकल्प को यादृच्छिक रूप से आधार बनाने के बजाय, यह निर्णयात्मक रूप से विकल्प बनाता है, ताकि विफलता की सशर्त संभावना को, अब तक के विकल्पों को देखते हुए, 1 से नीचे रखा जा सके। विफलता की सशर्त संभावना को सीमित करना हम प्रत्येक चर को बारी-बारी से निर्धारित करने में सक्षम होना चाहते हैं ताकि विफलता की सशर्त संभावना को 1 से नीचे रखा जा सके। ऐसा करने के लिए, हमें विफलता की सशर्त संभावना पर एक अच्छी सीमा की आवश्यकता है। मूल अस्तित्व प्रमाण को परिष्कृत करके सीमा आ जाएगी। यह प्रमाण स्पष्ट रूप से यादृच्छिक चर की अपेक्षा से विफलता की संभावना को सीमित करता है, जहां अंत में उजागर किए गए तत्वों का समूह है। यादृच्छिक चर थोड़ा रहस्यमय लग सकता है, लेकिन यह एक व्यवस्थित तरीके से संभावित प्रमाण को प्रतिबिंबित करता है। पहला कार्यकाल पहली बुरी घटना (लागत बहुत अधिक है) की संभावना को सीमित करने के लिए मार्कोव की असमानता को लागू करने से आता है। यदि लागत बहुत अधिक है तो यह कम से कम 1 का योगदान देता है। दूसरा पद दूसरे प्रकार की बुरी घटनाओं (उजागर तत्वों) की संख्या को गिनता है। यदि कोई तत्व खुला छोड़ देता है तो यह कम से कम 1 का योगदान देता है। इस प्रकार, किसी भी परिणाम में जहां 1 से कम है, सभी तत्वों को शामिल करना चाहिए और लीम्मा से वांछित सीमा को पूरा करने वाली लागत होनी चाहिए। संक्षेप में, यदि राउंडिंग चरण विफल हो जाता है, तो। इसका तात्पर्य है (मार्कोव की असमानता से) जो विफलता की संभावना पर एक ऊपरी सीमा है। ध्यान दें कि उपरोक्त तर्क पहले से ही लेम्मा के प्रमाण में निहित है, जो गणना से यह भी दर्शाता है। सशर्त संभावनाओं की विधि को लागू करने के लिए, हमें गोल चरण के आगे बढ़ने के साथ विफलता की सशर्त संभावना को बाध्य करने के लिए तर्क का विस्तार करने की आवश्यकता है। आमतौर पर, यह एक व्यवस्थित तरीके से किया जा सकता है, हालांकि यह तकनीकी रूप से थकाऊ हो सकता है। तो, विफलता की सशर्त संभावना के बारे में क्या क्योंकि गोल चरण सेट के माध्यम से दोहराता है? चूंकि किसी भी परिणाम में जहां मार्कोव की असमानता के कारण गोल चरण विफल हो जाता है, विफलता की सशर्त संभावना अधिक से अधिक की सशर्त अपेक्षा होती है। इसके बाद हम की सशर्त अपेक्षा की गणना करते हैं, जैसा कि हमने मूल प्रमाण में की बिना शर्त अपेक्षा की गणना की थी। कुछ पुनरावृत्ति के अंत में गोल करने की प्रक्रिया की स्थिति पर विचार करें। आइए अब तक विचार किए गए सेटों को दर्शाते हैं (पहले सेट में)। आइए (आंशिक रूप से निर्दिष्ट) वेक्टर को निरूपित करें (इसलिए केवल यदि निर्धारित किया जाता है)। प्रत्येक समूह के लिए, आइए उस संभावना को दर्शाते हैं जिसके साथ 1 पर सेट किया जाएगा। आइए उन तत्वों को शामिल करें जो अभी तक ढके नहीं हैं। फिर, अब तक किए गए विकल्पों को देखते हुए, जो सशर्त अपेक्षा दी गई है, वह नोट है जो पुनरावृत्ति के बाद ही निर्धारित की जाती है। विफलता की सशर्त संभावना को 1 से नीचे रखना विफलता की सशर्त संभावना को 1 से नीचे रखने के लिए, 1 से नीचे की सशर्त अपेक्षा रखने के लिए पर्याप्त है। ऐसा करने के लिए, यह बढ़ने की सशर्त अपेक्षा को बनाए रखने के लिए पर्याप्त है। एल्गोरिथ्म यही करेगा। यह सुनिश्चित करने के लिए प्रत्येक पुनरावृत्ति में सेट किया जाएगा कि (कहाँ)। th पुनरावृत्ति में, यह सुनिश्चित करने के लिए एल्गोरिथ्म कैसे सेट किया जा सकता है? यह पता चला है कि यह बस सेट कर सकता है ताकि इसके परिणामी मूल्य को कम से कम किया जा सके। यह देखने के लिए कि क्यों, उस समय पर ध्यान केंद्रित करें जब पुनरावृत्ति शुरू होती है। उस समय, निर्धारित किया जाता है, लेकिन अभी तक निर्धारित नहीं किया गया है---यह दो संभावित मान ले सकता है जो इस बात पर निर्भर करता है कि पुनरावृत्ति में कैसे सेट किया जाता है। के मान को दर्शाते हैं। मान लीजिए और, के दो संभावित मानों को दर्शाते हैं, जो इस बात पर निर्भर करता है कि क्या क्रमशः 0 या 1 पर सेट किया गया है। सशर्त अपेक्षा की परिभाषा के अनुसार, चूंकि दो मात्राओं का भारित औसत हमेशा उन दो मात्राओं में से कम से कम न्यूनतम होता है, इसलिए यह इस बात की गारंटी देता है कि इसके परिणामी मूल्य को कम करने के लिए इस तरह से निर्धारित किया जाए। एल्गोरिथ्म यही करेगा। विस्तार से, इसका क्या अर्थ है? एक फलन के रूप में माना जाता है (अन्य सभी मात्राओं के साथ निश्चित) एक रैखिक फलन है, और उस फलन में गुणांक है इस प्रकार, एल्गोरिथ्म को 0 पर सेट करना चाहिए यदि यह अभिव्यक्ति सकारात्मक है, और अन्यथा 1। यह निम्नलिखित एल्गोरिथ्म देता है। सेट कवर इनपुट के लिए यादृच्छिक-गोल एल्गोरिदमः सेट सिस्टम, ब्रह्मांड, लागत वेक्टर आउटपुटः सेट कवर (सेट कवर के लिए मानक पूर्णांक रैखिक कार्यक्रम का एक समाधान) एक न्यूनतम-लागत आंशिक सेट कवर की गणना करें (एलपी छूट के लिए एक इष्टतम समाधान)। जाने दीजिए। हर एक के लिए छोड़ दें। प्रत्येक के लिएः चलो। (इसमें अभी तक निर्धारित नहीं किए गए सेट शामिल हैं।) यदि फिर सेट किया जाता है, तो और सेट करें। (इसमें अभी तक न ढके हुए तत्व शामिल हैं।) वापस लौटें। लेम्मा (एल्गोरिथम के लिए सन्निकटन गारंटी) उपरोक्त एल्गोरिथ्म किसी भी (आंशिक) सेट कवर की न्यूनतम लागत के अधिकांश समय पर लागत का एक सेट कवर देता है। प्रमाण एल्गोरिथ्म यह सुनिश्चित करता है कि, की सशर्त अपेक्षा प्रत्येक पुनरावृत्ति पर नहीं बढ़ती है। चूँकि यह सशर्त अपेक्षा शुरू में 1 से कम है (जैसा कि पहले दिखाया गया है), एल्गोरिथ्म यह सुनिश्चित करता है कि सशर्त अपेक्षा 1 से कम रहे। चूँकि विफलता की सशर्त संभावना अधिक से अधिक सशर्त अपेक्षा है, इस तरह एल्गोरिथ्म यह सुनिश्चित करता है कि विफलता की सशर्त संभावना 1 से कम रहे। इस प्रकार, अंत में, जब सभी विकल्प निर्धारित किए जाते हैं, तो एल्गोरिथ्म एक सफल परिणाम तक पहुँचता है। अर्थात्, उपरोक्त एल्गोरिथ्म किसी भी (आंशिक) सेट कवर की न्यूनतम लागत के अधिकांश समय पर लागत का एक सेट कवर देता है। टिप्पणी उपरोक्त उदाहरण में, एल्गोरिथ्म को यादृच्छिक चर की सशर्त अपेक्षा द्वारा निर्देशित किया गया था। कुछ मामलों में, एक सटीक सशर्त अपेक्षा के बजाय, कुछ सशर्त अपेक्षा पर एक ऊपरी सीमा (या कभी-कभी एक निचली सीमा) का उपयोग किया जाता है। इसे निराशावादी अनुमानक कहा जाता है। संभावित विधि के अन्य अनुप्रयोगों के साथ तुलना यादृच्छिक गोल चरण दो मामलों में संभावित विधि के अधिकांश अनुप्रयोगों से अलग हैः गोल चरण की कम्प्यूटेशनल जटिलता महत्वपूर्ण है। इसे उपवास द्वारा लागू किया जाना चाहिए (जैसे। बहुपद समय) एल्गोरिथ्म। यादृच्छिक प्रयोग में अंतर्निहित संभाव्यता वितरण समस्या उदाहरण के विश्राम के समाधान का एक कार्य है। यह तथ्य सन्निकटन एल्गोरिथ्म की प्रदर्शन गारंटी को साबित करने के लिए महत्वपूर्ण है---अर्थात, किसी भी समस्या के उदाहरण के लिए, एल्गोरिथ्म एक समाधान देता है जो उस विशिष्ट उदाहरण के लिए इष्टतम समाधान का अनुमान लगाता है। इसकी तुलना में, संयोजन विज्ञान में संभावित विधि के अनुप्रयोग आम तौर पर संरचनाओं के अस्तित्व को दर्शाते हैं जिनकी विशेषताएं इनपुट के अन्य मापदंडों पर निर्भर करती हैं। उदाहरण के लिए, तुरान के प्रमेय पर विचार करें, जिसे "औसत डिग्री के शीर्ष वाले किसी भी ग्राफ में कम से कम आकार का एक स्वतंत्र सेट होना चाहिए। (तुरान के प्रमेय के संभावित प्रमाण के लिए इसे देखें।) जबकि ऐसे ग्राफ हैं जिनके लिए यह सीमा तंग है, ऐसे ग्राफ भी हैं जिनके स्वतंत्र सेट उससे बहुत बड़े हैं। इस प्रकार, एक ग्राफ में तुरान के प्रमेय द्वारा मौजूद स्वतंत्र सेट का आकार, सामान्य रूप से, उस ग्राफ के लिए अधिकतम स्वतंत्र सेट की तुलना में बहुत छोटा हो सकता है। रैखिक कार्यक्रम को हल किए बिना सशर्त संभावनाओं यादृच्छिक गोल करने की विधि भी देखें। संदर्भ। आगे पढ़ने के लिए एल्गोरिदम संभावित तर्क