Randomized Algorithms
بدلاً من البحث عن الحل الدقيق (الذي قد يستغرق سنوات)، نستخدم أرقاماً عشوائية للحصول على إجابة سريعة جداً (مع احتمالية خطأ ضئيلة جداً).
اختبار الأعداد الأولية (Primality Test)
كيف نعرف أن رقماً ضخماً جداً هو عدد أولي؟ (مهم للتشفير).
القسمة التقليدية تأخذ وقتاً طويلاً.
إذا كان $P$ أولياً، فإن $A^{P-1} \equiv 1 \pmod P$.
نختار $A$ عشوائياً ونجرب. إذا نجح الاختبار عدة مرات، فالعدد "غالباً" أولي .
Randomized Quicksort
مشكلة Quicksort هي الـ Worst Case $O(N^2)$ إذا كان الـ Pivot سيئاً.
- الحل: اختر الـ Pivot عشوائياً.
- النتيجة: احتمال حدوث الـ Worst Case يصبح شبه مستحيل، ونضمن الأداء $O(N \log N)$ في المتوسط.
Backtracking (التراجع)
Brute Force with Brains 🧠
هي طريقة لحل المشاكل بتجربة الخطوات واحدة تلو الأخرى.
إذا وصلنا لطريق مسدود (أو خالفنا شرطاً)، نقوم بـ التراجع (Backtrack) خطوة للخلف ونجرب مساراً آخر.
إعادة بناء مواقع النقاط من مجموعة المسافات بينها. نضع نقطة، ونتحقق من المسافات، إذا فشلت نحذفها ونجرب غيرها.
(Try -> Fail -> Back)
Game Strategies (Minimax)
كيف يلعب الكمبيوتر؟
في ألعاب مثل Tic-Tac-Toe أو الشطرنج:
• الكمبيوتر يريد تعظيم فوزه (Max).
• الخصم يريد تقليل فوز الكمبيوتر (Min).
يبحث في شجرة اللعبة (Game Tree) لعدة خطوات للأمام، ويختار الحركة التي تضمن أفضل نتيجة ممكنة بغض النظر عن لعب الخصم.
Tic-Tac-Toe State
Pruning (التقليم)
هو عملية إيقاف البحث في فرع معين من الشجرة لأننا تأكدنا أنه لن يؤدي لحل (في Backtracking) أو أنه أسوأ من حل وجدناه سابقاً (في Alpha-Beta).
التقليم هو سر سرعة هذه الخوارزميات.
Are Randomized Algorithms Perfect?
ليس دائماً!
• Monte Carlo: سريعة دائماً، لكن قد تخطئ في الإجابة أحياناً (مثل Primality Test).
• Las Vegas: الإجابة صحيحة دائماً، لكن قد تأخذ وقتاً طويلاً (مثل Randomized Quicksort).