स्मूथ्द एनालिसिस: Difference between revisions

Latest revision as of 14:55, 6 September 2023

व्यवस्थित रूप से उत्पन्न बिटमैप सामान्य चित्रों जैसा नहीं होता है।

एक सामान्य चित्र किसी रैंडम बिटमैप जैसा नहीं होता.

सैद्धांतिक कंप्यूटर विज्ञान में, स्मूथ्द एनालिसिस एल्गोरिदम के एनालिसिस को मापने की एक विधि है। 2001 में इसके प्रारंभ होने के बाद से, गणितीय प्रोग्रामिंग, नुमेरिकल एनालिसिस, मशीन लर्निंग और डेटा माइनिंग से लेकर समस्याओं के लिए स्मूथ्द एनालिसिस का उपयोग अधिक शोध के आधार के रूप में किया गया है।^[1] यह वर्स्ट केस या औसत-स्थिति परिदृश्यों का उपयोग करने वाले एनालिसिस की तुलना में एल्गोरिदम के व्यावहारिक प्रदर्शन (उदाहरण के लिए, रनिंग टाइम, सक्सेस रेट, अप्प्रोक्सिमेसन क्वालिटी) का अधिक यथार्थवादी एनालिसिस दे सकता है।

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

यद्यपि वर्स्ट केस एनालिसिस कई एल्गोरिदम के व्यावहारिक प्रदर्शन को समझाने में व्यापक रूप से सफल रहा है, एनालिसिस की यह शैली कई समस्याओं के लिए मिसलीडिंग परिणाम देती है। वर्स्ट केस कोम्प्लेक्ससिटी किसी भी इनपुट को हल करने में लगने वाले समय को मापती है, चूँकि हल करने में कठिन इनपुट अभ्यास में कभी नहीं आ सकते हैं। ऐसे स्थितियों में, वर्स्ट केस रनिंग टाइम अभ्यास में ओब्सेर्वे रनिंग टाइम कहीं अधिक वोर्स हो सकता है। उदाहरण के लिए, सिम्प्लेक्स एल्गोरिथ्म का उपयोग करके एक लीनियर प्रोग्राम को हल करने की वर्स्ट केस कोम्प्लेक्ससिटी घातीय है,^[2] चूँकि अभ्यास में चरणों की देखी गई संख्या सामान्य रूप से लीनियर है।^[3]^[4] सिम्पलेक्स एल्गोरिथ्म वास्तव में अभ्यास में एल्लिप्सोइड विधि की तुलना में बहुत तेज़ है, चूँकि उत्तरार्द्ध में पालीनोमिअल टाइम की वर्स्ट केस वाली कोम्प्लेक्ससिटी है।

औसत-केस एनालिसिस सबसे पहले सबसे वर्स्ट -केस एनालिसिस की सीमाओं को दूर करने के लिए प्रस्तुत किया गया था। चूँकि, परिणामी औसत-स्थिति की कोम्प्लेक्ससिटी इनपुट पर चुने गए प्रोबब्लिटी डिस्ट्रीबुसन पर बहुत अधिक निर्भर करती है। वास्तव में वास्तविक इनपुट और इनपुट का डिस्ट्रीबुसन एनालिसिस के समय बनाई गई धारणाओं से भिन्न हो सकता है: एक रैंडम इनपुट एक विशिष्ट इनपुट से बहुत भिन्न हो सकता है। डेटा मॉडल की इस पसंद के कारण, सैद्धांतिक औसत-स्थति का परिणाम एल्गोरिदम के व्यावहारिक प्रदर्शन के बारे में बहुत कम कह सकता है।

स्मूथ्द एनालिसिस वर्स्ट केस और औसत-स्थिति एनालिसिस दोनों को सामान्यीकृत करता है और दोनों की शक्ति प्राप्त करता है। इसका उद्देश्य औसत-स्थिति की कोम्प्लेक्ससिटी से कहीं अधिक सामान्य होना है जबकि अभी भी कम कोम्प्लेक्ससिटी सीमाओं को सिद्ध करने की अनुमति है।

इतिहास

एसीएम और ईएटीसीएस ने स्मूथ्द एनालिसिस विकसित करने के लिए डेनियल स्पीलमैन और शांग ड्रा टी को 2008 गोडेल प्राइज से सम्मानित किया था। स्मूथेड एनालिसिस नाम एलन एडेलमैन द्वारा डेवलपिंग किया गया था।^[1] 2010 में स्पीलमैन को स्मूथ्द एनालिसिस विकसित करने के लिए नेवानलिन्ना प्राइज मिला। स्पीलमैन और टेंग का जेएसीएम पेपर एल्गोरिदम का स्मूथ्द एनालिसिस: सिम्प्लेक्स एल्गोरिदम सामान्यत: बहुपद समय क्यों लेता है, गणितीय प्रोग्रामिंग सोसायटी (एमपीएस) और अमेरिकन गणितीय सोसाइटी (एएमएस) द्वारा संयुक्त रूप से प्रायोजित 2009 फुलकर्सन प्राइज के तीन विजेताओं में से एक था।

उदाहरण

लीनियर प्रोग्रामिंग के लिए सिंप्लेक्स एल्गोरिदम

सिम्प्लेक्स एल्गोरिदम अभ्यास में एक बहुत ही कुशल एल्गोरिदम है, और यह अभ्यास में लीनियर प्रोग्रामिंग के लिए प्रमुख एल्गोरिदम में से एक है। प्रायोगिक समस्याओं पर, एल्गोरिदम द्वारा उठाए गए कदमों की संख्या चर और बाधाओं की संख्या में लीनियर है।^[3]^[4] फिर भी सैद्धांतिक रूप से वर्स्ट केस में सबसे सफलतापूर्वक विश्लेषित धुरी नियमों के लिए इसमें तेजी से कई कदम उठाने पड़ते हैं। स्मूथ्द एनालिसिस विकसित करने के लिए यह मुख्य प्रेरणाओं में से एक था।^[5]

पेरटूरबाशन मॉडल के लिए, हम मानते हैं कि इनपुट डेटा गाऊसी डिस्ट्रीब्यूशन से ध्वनि से परेशान है। सामान्यीकरण उद्देश्यों के लिए, हम अप्रभावित डेटा मानते हैं ${\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n},\mathbf {c} \in \mathbb {R} ^{d}$ संतुष्ट $\|({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})\|_{2}\leq 1$ सभी पंक्तियों के लिए $({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})$ आव्यूह का $({\bar {\mathbf {A} }},{\bar {\mathbf {b} }}).$ ये ध्वनि $({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})$ माध्य के साथ गाऊसी डिस्ट्रीबुसन से नमूना की गई स्वतंत्र प्रविष्टियाँ $0$ और मानक विचलन $\sigma$ . हमने $\mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }}+{\hat {\mathbf {b} }}$ .सेट किया है जो स्मूथ्द इनपुट डेटा में लीनियर प्रोग्राम सम्मिलित होता है

अधिकतम करें

\mathbf {c^{T}} \cdot \mathbf {x}

का विषय है

\mathbf {A} \mathbf {x} \leq \mathbf {b}

.

यदि डेटा पर हमारे एल्गोरिदम का चलने का समय $\mathbf {A} ,\mathbf {b} ,\mathbf {c}$ द्वारा दिया गया है $T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )$ तो सिंप्लेक्स विधि की स्मूथ्द कोम्प्लेक्ससिटी है^[6]

C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}[T({\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},{\bar {\mathbf {b} }}+{\hat {\mathbf {b} }},\mathbf {c} )]={\rm {poly}}(d,\log n,\sigma ^{-1}).

यह सीमा एक विशिष्ट धुरी नियम के लिए है जिसे छाया शीर्ष नियम कहा जाता है। शैडो वर्टेक्स नियम सामान्यत: उपयोग किए जाने वाले धुरी नियमों जैसे कि डेंटज़िग नियम या सबसे तेज किनारे वाले नियम की तुलना में धीमा है^[7] किंतु इसमें ऐसे गुण हैं जो इसे संभाव्य एनालिसिस के लिए बहुत उपयुक्त बनाते हैं।^[8]

संयुक्त अनुकूलन के लिए कोम्बिनाटोरिअल ओप्टीमायजैसन

कई स्थानीय खोज (अनुकूलन) एल्गोरिदम का चलने का समय सबसे व्यर्थ होता है, किंतु अभ्यास में वे अच्छा प्रदर्शन करते हैं।^[9]

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

समस्या उदाहरणों का एक वर्ग बॉक्स $[0,1]^{d}$ में $n$ बिंदुओं द्वारा दिया जा सकता है, जहां उनकी युग्‍मानूसार दूरियां एक नॉर्म (गणित) से आती हैं। पहले से ही दो आयामों में, 2-ऑप्ट अनुमान स्थानीय इष्टतम खोजने तक तेजी से कई पुनरावृत्तियों को ले सकता है। इस सेटिंग में, कोई पेरटूरबाशन मॉडल का विश्लेषण कर सकता है जहां कोने $v_{1},\dots ,v_{n}$ को प्रोबब्लिटी डेंसिटी फ़ंक्शन $f_{1},\dots ,f_{n}:[0,1]^{d}\rightarrow [0,\theta ]$ के साथ युनिफोर्मिली डिस्ट्रीबुसन के अनुसार स्वतंत्र रूप से नमूना किया जाता है। $\theta =1$ के लिए, अंक समान रूप से वितरित किए गए हैं। जब $\theta >1$ बड़ा होता है, तो प्रतिद्वंद्वी के पास कठिन समस्या की संभावना को बढ़ाने की अधिक क्षमता होती है। इस पेरटूरबाशन मॉडल में, 2-ऑप्ट हेयुरिस्टिक के पुनरावृत्तियों की अपेक्षित संख्या, साथ ही परिणामी आउटपुट के अनुमानित अनुपात, $n$ और $\theta$ के बहुपद कार्यों से बंधे हैं।^[10]

एक अन्य स्थानीय खोज एल्गोरिदम जिसके लिए स्मूथ्द एनालिसिस सफल रहा वह के-मीन्स विधि है। $[0,1]^{d}$ में $n$ अंक दिए जाने पर, एक ही क्लस्टर में बिंदुओं के बीच छोटी युग्म दूरी वाले समूहों में एक अच्छा विभाजन खोजना एनपी-कठिन है। लॉयड का एल्गोरिदम व्यापक रूप से उपयोग किया जाता है और अभ्यास में बहुत तेज़ है, चूँकि यह स्थानीय रूप से इष्टतम समाधान खोजने के लिए सबसे वर्स्ट केस में पुनरावृत्तियों को ले सकता है। चूँकि यह मानते हुए कि बिंदुओं में स्वतंत्र गॉसियन डिस्ट्रीबुसन हैं, प्रत्येक की अपेक्षा $[0,1]^{d}$ और मानक विचलन $\sigma$ है, एल्गोरिदम के पुनरावृत्तियों की अपेक्षित संख्या $n$ , $d$ और $\sigma$ . में एक बहुपद से घिरी है।^[11]

यह भी देखें

एवरेज केस कॉम्पलेक्ससिटी
सूडो -पालीनोमिअल टाइम
वर्स्ट केस कॉम्पलेक्ससिटी

संदर्भ

↑ ^1.0 ^1.1 Spielman, Daniel; Teng, Shang-Hua (2009), "Smoothed analysis: an attempt to explain the behavior of algorithms in practice" (PDF), Communications of the ACM, ACM, 52 (10): 76–84, doi:10.1145/1562764.1562785
↑ Amenta, Nina; Ziegler, Günter (1999), "Deformed products and maximal shadows of polytopes", Contemporary Mathematics, American Mathematical Society, 223: 10–19, CiteSeerX 10.1.1.80.3241, doi:10.1090/conm/223, ISBN 9780821806746, MR 1661377
↑ ^3.0 ^3.1 Shamir, Ron (1987), "The Efficiency of the Simplex Method: A Survey", Management Science, 33 (3): 301–334, doi:10.1287/mnsc.33.3.301
↑ ^4.0 ^4.1 Andrei, Neculai (2004), "Andrei, Neculai. "On the complexity of MINOS package for linear programming", Studies in Informatics and Control, 13 (1): 35–46
↑ Spielman, Daniel; Teng, Shang-Hua (2001), "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time", Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM: 296–305, arXiv:cs/0111050, Bibcode:2001cs.......11050S, doi:10.1145/380752.380813, ISBN 978-1-58113-349-3
↑ Dadush, Daniel; Huiberts, Sophie (2018), "A friendly smoothed analysis of the simplex method", Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing: 390–403, arXiv:1711.05667, doi:10.1145/3188745.3188826, ISBN 9781450355599
↑ Borgwardt, Karl-Heinz; Damm, Renate; Donig, Rudolf; Joas, Gabriele (1993), "Empirical studies on the average efficiency of simplex variants under rotation symmetry", ORSA Journal on Computing, Operations Research Society of America, 5 (3): 249–260, doi:10.1287/ijoc.5.3.249
↑ Borgwardt, Karl-Heinz (1987), The Simplex Method: A Probabilistic Analysis, Algorithms and Combinatorics, vol. 1, Springer-Verlag, doi:10.1007/978-3-642-61578-8, ISBN 978-3-540-17096-9
↑ Manthey, Bodo (2021), Roughgarden, Tim (ed.), "Smoothed Analysis of Local Search", Beyond the Worst-Case Analysis of Algorithms, Cambridge: Cambridge University Press, pp. 285–308, doi:10.1017/9781108637435.018, ISBN 978-1-108-49431-1, retrieved 2022-06-15
↑ ^10.0 ^10.1 Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2007), "Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 68: 190–264, doi:10.1007/s00453-013-9801-4
↑ Arthur, David; Manthey, Bodo; Röglin, Heiko (2011), "Smoothed Analysis of the k-Means Method", Journal of the ACM, 58 (5): 1–31, doi:10.1145/2027216.2027217

[spielman-teng-2009-1] 1.0 ^1.1 Spielman, Daniel; Teng, Shang-Hua (2009), "Smoothed analysis: an attempt to explain the behavior of algorithms in practice" (PDF), Communications of the ACM, ACM, 52 (10): 76–84, doi:10.1145/1562764.1562785

[amenta-ziegler-2] Amenta, Nina; Ziegler, Günter (1999), "Deformed products and maximal shadows of polytopes", Contemporary Mathematics, American Mathematical Society, 223: 10–19, CiteSeerX 10.1.1.80.3241, doi:10.1090/conm/223, ISBN 9780821806746, MR 1661377

[shamir-3] 3.0 ^3.1 Shamir, Ron (1987), "The Efficiency of the Simplex Method: A Survey", Management Science, 33 (3): 301–334, doi:10.1287/mnsc.33.3.301

[andrei-4] 4.0 ^4.1 Andrei, Neculai (2004), "Andrei, Neculai. "On the complexity of MINOS package for linear programming", Studies in Informatics and Control, 13 (1): 35–46

[spielman-teng-2001-5] Spielman, Daniel; Teng, Shang-Hua (2001), "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time", Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM: 296–305, arXiv:cs/0111050, Bibcode:2001cs.......11050S, doi:10.1145/380752.380813, ISBN 978-1-58113-349-3

[6] Dadush, Daniel; Huiberts, Sophie (2018), "A friendly smoothed analysis of the simplex method", Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing: 390–403, arXiv:1711.05667, doi:10.1145/3188745.3188826, ISBN 9781450355599

[borgwardt-damm-donig-joas-7] Borgwardt, Karl-Heinz; Damm, Renate; Donig, Rudolf; Joas, Gabriele (1993), "Empirical studies on the average efficiency of simplex variants under rotation symmetry", ORSA Journal on Computing, Operations Research Society of America, 5 (3): 249–260, doi:10.1287/ijoc.5.3.249

[borgwardt-8] Borgwardt, Karl-Heinz (1987), The Simplex Method: A Probabilistic Analysis, Algorithms and Combinatorics, vol. 1, Springer-Verlag, doi:10.1007/978-3-642-61578-8, ISBN 978-3-540-17096-9

[9] Manthey, Bodo (2021), Roughgarden, Tim (ed.), "Smoothed Analysis of Local Search", Beyond the Worst-Case Analysis of Algorithms, Cambridge: Cambridge University Press, pp. 285–308, doi:10.1017/9781108637435.018, ISBN 978-1-108-49431-1, retrieved 2022-06-15

[engler-roeglin-voecking-10] 10.0 ^10.1 Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2007), "Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 68: 190–264, doi:10.1007/s00453-013-9801-4

[david-manthey-roeglin-11] Arthur, David; Manthey, Bodo; Röglin, Heiko (2011), "Smoothed Analysis of the k-Means Method", Journal of the ACM, 58 (5): 1–31, doi:10.1145/2027216.2027217

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
-[[File:Every pixel has a random color.png|thumb|बेतरतीब ढंग से उत्पन्न [[बिटमैप]] सामान्य चित्रों जैसा नहीं होता है।]]
+[[File:Every pixel has a random color.png|thumb|व्यवस्थित रूप से उत्पन्न [[बिटमैप]] सामान्य चित्रों जैसा नहीं होता है।]]
-[[File:Edible fungi in basket 2012 G1.jpg|thumb|एक सामान्य चित्र किसी रैंडम बिटमैप जैसा नहीं होता.]][[सैद्धांतिक कंप्यूटर विज्ञान]] में, '''स्मूथ्द एनालिसिस''' एल्गोरिदम के एनालिसिस को मापने की एक विधि है। 2001 में इसके प्रारंभ होने के बाद से, [[गणितीय प्रोग्रामिंग]], [[संख्यात्मक विश्लेषण|नुमेरिकल एनालिसिस]], [[ यंत्र अधिगम | मशीन लर्निंग]] और [[डेटा खनन|डेटा माइनिंग]]  से लेकर समस्याओं के लिए स्मूथ्द एनालिसिस का उपयोग अधिक  शोध के आधार के रूप में किया गया है।<ref name="spielman-teng-2009" /> यह वर्स्ट केस या औसत-स्थिति परिदृश्यों का उपयोग करने वाले एनालिसिस की तुलना में एल्गोरिदम के व्यावहारिक प्रदर्शन (उदाहरण के लिए, रनिंग टाइम, सक्सेस रेट, अप्प्रोक्सिमेसन क्वालिटी) का अधिक यथार्थवादी एनालिसिस दे सकता है।
+[[File:Edible fungi in basket 2012 G1.jpg|thumb|एक सामान्य चित्र किसी रैंडम बिटमैप जैसा नहीं होता.]][[सैद्धांतिक कंप्यूटर विज्ञान]] में, '''स्मूथ्द एनालिसिस''' एल्गोरिदम के एनालिसिस को मापने की एक विधि है। 2001 में इसके प्रारंभ होने के बाद से, [[गणितीय प्रोग्रामिंग]], [[संख्यात्मक विश्लेषण|नुमेरिकल एनालिसिस]], [[ यंत्र अधिगम |मशीन लर्निंग]] और [[डेटा खनन|डेटा माइनिंग]] से लेकर समस्याओं के लिए स्मूथ्द एनालिसिस का उपयोग अधिक शोध के आधार के रूप में किया गया है।<ref name="spielman-teng-2009" /> यह वर्स्ट केस या औसत-स्थिति परिदृश्यों का उपयोग करने वाले एनालिसिस की तुलना में एल्गोरिदम के व्यावहारिक प्रदर्शन (उदाहरण के लिए, रनिंग टाइम, सक्सेस रेट, अप्प्रोक्सिमेसन क्वालिटी) का अधिक यथार्थवादी एनालिसिस दे सकता है।
-स्मूथ्द एनालिसिस वर्स्ट केस और औसत-स्थिति एनालिसिस का एक मिश्रण है जो दोनों के लाभ प्राप्त करता है। यह वर्स्ट केस वाले इनपुट के समान्य रैनडम पेरटूरबाशन  के तहत एल्गोरिदम के अपेक्षित प्रदर्शन को मापता है। यदि किसी एल्गोरिदम की स्मूथ्द कोम्प्लेक्ससिटी कम है, तो यह संभावना नहीं है कि एल्गोरिदम को व्यावहारिक उदाहरणों को हल करने में लंबा समय लगेगा, जिनका डेटा सामान्य ध्वनि और अशुद्धियों के अधीन है। स्मूथ्द कोम्प्लेक्ससिटी परिणाम शसक्त संभाव्य परिणाम हैं, सामान्य रूप से यह बताते हुए कि, इनपुट के स्थान के प्रत्येक बड़े पर्याप्त निकट में, अधिकांश इनपुट आसानी से हल करने योग्य हैं। इस प्रकार, लो स्मूथ्द कोम्प्लेक्ससिटी का अर्थ है कि इनपुट की कठोरता एक ब्रिटत्ल प्रॉपर्टी है।
+स्मूथ्द एनालिसिस वर्स्ट केस और औसत-स्थिति एनालिसिस का एक मिश्रण है जो दोनों के लाभ प्राप्त करता है। यह वर्स्ट केस वाले इनपुट के समान्य रैनडम पेरटूरबाशन के तहत एल्गोरिदम के अपेक्षित प्रदर्शन को मापता है। यदि किसी एल्गोरिदम की स्मूथ्द कोम्प्लेक्ससिटी कम है, तो यह संभावना नहीं है कि एल्गोरिदम को व्यावहारिक उदाहरणों को हल करने में लंबा समय लगेगा, जिनका डेटा सामान्य ध्वनि और अशुद्धियों के अधीन है। स्मूथ्द कोम्प्लेक्ससिटी परिणाम शसक्त संभाव्य परिणाम हैं, सामान्य रूप से यह बताते हुए कि, इनपुट के स्थान के प्रत्येक बड़े पर्याप्त निकट में, अधिकांश इनपुट आसानी से हल करने योग्य हैं। इस प्रकार, लो स्मूथ्द कोम्प्लेक्ससिटी का अर्थ है कि इनपुट की कठोरता एक ब्रिटत्ल प्रॉपर्टी है।
-यद्यपि [[सबसे खराब स्थिति का विश्लेषण|वर्स्ट केस]] एनालिसिस कई एल्गोरिदम के व्यावहारिक प्रदर्शन को समझाने में व्यापक रूप से सफल रहा है, एनालिसिस की यह शैली कई समस्याओं के लिए मिसलीडिंग परिणाम देती है। [[सबसे खराब स्थिति का विश्लेषण|वर्स्ट केस]] कोम्प्लेक्ससिटी किसी भी इनपुट को हल करने में लगने वाले समय को मापती है, चूँकि  हल करने में कठिन इनपुट अभ्यास में कभी नहीं आ सकते हैं। ऐसे स्थितियों में, वर्स्ट केस रनिंग टाइम अभ्यास में ओब्सेर्वे रनिंग टाइम  कहीं अधिक वोर्स हो सकता है। उदाहरण के लिए, [[सिम्प्लेक्स एल्गोरिथ्म]] का उपयोग करके एक [[रैखिक कार्यक्रम|लीनियर प्रोग्राम]] को हल करने की वर्स्ट केस कोम्प्लेक्ससिटी घातीय है,<ref name="amenta-ziegler" /> चूँकि अभ्यास में चरणों की देखी गई संख्या सामान्य रूप से लीनियर है।<ref name="shamir" /><ref name="andrei" /> सिम्पलेक्स एल्गोरिथ्म वास्तव में अभ्यास में एल्लिप्सोइड विधि की तुलना में बहुत तेज़ है, चूँकि उत्तरार्द्ध में पालीनोमिअल टाइम  की वर्स्ट केस वाली कोम्प्लेक्ससिटी है।
+यद्यपि [[सबसे खराब स्थिति का विश्लेषण|वर्स्ट केस]] एनालिसिस कई एल्गोरिदम के व्यावहारिक प्रदर्शन को समझाने में व्यापक रूप से सफल रहा है, एनालिसिस की यह शैली कई समस्याओं के लिए मिसलीडिंग परिणाम देती है। [[सबसे खराब स्थिति का विश्लेषण|वर्स्ट केस]] कोम्प्लेक्ससिटी किसी भी इनपुट को हल करने में लगने वाले समय को मापती है, चूँकि हल करने में कठिन इनपुट अभ्यास में कभी नहीं आ सकते हैं। ऐसे स्थितियों में, वर्स्ट केस रनिंग टाइम अभ्यास में ओब्सेर्वे रनिंग टाइम कहीं अधिक वोर्स हो सकता है। उदाहरण के लिए, [[सिम्प्लेक्स एल्गोरिथ्म]] का उपयोग करके एक [[रैखिक कार्यक्रम|लीनियर प्रोग्राम]] को हल करने की वर्स्ट केस कोम्प्लेक्ससिटी घातीय है,<ref name="amenta-ziegler" /> चूँकि अभ्यास में चरणों की देखी गई संख्या सामान्य रूप से लीनियर है।<ref name="shamir" /><ref name="andrei" /> सिम्पलेक्स एल्गोरिथ्म वास्तव में अभ्यास में एल्लिप्सोइड विधि की तुलना में बहुत तेज़ है, चूँकि उत्तरार्द्ध में पालीनोमिअल टाइम की वर्स्ट केस वाली कोम्प्लेक्ससिटी है।
-औसत-केस एनालिसिस सबसे पहले सबसे वर्स्ट -केस एनालिसिस की सीमाओं को दूर करने के लिए प्रस्तुत  किया गया था। चूँकि, परिणामी औसत-स्थिति की कोम्प्लेक्ससिटी इनपुट पर चुने गए प्रोबब्लिटी डिस्ट्रीबुसन  पर बहुत अधिक निर्भर करती है। वास्तव में वास्तविक इनपुट और इनपुट का डिस्ट्रीबुसन एनालिसिस के समय बनाई गई धारणाओं से भिन्न हो सकता है: एक रैंडम इनपुट एक विशिष्ट इनपुट से बहुत भिन्न हो सकता है। डेटा मॉडल की इस पसंद के कारण, सैद्धांतिक औसत-स्थति का परिणाम एल्गोरिदम के व्यावहारिक प्रदर्शन के बारे में बहुत कम कह सकता है।
+औसत-केस एनालिसिस सबसे पहले सबसे वर्स्ट -केस एनालिसिस की सीमाओं को दूर करने के लिए प्रस्तुत किया गया था। चूँकि, परिणामी औसत-स्थिति की कोम्प्लेक्ससिटी इनपुट पर चुने गए प्रोबब्लिटी डिस्ट्रीबुसन पर बहुत अधिक निर्भर करती है। वास्तव में वास्तविक इनपुट और इनपुट का डिस्ट्रीबुसन एनालिसिस के समय बनाई गई धारणाओं से भिन्न हो सकता है: एक रैंडम इनपुट एक विशिष्ट इनपुट से बहुत भिन्न हो सकता है। डेटा मॉडल की इस पसंद के कारण, सैद्धांतिक औसत-स्थति का परिणाम एल्गोरिदम के व्यावहारिक प्रदर्शन के बारे में बहुत कम कह सकता है।
 स्मूथ्द एनालिसिस वर्स्ट केस और औसत-स्थिति एनालिसिस दोनों को सामान्यीकृत करता है और दोनों की शक्ति प्राप्त करता है। इसका उद्देश्य औसत-स्थिति की कोम्प्लेक्ससिटी से कहीं अधिक सामान्य होना है जबकि अभी भी कम कोम्प्लेक्ससिटी सीमाओं को सिद्ध करने की अनुमति है।
 ==इतिहास==
-[[संगणक तंत्र संस्था|एसीएम]] और  [[ईएटीसीएस]] ने स्मूथ्द एनालिसिस विकसित करने के लिए [[डेनियल स्पीलमैन]] और [[शांग ड्रा टी]] को 2008 गोडेल प्राइज से सम्मानित किया था। स्मूथेड एनालिसिस नाम [[एलन एडेलमैन]] द्वारा डेवलपिंग किया गया था।<ref name="spielman-teng-2009" /> 2010 में स्पीलमैन को स्मूथ्द एनालिसिस विकसित करने के लिए [[नेवानलिन्ना पुरस्कार|नेवानलिन्ना प्राइज]] मिला। स्पीलमैन और टेंग का जेएसीएम पेपर एल्गोरिदम का स्मूथ्द एनालिसिस: सिम्प्लेक्स एल्गोरिदम सामान्यत: बहुपद समय क्यों लेता है, [[गणितीय प्रोग्रामिंग सोसायटी]] (एमपीएस) और अमेरिकन गणितीय सोसाइटी (एएमएस) द्वारा संयुक्त रूप से प्रायोजित 2009 फुलकर्सन प्राइज के तीन विजेताओं में से एक था।
+[[संगणक तंत्र संस्था|एसीएम]] और [[ईएटीसीएस]] ने स्मूथ्द एनालिसिस विकसित करने के लिए [[डेनियल स्पीलमैन]] और [[शांग ड्रा टी]] को 2008 गोडेल प्राइज से सम्मानित किया था। स्मूथेड एनालिसिस नाम [[एलन एडेलमैन]] द्वारा डेवलपिंग किया गया था।<ref name="spielman-teng-2009" /> 2010 में स्पीलमैन को स्मूथ्द एनालिसिस विकसित करने के लिए [[नेवानलिन्ना पुरस्कार|नेवानलिन्ना प्राइज]] मिला। स्पीलमैन और टेंग का जेएसीएम पेपर एल्गोरिदम का स्मूथ्द एनालिसिस: सिम्प्लेक्स एल्गोरिदम सामान्यत: बहुपद समय क्यों लेता है, [[गणितीय प्रोग्रामिंग सोसायटी]] (एमपीएस) और अमेरिकन गणितीय सोसाइटी (एएमएस) द्वारा संयुक्त रूप से प्रायोजित 2009 फुलकर्सन प्राइज के तीन विजेताओं में से एक था।
 ==उदाहरण==
@@ Line 18: / Line 18: @@
 सिम्प्लेक्स एल्गोरिदम अभ्यास में एक बहुत ही कुशल एल्गोरिदम है, और यह अभ्यास में लीनियर प्रोग्रामिंग के लिए प्रमुख एल्गोरिदम में से एक है। प्रायोगिक समस्याओं पर, एल्गोरिदम द्वारा उठाए गए कदमों की संख्या चर और बाधाओं की संख्या में लीनियर है।<ref name="shamir" /><ref name="andrei" /> फिर भी सैद्धांतिक रूप से वर्स्ट केस में सबसे सफलतापूर्वक विश्लेषित धुरी नियमों के लिए इसमें तेजी से कई कदम उठाने पड़ते हैं। स्मूथ्द एनालिसिस विकसित करने के लिए यह मुख्य प्रेरणाओं में से एक था।<ref name=spielman-teng-2001 />
-पेरटूरबाशन मॉडल के लिए, हम मानते हैं कि इनपुट डेटा [[गाऊसी वितरण|गाऊसी डिस्ट्रीब्यूशन]]  से ध्वनि से परेशान है। सामान्यीकरण उद्देश्यों के लिए, हम अप्रभावित डेटा मानते हैं <math>\bar{\mathbf A} \in \mathbb{R}^{n\times d}, \bar{\mathbf b} \in \mathbb{R}^n, \mathbf c \in \mathbb{R}^d</math> संतुष्ट <math>\|(\bar{\mathbf a}_i, \bar{b}_i)\|_2 \leq 1</math> सभी पंक्तियों के लिए <math>(\bar{\mathbf a}_i, \bar{b}_i)</math> आव्यूह  का <math>(\bar{\mathbf A}, \bar{\mathbf b}).</math> ये ध्वनि <math>(\hat{\mathbf A}, \hat{\mathbf b})</math> माध्य के साथ गाऊसी डिस्ट्रीबुसन से नमूना की गई स्वतंत्र प्रविष्टियाँ  <math>0</math> और मानक विचलन <math>\sigma</math>. हमने  <math>\mathbf A = \bar{\mathbf A} + \hat{\mathbf A}, \mathbf b = \bar{\mathbf b} + \hat{\mathbf b}</math>.सेट किया है जो स्मूथ्द इनपुट डेटा में लीनियर प्रोग्राम सम्मिलित होता है
+पेरटूरबाशन मॉडल के लिए, हम मानते हैं कि इनपुट डेटा [[गाऊसी वितरण|गाऊसी डिस्ट्रीब्यूशन]] से ध्वनि से परेशान है। सामान्यीकरण उद्देश्यों के लिए, हम अप्रभावित डेटा मानते हैं <math>\bar{\mathbf A} \in \mathbb{R}^{n\times d}, \bar{\mathbf b} \in \mathbb{R}^n, \mathbf c \in \mathbb{R}^d</math> संतुष्ट <math>\|(\bar{\mathbf a}_i, \bar{b}_i)\|_2 \leq 1</math> सभी पंक्तियों के लिए <math>(\bar{\mathbf a}_i, \bar{b}_i)</math> आव्यूह का <math>(\bar{\mathbf A}, \bar{\mathbf b}).</math> ये ध्वनि <math>(\hat{\mathbf A}, \hat{\mathbf b})</math> माध्य के साथ गाऊसी डिस्ट्रीबुसन से नमूना की गई स्वतंत्र प्रविष्टियाँ <math>0</math> और मानक विचलन <math>\sigma</math>. हमने <math>\mathbf A = \bar{\mathbf A} + \hat{\mathbf A}, \mathbf b = \bar{\mathbf b} + \hat{\mathbf b}</math>.सेट किया है जो स्मूथ्द इनपुट डेटा में लीनियर प्रोग्राम सम्मिलित होता है
 :अधिकतम करें
@@ Line 33: / Line 33: @@
 कई [[स्थानीय खोज (अनुकूलन)]] एल्गोरिदम का चलने का समय सबसे व्यर्थ होता है, किंतु अभ्यास में वे अच्छा प्रदर्शन करते हैं।<ref>{{Citation |last=Manthey |first=Bodo |title=Smoothed Analysis of Local Search |date=2021 |url=https://www.cambridge.org/core/books/beyond-the-worstcase-analysis-of-algorithms/smoothed-analysis-of-local-search/CA67DD5FE32ABD53898165847C3F86C7 |work=Beyond the Worst-Case Analysis of Algorithms |pages=285–308 |editor-last=Roughgarden |editor-first=Tim |place=Cambridge |publisher=Cambridge University Press |doi=10.1017/9781108637435.018 |isbn=978-1-108-49431-1 |access-date=2022-06-15}}</ref>
-एक उदाहरण [[ट्रैवलिंग सेल्समैन की समस्या]] के लिए [[2-ऑप्ट]] अनुमानी है। स्थानीय रूप से इष्टतम समाधान मिलने तक इसमें तेजी से कई पुनरावृत्तियां हो सकती हैं, चूँकि अभ्यास में चलने का समय वेर्टिसस की संख्या में सबक्वाड्रैटीक है।<ref name="engler-roeglin-voecking" /> [[सन्निकटन अनुपात|अप्प्रोक्सिमेसन  रेश्यो]], जो एल्गोरिदम के आउटपुट की लंबाई और इष्टतम समाधान की लंबाई के बीच का अनुपात है, अभ्यास में अच्छा होता है किंतु सैद्धांतिक रूप से वर्स्ट केस में भी व्यर्थ हो सकता है।
+एक उदाहरण [[ट्रैवलिंग सेल्समैन की समस्या]] के लिए [[2-ऑप्ट]] अनुमानी है। स्थानीय रूप से इष्टतम समाधान मिलने तक इसमें तेजी से कई पुनरावृत्तियां हो सकती हैं, चूँकि अभ्यास में चलने का समय वेर्टिसस की संख्या में सबक्वाड्रैटीक है।<ref name="engler-roeglin-voecking" /> [[सन्निकटन अनुपात|अप्प्रोक्सिमेसन रेश्यो]], जो एल्गोरिदम के आउटपुट की लंबाई और इष्टतम समाधान की लंबाई के बीच का अनुपात है, अभ्यास में अच्छा होता है किंतु सैद्धांतिक रूप से वर्स्ट केस में भी व्यर्थ हो सकता है।
-समस्या उदाहरणों का एक वर्ग बॉक्स <math>[0,1]^d</math> में <math>n</math> बिंदुओं द्वारा दिया जा सकता है,  जहां उनकी जोड़ीदार दूरियां एक नॉर्म (गणित) से आती हैं। पहले से ही दो आयामों में, 2-ऑप्ट अनुमान स्थानीय इष्टतम खोजने तक तेजी से कई पुनरावृत्तियों को ले सकता है। इस सेटिंग में, कोई पेरटूरबाशन मॉडल का विश्लेषण कर सकता है जहां कोने <math>v_1,\dots,v_n</math> को प्रोबब्लिटी डेंसिटी फ़ंक्शन <math>f_1,\dots,f_n : [0,1]^d \rightarrow [0,\theta]</math> के साथ युनिफोर्मिली डिस्ट्रीबुसन के अनुसार स्वतंत्र रूप से नमूना किया जाता है। <math>\theta = 1</math> के लिए, अंक समान रूप से वितरित किए गए हैं। जब <math>\theta > 1</math> बड़ा होता है, तो प्रतिद्वंद्वी के पास कठिन समस्या की संभावना को बढ़ाने की अधिक क्षमता होती है। इस पेरटूरबाशन मॉडल में, 2-ऑप्ट हेयुरिस्टिक के पुनरावृत्तियों की अपेक्षित संख्या, साथ ही परिणामी आउटपुट के अनुमानित अनुपात,  <math>n</math> और <math>\theta</math> के बहुपद कार्यों से बंधे हैं।<ref name="engler-roeglin-voecking" />
+समस्या उदाहरणों का एक वर्ग बॉक्स <math>[0,1]^d</math> में <math>n</math> बिंदुओं द्वारा दिया जा सकता है, जहां उनकी युग्‍मानूसार दूरियां एक नॉर्म (गणित) से आती हैं। पहले से ही दो आयामों में, 2-ऑप्ट अनुमान स्थानीय इष्टतम खोजने तक तेजी से कई पुनरावृत्तियों को ले सकता है। इस सेटिंग में, कोई पेरटूरबाशन मॉडल का विश्लेषण कर सकता है जहां कोने <math>v_1,\dots,v_n</math> को प्रोबब्लिटी डेंसिटी फ़ंक्शन <math>f_1,\dots,f_n : [0,1]^d \rightarrow [0,\theta]</math> के साथ युनिफोर्मिली डिस्ट्रीबुसन के अनुसार स्वतंत्र रूप से नमूना किया जाता है। <math>\theta = 1</math> के लिए, अंक समान रूप से वितरित किए गए हैं। जब <math>\theta > 1</math> बड़ा होता है, तो प्रतिद्वंद्वी के पास कठिन समस्या की संभावना को बढ़ाने की अधिक क्षमता होती है। इस पेरटूरबाशन मॉडल में, 2-ऑप्ट हेयुरिस्टिक के पुनरावृत्तियों की अपेक्षित संख्या, साथ ही परिणामी आउटपुट के अनुमानित अनुपात, <math>n</math> और <math>\theta</math> के बहुपद कार्यों से बंधे हैं।<ref name="engler-roeglin-voecking" />
+एक अन्य स्थानीय खोज एल्गोरिदम जिसके लिए स्मूथ्द एनालिसिस सफल रहा वह के-मीन्स विधि है।<math>[0,1]^d</math> में <math>n</math> अंक दिए जाने पर, एक ही क्लस्टर में बिंदुओं के बीच छोटी युग्म दूरी वाले समूहों में एक अच्छा विभाजन खोजना एनपी-कठिन है। लॉयड का एल्गोरिदम व्यापक रूप से उपयोग किया जाता है और अभ्यास में बहुत तेज़ है, चूँकि यह स्थानीय रूप से इष्टतम समाधान खोजने के लिए सबसे वर्स्ट केस में पुनरावृत्तियों को ले सकता है। चूँकि यह मानते हुए कि बिंदुओं में स्वतंत्र गॉसियन डिस्ट्रीबुसन हैं, प्रत्येक की अपेक्षा <math>[0,1]^d</math> और मानक विचलन <math>\sigma</math> है, एल्गोरिदम के पुनरावृत्तियों की अपेक्षित संख्या <math>n</math>, <math>d</math> और <math>\sigma</math>. में एक बहुपद से घिरी है।<ref name="david-manthey-roeglin" />
-एक अन्य स्थानीय खोज एल्गोरिदम जिसके लिए स्मूथ्द एनालिसिस सफल रहा वह के-मीन्स विधि है।<math>[0,1]^d</math> में <math>n</math> अंक दिए जाने पर, एक ही क्लस्टर में बिंदुओं के बीच छोटी जोड़ीदार दूरी वाले समूहों में एक अच्छा विभाजन खोजना एनपी-कठिन है। लॉयड का एल्गोरिदम व्यापक रूप से उपयोग किया जाता है और अभ्यास में बहुत तेज़ है, चूँकि यह स्थानीय रूप से इष्टतम समाधान खोजने के लिए सबसे वर्स्ट केस में पुनरावृत्तियों को ले सकता है। चूँकि यह मानते हुए कि बिंदुओं में स्वतंत्र गॉसियन डिस्ट्रीबुसन हैं, प्रत्येक की अपेक्षा <math>[0,1]^d</math> और मानक विचलन <math>\sigma</math> है, एल्गोरिदम के पुनरावृत्तियों की अपेक्षित संख्या  <math>n</math>, <math>d</math> और <math>\sigma</math>. में एक बहुपद से घिरी है।<ref name="david-manthey-roeglin" />
 ==यह भी देखें==
@@ Line 191: / Line 190: @@
 }}
-[[Category: कम्प्यूटेशनल जटिलता सिद्धांत]] [[Category: गणितीय अनुकूलन]] [[Category: एल्गोरिदम का विश्लेषण]]
-[[Category: Machine Translated Page]]
 [[Category:Created On 09/07/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Pages with script errors]]
+[[Category:Templates Vigyan Ready]]
+[[Category:एल्गोरिदम का विश्लेषण]]
+[[Category:कम्प्यूटेशनल जटिलता सिद्धांत]]
+[[Category:गणितीय अनुकूलन]]

Anonymous

Search

स्मूथ्द एनालिसिस: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 14:55, 6 September 2023

Contents

इतिहास

उदाहरण

लीनियर प्रोग्रामिंग के लिए सिंप्लेक्स एल्गोरिदम

संयुक्त अनुकूलन के लिए कोम्बिनाटोरिअल ओप्टीमायजैसन

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

स्मूथ्द एनालिसिस: Difference between revisions

Latest revision as of 14:55, 6 September 2023

इतिहास

उदाहरण

लीनियर प्रोग्रामिंग के लिए सिंप्लेक्स एल्गोरिदम

संयुक्त अनुकूलन के लिए कोम्बिनाटोरिअल ओप्टीमायजैसन

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories