Prune and search
کٹائی اور تلاش اصلاح کے مسائل کو حل کرنے کا ایک طریقہ ہے جو نیمروڈ میگڈو نے 1983 میں تجویز کیا تھا۔ طریقہ کار کا بنیادی خیال ایک تکراری طریقہ کار ہے جس میں ہر مرحلے پر ان پٹ کا سائز ایک مستقل عنصر کے ذریعے کم ("کٹا ہوا") کیا جاتا ہے۔ اس طرح، یہ کمی اور فتح الگورتھم کی ایک شکل ہے، جہاں ہر مرحلے پر کمی ایک مستقل عنصر سے ہوتی ہے۔ آئیے ان پٹ کا سائز ہو، پوری کٹائی اور تلاش کے الگورتھم کی وقت کی پیچیدگی ہو، اور کٹائی کے مرحلے کی وقت کی پیچیدگی ہو۔ پھر مندرجہ ذیل تکرار کے تعلق کی اطاعت کرتا ہے: یہ بائنری سرچ کے تکرار سے ملتا جلتا ہے لیکن اس کی اصطلاح بائنری سرچ کی مستقل اصطلاح سے بڑی ہے۔ پرن اور سرچ الگورتھم میں S (n) عام طور پر کم از کم لکیری ہوتا ہے (چونکہ پورے ان پٹ پر کارروائی کی جانی چاہیے)۔ اس مفروضے کے ساتھ، تکرار کا حل ہے۔ یہ یا تو تقسیم اور فتح کے تکرار کے لیے ماسٹر تھیوریم کا اطلاق کرکے یا یہ مشاہدہ کرکے دیکھا جا سکتا ہے کہ جیومیٹرک سیریز میں تکرار کے ذیلی مسائل کا وقت کم ہو جاتا ہے۔ خاص طور پر، میگڈو نے خود اس نقطہ نظر کو اپنے لکیری ٹائم الگورتھم میں لکیری پروگرامنگ کے مسئلے کے لیے استعمال کیا جب طول و عرض طے ہوتا ہے اور خلا میں پوائنٹس کے ایک سیٹ کے لیے کم سے کم منسلک دائرے کے مسئلے کے لیے۔ حوالہ جات ہندسی الگورتھم لکیری پروگرامنگ