الخوارزميات العشوائية والتقريبية
توازن الخوارزميات العشوائية والتقريبية بين الدقة أو الحتمية والكفاءة: تستخدم الخوارزميات العشوائية خيارات عشوائية لكسب السرعة أو البساطة، بينما تجد الخوارزميات التقريبية حلولاً شبه مثالية يمكن إثباتها للمشكلات التي يصعب حلها بدقة.
Definition
تتخذ الخوارزميات العشوائية خيارات عشوائية أثناء التنفيذ ويتم تحليلها لوقت التشغيل المتوقع أو احتمال الصحة؛ تعمل الخوارزميات التقريبية بكفاءة وتعيد حلولًا مضمونة لتكون ضمن عامل مثبت من الأمثل لمشكلات التحسين الصعبة.
Scope
يغطي هذا المجال الخوارزميات التي تتخلى عن هدف الحصول على إجابة دقيقة وحتمية. ويشمل الخوارزميات العشوائية (لاس فيغاس ومونتي كارلو)، مع ضماناتها الاحتمالية؛ وخوارزميات التقريب لتحسين NP-hard مع نسب تقريب مثبتة؛ والخوارزميات عبر الإنترنت التي يجب أن تتخذ قرارات دون معرفة المستقبل، ويتم تحليلها بنسبة تنافسية. هذه هي الاستجابات القياسية للمشكلات المستعصية والإعدادات التي تتسم بعدم اليقين، بالاعتماد على تحليل التعقيد ونماذج التصميم.
Sub-topics
Core questions
- كيف يحسن العشوائية وقت التشغيل أو البساطة أو المتانة؟
- ما الفرق بين ضمانات لاس فيغاس ومونتي كارلو؟
- كيف يتم تحديد جودة خوارزمية التقريب بواسطة نسبة التقريب؟
- ما هي مشكلات NP-hard التي تقبل تقريبات جيدة، وما هي التي تقاومها؟
- كيف يتم تقييم القرارات عبر الإنترنت، التي تتخذ دون معلومات مستقبلية، بشكل تنافسي؟
Key concepts
- الخوارزميات العشوائية
- لاس فيغاس ومونتي كارلو
- وقت التشغيل المتوقع
- متباينات التركيز
- نسبة التقريب
- مخطط التقريب متعدد الحدود
- الخوارزميات عبر الإنترنت
- النسبة التنافسية
Key theories
- العشوائية من أجل الكفاءة
- يمكن أن تؤدي الخيارات العشوائية إلى خوارزميات أسرع أو أبسط من أفضل الخوارزميات الحتمية، مع ضمانات على الوقت المتوقع (لاس فيغاس) أو على احتمال الخطأ (مونتي كارلو)، غالبًا باستخدام متباينات التركيز للتحليل.
- نسب التقريب للمشكلات الصعبة NP-hard
- عندما تكون الحلول الدقيقة غير قابلة للتطبيق، توفر خوارزمية التقريب حلاً يمكن إثباته ضمن عامل (نسبة التقريب) من الأمثل؛ وتحدد النسبة القابلة للتحقيق مدى جودة تقريب المشكلة.
Clinical relevance
تُعد هذه الأساليب مجموعة الأدوات العملية للمشكلات الصعبة وغير المؤكدة: تدفع الخوارزميات العشوائية اختبار الأولية في التشفير، والتجزئة، وموازنة الحمل؛ وتنتج الخوارزميات التقريبية حلولًا قابلة للاستخدام لجدولة NP-hard، والتوجيه، والتجميع، ومشكلات تحديد المواقع؛ وتُنمذج الخوارزميات عبر الإنترنت التخزين المؤقت، والترحيل، وتخصيص الموارد حيث يجب اتخاذ القرارات في الوقت الفعلي.
History
اكتسبت الخوارزميات العشوائية أهمية مع اختبارات سولوفاي-ستراسن ورابين للأولية في السبعينيات ودعوة رابين الأوسع للطرق الاحتمالية. نمت خوارزميات التقريب جنبًا إلى جنب مع نظرية NP-completeness منذ السبعينيات، وتم إضفاء الطابع الرسمي على التحليل التنافسي للخوارزميات عبر الإنترنت بواسطة سلاتور وتارجان في الثمانينيات، لتشكل معًا الدراسة الحديثة للخوارزميات غير الدقيقة والاحتمالية.
Key figures
- Rajeev Motwani
- Prabhakar Raghavan
- Vijay Vazirani
- Michael Rabin
- Robert Solovay
- Volker Strassen
Related topics
Seminal works
- motwani1995
- vazirani2001
- cormen2009
Frequently asked questions
- هل الخوارزميات العشوائية غير موثوقة لأنها تستخدم العشوائية؟
- لا. تعيد خوارزميات لاس فيغاس دائمًا إجابة صحيحة ويتغير وقت تشغيلها فقط. قد تخطئ خوارزميات مونتي كارلو، ولكن يمكن تقليل احتمال الخطأ بشكل تعسفي عن طريق التكرار. ضماناتها هي عبارات احتمالية دقيقة، وليست عدم قابلية للتنبؤ.
- لماذا نستخدم خوارزمية تقريب بدلاً من مجرد إيجاد الحل الأمثل؟
- بالنسبة لمشكلات التحسين الصعبة NP-hard، قد يكون إيجاد الحل الأمثل غير ممكن للمدخلات الكبيرة. تعمل خوارزمية التقريب في وقت متعدد الحدود وتضمن حلاً ضمن عامل معروف من الأمثل، وهو غالبًا ما يكون جيدًا بما يكفي وأكثر عملية بكثير من انتظار إجابة دقيقة.