प्रून एंड सर्च

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

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

$T(n)=S(n)+T(n(1-p)).$

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

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