Prune and search
ছাঁটাই এবং অনুসন্ধান হল 1983 সালে নিম্রোদ মেগিডো দ্বারা প্রস্তাবিত অপ্টিমাইজেশন সমস্যা সমাধানের একটি পদ্ধতি। পদ্ধতির মূল ধারণাটি হল একটি পুনরাবৃত্তিমূলক পদ্ধতি যেখানে প্রতিটি ধাপে ইনপুটের আকার একটি ধ্রুবক ফ্যাক্টর দ্বারা হ্রাস করা হয় ("ছাঁটা")। যেমন, এটি হ্রাস এবং জয় অ্যালগরিদমের একটি রূপ, যেখানে প্রতিটি ধাপে হ্রাস একটি ধ্রুবক ফ্যাক্টর দ্বারা হয়। ইনপুট আকার হতে দিন, পুরো ছাঁটাই-এবং-অনুসন্ধান অ্যালগরিদমের সময় জটিলতা হতে দিন, এবং ছাঁটাই ধাপের সময় জটিলতা হতে দিন। তারপর নিম্নলিখিত পুনরাবৃত্তির সম্পর্ক মেনে চলেঃ এটি বাইনারি অনুসন্ধানের পুনরাবৃত্তির অনুরূপ তবে বাইনারি অনুসন্ধানের ধ্রুবক শব্দের চেয়ে বড় শব্দ রয়েছে। প্রুন এবং সার্চ অ্যালগরিদমগুলিতে এস (এন) সাধারণত কমপক্ষে রৈখিক হয় (যেহেতু পুরো ইনপুটটি অবশ্যই প্রক্রিয়া করা উচিত)। এই অনুমানের সাথে, পুনরাবৃত্তির সমাধান রয়েছে। এটি হয় বিভাজন-এবং-জয় পুনরাবৃত্তির জন্য প্রধান উপপাদ্য প্রয়োগ করে বা পর্যবেক্ষণ করে দেখা যেতে পারে যে একটি জ্যামিতিক সিরিজে পুনরাবৃত্তিমূলক উপ-সমস্যাগুলির সময় হ্রাস পায়। বিশেষত, মেগিডো নিজেই তার রৈখিক সময় অ্যালগরিদমে রৈখিক প্রোগ্রামিং সমস্যার জন্য এই পদ্ধতিটি ব্যবহার করেছিলেন যখন মাত্রা স্থির থাকে এবং স্থানের পয়েন্টগুলির একটি সেটের জন্য ন্যূনতম আবদ্ধ গোলক সমস্যার জন্য। তথ্যসূত্র জ্যামিতিক অ্যালগরিদম রৈখিক প্রোগ্রামিং