प्रून एंड सर्च
प्रून एंड सर्च 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
