प्रून एंड सर्च: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Optimization method}} | {{Short description|Optimization method}} | ||
प्रून एंड सर्च 1983 में [[निम्रोद मेगिद्दो]] द्वारा सुझाई गई | '''प्रून एंड सर्च''' सन्न 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–776 {{doi|10.1109/SFCS.1982.24}}</ref> | ||
विधि का मूल विचार पुनरावर्ती प्रक्रिया है जिसमें प्रत्येक चरण पर इनपुट आकार को स्थिर कारक | |||
सामान्यतः विधि का मूल विचार पुनरावर्ती प्रक्रिया है जिसमें प्रत्येक चरण पर इनपुट आकार को स्थिर कारक {{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'') = [[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" /> | ||
==संदर्भ== | ==संदर्भ== | ||
{{reflist}} | {{reflist}} | ||
Revision as of 00:05, 8 August 2023
प्रून एंड सर्च सन्न 1983 में निम्रोद मेगिद्दो द्वारा सुझाई गई अनुकूलन (गणित) समस्याओं को हल करने की विधि होती है।[1]
सामान्यतः विधि का मूल विचार पुनरावर्ती प्रक्रिया है जिसमें प्रत्येक चरण पर इनपुट आकार को स्थिर कारक 0 < p < 1 द्वारा कम (छंटाई) किया जाता है। इस प्रकार, यह कमी और विजय एल्गोरिथ्म का रूप होता है, जहां प्रत्येक चरण में कमी स्थिर कारक द्वारा होती है। मान लीजिए n इनपुट आकार होता है, अतः T(n) संपूर्ण प्रून-एंड-सर्च एल्गोरिदम की समय जटिलता होती है, और S(n) प्रूनिंग चरण की समय जटिलता होती है। इस प्रकार तब T(n) निम्नलिखित पुनरावृत्ति संबंध का पालन करता है।
यह बाइनरी खोज के लिए पुनरावृत्ति जैसा दिखता है किंतु इसमें बाइनरी खोज के स्थिर पद की तुलना में बड़ा S(n) पद होता है। इस प्रकार प्रून और सर्च एल्गोरिदम में एस(एन) सामान्यतः कम से कम रैखिक होता है (जिससे कि पूर्ण इनपुट को संसाधित किया जाता है)। इस धारणा के साथ, पुनरावृत्ति का समाधान T(n) = O(S(n)) होता है। इसे या तो विभाजित करते है और जीतें पुनरावृत्ति के लिए मास्टर प्रमेय (एल्गोरिदम का विश्लेषण) को क्रियान्वित करके या यह देखकर देखा जा सकता है कि पुनरावर्ती उपसमस्याओं के लिए समय ज्यामितीय श्रृंखला में घट जाता है।
विशेष रूप से, मेगिद्दो ने स्वयं अपने रैखिक समय एल्गोरिदम में इस दृष्टिकोण का उपयोग रैखिक प्रोग्रामिंग समस्या के लिए किया गया था[2] और अंतरिक्ष में बिंदुओं के समुच्चय के लिए न्यूनतम घेरने वाले क्षेत्र की समस्या के लिए होता है।[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
- ↑ Nimrod Megiddo (1984)Linear Programming in Linear Time When the Dimension Is Fixed doi:10.1145/2422.322418
