الخوارزمية الدقيقة
في علوم الحاسوب وبحوث العمليات ، الخوارزميات الدقيقة هي خوارزميات تحل دائمًا مشكلة التحسين إلى الحل الأمثل.
ما لم تكن P = NP ، فإن الخوارزمية الدقيقة لمسألة تحسين صعبة من فئة NP لا يمكن أن تعمل في أسوأ الحالات في وقت متعدد الحدود . وقد أُجريت أبحاث مكثفة لإيجاد خوارزميات دقيقة يكون وقت تشغيلها أُسّيًا مع أساس منخفض. [ 1 ] [ 2 ]
انظر أيضاً
- الاختزال الحافظ على التقريب
- APX هي فئة من المسائل التي تحتوي على خوارزمية تقريب ذات عامل ثابت
- خوارزمية استدلالية
- PTAS - نوع من خوارزميات التقريب التي تأخذ نسبة التقريب كمعامل
مراجع
- ↑ فومين، فيدور ف.؛ كاسكي، بيتري (مارس 2013)، "خوارزميات أسية دقيقة" ، اتصالات رابطة آلات الحوسبة ، 56 (3): 80-88 ، doi : 10.1145/2428556.2428575.
- ^ فومين، فيدور ف. كراتش، ديتر (2010). الخوارزميات الأسية الدقيقة . سبرينغر. ص. 203 . رقم ISBN 978-3-642-16532-0.
فئات :
- نظرية التعقيد الحسابي
- خوارزميات وأساليب التحسين