प्रून एंड सर्च: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Optimization method}} प्रून एंड सर्च 1983 में निम्रोद मेगिद्दो द्वारा सुझ...")
 
No edit summary
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Optimization method}}
{{Short description|Optimization method}}
प्रून एंड सर्च 1983 में [[निम्रोद मेगिद्दो]] द्वारा सुझाई गई ऑप्टिमाइज़ेशन (गणित) समस्याओं को हल करने की एक विधि है।<ref name=lp3>Nimrod Megiddo (1983) Linear-time algorithms for linear programming in R<sup>3</sup> and related problems. SIAM J. Comput., 12:759&ndash;776 {{doi|10.1109/SFCS.1982.24}}</ref>
'''प्रून एंड सर्च''' सन्न 1983 में [[निम्रोद मेगिद्दो]] द्वारा सुझाई गई अनुकूलन (गणित) समस्याओं को हल करने की विधि होती है।<ref name="lp3">Nimrod Megiddo (1983) Linear-time algorithms for linear programming in R<sup>3</sup> and related problems. SIAM J. Comput., 12:759&ndash;776 {{doi|10.1109/SFCS.1982.24}}</ref>
विधि का मूल विचार एक पुनरावर्ती प्रक्रिया है जिसमें प्रत्येक चरण पर इनपुट आकार को एक स्थिर कारक द्वारा कम (छंटाई) किया जाता है {{math|0 < ''p'' < 1}}. इस प्रकार, यह कमी और विजय एल्गोरिथ्म का एक रूप है, जहां प्रत्येक चरण में कमी एक स्थिर कारक द्वारा होती है। होने देना {{mvar|n}} इनपुट आकार हो, {{math|''T''(''n'')}} संपूर्ण प्रून-एंड-सर्च एल्गोरिदम की समय जटिलता हो, और {{math|''S''(''n'')}} प्रूनिंग चरण की समय जटिलता हो। तब {{math|''T''(''n'')}} निम्नलिखित [[पुनरावृत्ति संबंध]] का पालन करता है:
 
सामान्यतः विधि का मूल विचार पुनरावर्ती प्रक्रिया है जिसमें प्रत्येक चरण पर इनपुट आकार को स्थिर कारक {{math|0 < ''p'' < 1}} द्वारा कम (छंटाई) किया जाता है। इस प्रकार, यह कमी और विजय एल्गोरिथ्म का रूप होता है, जहां प्रत्येक चरण में कमी स्थिर कारक द्वारा होती है। मान लीजिए {{mvar|n}} इनपुट आकार होता है, अतः {{math|''T''(''n'')}} संपूर्ण प्रून-एंड-सर्च एल्गोरिदम की समय जटिलता होती है, और {{math|''S''(''n'')}} प्रूनिंग चरण की समय जटिलता होती है। इस प्रकार तब {{math|''T''(''n'')}} निम्नलिखित [[पुनरावृत्ति संबंध]] का पालन करता है।


: <math>T(n) = S(n) + T(n(1-p)). </math>
: <math>T(n) = S(n) + T(n(1-p)). </math>
यह बाइनरी खोज के लिए पुनरावृत्ति जैसा दिखता है लेकिन इसमें बड़ा है {{math|''S''(''n'')}} द्विआधारी खोज की स्थिर अवधि की तुलना में शब्द। प्रून और सर्च एल्गोरिदम में एस(एन) आम तौर पर कम से कम रैखिक होता है (क्योंकि पूरे इनपुट को संसाधित किया जाना चाहिए)। इस धारणा के साथ, पुनरावृत्ति का समाधान है {{math|1=''T''(''n'')&nbsp;=&nbsp;[[Big Oh notation|O]](''S''(''n''))}}. इसे या तो विभाजित करें और जीतें पुनरावृत्ति के लिए [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]] | मास्टर प्रमेय को लागू करके या यह देखकर देखा जा सकता है कि पुनरावर्ती उपसमस्याओं के लिए समय एक ज्यामितीय श्रृंखला में घटता है।
यह बाइनरी खोज के लिए पुनरावृत्ति जैसा दिखता है किंतु इसमें बाइनरी खोज के स्थिर पद की तुलना में बड़ा {{math|''S''(''n'')}} पद होता है। इस प्रकार प्रून और सर्च एल्गोरिदम में एस(एन) सामान्यतः कम से कम रैखिक होता है (जिससे कि पूर्ण इनपुट को संसाधित किया जाता है)। इस धारणा के साथ, पुनरावृत्ति का समाधान {{math|1=''T''(''n'')&nbsp;=&nbsp;[[Big Oh notation|O]](''S''(''n''))}} होता है। इसे या तो विभाजित करते है और जीतें पुनरावृत्ति के लिए [[मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)]] को क्रियान्वित करके या यह देखकर देखा जा सकता है कि पुनरावर्ती उपसमस्याओं के लिए समय ज्यामितीय श्रृंखला में घट जाता है।
 
विशेष रूप से, आयाम तय होने पर [[रैखिक प्रोग्रामिंग]] समस्या के लिए मेगिद्दो ने स्वयं अपने [[रैखिक समय]] एल्गोरिदम में इस दृष्टिकोण का उपयोग किया था<ref>Nimrod Megiddo (1984)Linear Programming in Linear Time When the Dimension Is Fixed {{doi|10.1145/2422.322418}}</ref> और अंतरिक्ष में बिंदुओं के एक सेट के लिए न्यूनतम घेरने वाले क्षेत्र की समस्या के लिए।<ref name=lp3/>
 


विशेष रूप से, मेगिद्दो ने स्वयं अपने [[रैखिक समय]] एल्गोरिदम में इस दृष्टिकोण का उपयोग [[रैखिक प्रोग्रामिंग]] समस्या के लिए किया गया था<ref>Nimrod Megiddo (1984)Linear Programming in Linear Time When the Dimension Is Fixed {{doi|10.1145/2422.322418}}</ref> और अंतरिक्ष में बिंदुओं के समुच्चय के लिए न्यूनतम घेरने वाले क्षेत्र की समस्या के लिए होता है।<ref name="lp3" />
==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}
{{Algorithmic paradigms}}[[Category: ज्यामितीय एल्गोरिदम]] [[Category: रैखिक प्रोग्रामिंग]]
{{Algorithmic paradigms}}
 
 


[[Category: Machine Translated Page]]
[[Category:Collapse templates]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:ज्यामितीय एल्गोरिदम]]
[[Category:रैखिक प्रोग्रामिंग]]

Latest revision as of 11:04, 14 August 2023

प्रून एंड सर्च सन्न 1983 में निम्रोद मेगिद्दो द्वारा सुझाई गई अनुकूलन (गणित) समस्याओं को हल करने की विधि होती है।[1]

सामान्यतः विधि का मूल विचार पुनरावर्ती प्रक्रिया है जिसमें प्रत्येक चरण पर इनपुट आकार को स्थिर कारक 0 < p < 1 द्वारा कम (छंटाई) किया जाता है। इस प्रकार, यह कमी और विजय एल्गोरिथ्म का रूप होता है, जहां प्रत्येक चरण में कमी स्थिर कारक द्वारा होती है। मान लीजिए n इनपुट आकार होता है, अतः T(n) संपूर्ण प्रून-एंड-सर्च एल्गोरिदम की समय जटिलता होती है, और S(n) प्रूनिंग चरण की समय जटिलता होती है। इस प्रकार तब T(n) निम्नलिखित पुनरावृत्ति संबंध का पालन करता है।

यह बाइनरी खोज के लिए पुनरावृत्ति जैसा दिखता है किंतु इसमें बाइनरी खोज के स्थिर पद की तुलना में बड़ा S(n) पद होता है। इस प्रकार प्रून और सर्च एल्गोरिदम में एस(एन) सामान्यतः कम से कम रैखिक होता है (जिससे कि पूर्ण इनपुट को संसाधित किया जाता है)। इस धारणा के साथ, पुनरावृत्ति का समाधान T(n) = O(S(n)) होता है। इसे या तो विभाजित करते है और जीतें पुनरावृत्ति के लिए मास्टर प्रमेय (एल्गोरिदम का विश्लेषण) को क्रियान्वित करके या यह देखकर देखा जा सकता है कि पुनरावर्ती उपसमस्याओं के लिए समय ज्यामितीय श्रृंखला में घट जाता है।

विशेष रूप से, मेगिद्दो ने स्वयं अपने रैखिक समय एल्गोरिदम में इस दृष्टिकोण का उपयोग रैखिक प्रोग्रामिंग समस्या के लिए किया गया था[2] और अंतरिक्ष में बिंदुओं के समुच्चय के लिए न्यूनतम घेरने वाले क्षेत्र की समस्या के लिए होता है।[1]

संदर्भ

  1. 1.0 1.1 Nimrod Megiddo (1983) Linear-time algorithms for linear programming in R3 and related problems. SIAM J. Comput., 12:759–776 doi:10.1109/SFCS.1982.24
  2. Nimrod Megiddo (1984)Linear Programming in Linear Time When the Dimension Is Fixed doi:10.1145/2422.322418