الخوارزمية العشوائية (Randomized Algorithm): ما هي ولماذا تُستخدم في هياكل البيانات؟

الخوارزمية العشوائية (Randomized Algorithm) هي ببساطة خوارزمية تستعين بمصدر للأرقام العشوائية لاتخاذ قرار أو أكثر أثناء تنفيذها، بدلاً من أن تسير على مسار واحد ثابت في كل مرة. النتيجة العملية أنك قد تُدخل المعطيات نفسها مرتين فتمرّ الخوارزمية بمسارين مختلفين داخلياً. الهدف من هذه «العشوائية» ليس اللعب بالحظ، بل تحسين متوسط الأداء أو تفادي الحالات الأسوأ التي تُوقِع الخوارزميات الحتمية (Deterministic) في فخ البطء.

قبل الدخول في التفاصيل، مهم أن نُصحّح لبساً شائعاً: الخوارزمية العشوائية ليست خوارزمية «تُعطي إجابة عشوائية». في معظم الحالات تكون الإجابة صحيحة تماماً، والعشوائية تقع في الطريقة أو الزمن لا في صحة النتيجة. هذا الفارق هو مفتاح فهم النوعين الأساسيين اللذين سنشرحهما بعد قليل.

كيف تعمل فكرة العشوائية داخل الخوارزمية؟

تخيّل أنك تبحث عن عنصر وسيط لتقسيم قائمة (كما في خوارزمية الترتيب Quicksort). لو اخترت دائماً العنصر الأول محوراً (pivot)، فإن خصماً يعرف خوارزميتك يستطيع ترتيب المدخلات بحيث تصبح أبطأ ما يمكن، أي بتعقيد زمني يقترب من O(n²). لكن إذا اخترت المحور عشوائياً في كل خطوة، فلا يستطيع أحد أن يُصمّم مدخلاً «سيئاً» بشكل مضمون، لأن الاختيار لم يعد متوقعاً. النتيجة: متوسط زمني ممتاز قدره O(n log n) بغضّ النظر عن ترتيب المدخلات.

هذه هي القيمة الحقيقية للعشوائية: تحويل «الحالة الأسوأ المضمونة» إلى «حالة أسوأ نادرة الاحتمال جداً».

أنواع الخوارزميات العشوائية: مونتي كارلو ولاس فيغاس

يُقسَّم هذا المجال تقليدياً إلى عائلتين، والفرق بينهما جوهري:

المعيار	خوارزميات مونتي كارلو (Monte Carlo)	خوارزميات لاس فيغاس (Las Vegas)
صحة النتيجة	قد تكون خاطئة باحتمال صغير	صحيحة دائماً
زمن التنفيذ	ثابت ومحدود سلفاً	متغيّر (متوسطه محدود)
مصدر العشوائية	تؤثّر في الدقة	تؤثّر في الزمن
مثال شهير	اختبار أولية عدد (Miller–Rabin)	Quicksort بمحور عشوائي
متى تفضّلها؟	حين تقبل هامش خطأ ضئيلاً مقابل سرعة	حين لا تقبل أي خطأ في النتيجة

القاعدة الذهنية البسيطة: مونتي كارلو تراهن على الدقة بزمن مضمون، ولاس فيغاس تراهن على الزمن بدقة مضمونة. وكثير من خوارزميات مونتي كارلو يمكن تحويلها إلى شبه مؤكدة بتكرارها عدة مرات، إذ يتضاءل احتمال الخطأ أُسّياً مع كل تكرار.

تطبيقات في هياكل البيانات

العشوائية ليست ترفاً نظرياً؛ هي في صميم هياكل بيانات تُستخدم يومياً:

1. قائمة التخطّي (Skip List): بديل أنيق للأشجار المتوازنة، تقرّر ارتفاع كل عقدة برمي «عملة» عشوائية. النتيجة بنية تحافظ على بحث وإدراج بمتوسط O(log n) من دون تعقيد إعادة الموازنة اليدوية.
2. شجرة الـ Treap: تدمج بين شجرة بحث ثنائية وكومة (heap) عبر إسناد أولوية عشوائية لكل عنصر، فتبقى الشجرة متوازنة إحصائياً دون قواعد صارمة.
3. التقطيع (Hashing) والـ Bloom Filter: تعتمد دوال التجزئة العشوائية على توزيع المفاتيح بانتظام لتقليل التصادمات، بينما يستخدم مرشّح بلوم العشوائية ليخبرك بسرعة هائلة إن كان عنصر «غالباً موجوداً» أو «مؤكد غير موجود».
4. خوارزميات الرسوم البيانية: مثل خوارزمية Karger لإيجاد أصغر قطع (Min Cut) في رسم بياني، وهي مونتي كارلو صرفة تعتمد على دمج حواف عشوائية.

متى تختار خوارزمية عشوائية؟ ومتى تتجنّبها؟

اختَرها حين تكون الخوارزمية الحتمية معقّدة أو بطيئة في الحالة الأسوأ، وحين يكون لديك مصدر عشوائية جيد. مثال عملي: اختبار أولية الأعداد الضخمة في التشفير يعتمد كلياً على مونتي كارلو لأنه أسرع بمراحل من الاختبار الحتمي.

تجنّبها، أو استخدمها بحذر، في نظام تحتاج فيه إلى نتائج قابلة لإعادة الإنتاج بدقة لأغراض التصحيح أو التدقيق. الحل الوسط الذكي هو تثبيت «البذرة» (seed) لمولّد الأرقام العشوائية، فتحصل على سلوك عشوائي في الإنتاج لكن قابل للتكرار بالضبط أثناء الاختبار.

نصيحة عملية كثيراً ما تُنسى: جودة الخوارزمية العشوائية لا تتجاوز جودة مولّد الأرقام العشوائية خلفها. استخدام مولّد ضعيف أو متوقّع (كدالة زمن بسيطة) قد يُلغي كل الفائدة النظرية، بل قد يفتح ثغرة أمنية في السياقات التشفيرية حيث يجب استخدام مولّد عشوائي آمن تشفيرياً (CSPRNG).

الأسئلة الشائعة

هل الخوارزمية العشوائية تعني أن نتيجتها غير موثوقة؟ لا. في خوارزميات لاس فيغاس النتيجة صحيحة دائماً، والعشوائية تؤثّر في الزمن فقط. أما في مونتي كارلو فاحتمال الخطأ يمكن جعله صغيراً إلى حدّ يُهمَل عبر التكرار.

ما الفرق بينها وبين الخوارزمية الحتمية؟ الخوارزمية الحتمية تُنتج المسار والنتيجة نفسها في كل تشغيل للمدخل ذاته، بينما العشوائية قد تسلك مساراً مختلفاً في كل مرة بسبب اعتمادها على أرقام عشوائية.

لماذا يُفضّل الكثيرون Quicksort العشوائي على النسخة العادية؟ لأن اختيار المحور عشوائياً يمنع أي مدخل «مُصمَّم» من إجبار الخوارزمية على الحالة الأسوأ O(n²)، فيصبح المتوسط O(n log n) موثوقاً عملياً.

هل أحتاج رياضيات متقدمة لاستخدامها؟ لا لاستخدامها؛ فكثير من المكتبات الجاهزة تطبّقها لك. لكن فهم الاحتمالات الأساسية يساعدك على تقدير هامش الخطأ واختيار عدد التكرارات المناسب في خوارزميات مونتي كارلو.