قم بالتقليم والبحث

يُعدّ التقليم والبحث طريقة لحل مشاكل التحسين التي اقترحها نمرود مجدو في عام 1983. ^{[ 1 ]}

تعتمد الفكرة الأساسية لهذه الطريقة على إجراء تكراري يتم فيه في كل خطوة تقليل حجم المدخلات ("تقليمها") بمعامل ثابت 0 < p < 1. وبذلك، فهي شكل من أشكال خوارزمية التقليل والتغلب ، حيث يكون التقليل في كل خطوة بمعامل ثابت. لنفترض أن n هو حجم المدخلات، و T ( n ) هو التعقيد الزمني لخوارزمية التقليم والبحث بأكملها، و S ( n ) هو التعقيد الزمني لخطوة التقليم. عندئذٍ، يخضع T ( n ) للعلاقة التكرارية التالية :

${\displaystyle T(n)=S(n)+T(n(1-p)).}$

يشبه هذا التكرار التكراري للبحث الثنائي، لكن حده S ( n ) أكبر من الحد الثابت في البحث الثنائي. في خوارزميات التقليم والبحث، يكون S(n) خطيًا على الأقل عادةً (لأن المدخلات بأكملها يجب معالجتها). بناءً على هذا الافتراض، يكون حل التكرار T ( n )  = O ( S ( n ))  . يمكن إثبات ذلك إما بتطبيق نظرية ماستر للتكرارات القائمة على أسلوب فرق تسد، أو بملاحظة أن أزمنة حل المسائل الفرعية المتكررة تتناقص وفق متسلسلة هندسية .

وعلى وجه الخصوص، استخدم مجيدو نفسه هذا النهج في خوارزمية الوقت الخطي الخاصة به لمسألة البرمجة الخطية عندما يكون البعد ثابتًا ^{[ 2 ]} ولمسألة الكرة المحيطة الدنيا لمجموعة من النقاط في الفضاء. ^{[ 1 ]}