خوارزمية Las Vegas: ما هي ومتى تُستخدم في هياكل البيانات؟
خوارزمية Las Vegas (لاس فيغاس) هي خوارزمية عشوائية تضمن دائمًا نتيجة صحيحة، لكنّ الزمن الذي تستغرقه للوصول إليها متغيّر ويعتمد على «حظّ» الاختيارات العشوائية داخلها. بعبارة أدق: النتيجة مضمونة الصحّة، أمّا سرعة الوصول إليها فغير مضمونة. هذه هي الفكرة الجوهرية التي تميّزها، وهي أيضًا ما يخلط فيه كثيرون بينها وبين نوع آخر اسمه مونت كارلو، كما سنوضّح بعد قليل.
الاسم مجرّد تشبيه طريف: كما أنّك في كازينو لاس فيغاس قد تربح بسرعة أو بعد محاولات كثيرة، لكنّك في النهاية تخرج بنتيجة، كذلك هذه الخوارزمية قد تنتهي بسرعة أو ببطء، لكنّها لا تعطيك أبدًا إجابة خاطئة.
الفكرة الأساسية: عشوائية في الطريق، لا في النتيجة
الخطأ الشائع هو تصوّر أنّ الخوارزمية «تجرّب حلولًا عشوائية حتى تصادف الحل الصحيح» كأنها تخمين أعمى. هذا غير دقيق. ما يحدث فعليًا أنّ الخوارزمية تتّخذ قرارات عشوائية أثناء عملها (مثل اختيار عنصر محوري عشوائي، أو موضع عشوائي في جدول)، لكنّها تتحقّق دائمًا من صحّة الخطوة قبل اعتمادها. فالعشوائية موجودة في مسار الحل، بينما صحّة الحل تبقى مؤكّدة في كل الأحوال.
هذا يعني أنّ زمن التنفيذ في خوارزمية لاس فيغاس هو متغيّر عشوائي: قد يكون قصيرًا جدًا وقد يطول، لكنّه في المتوسّط جيّد. لذلك نتحدّث عادةً عن «الزمن المتوقّع» (expected time) لا الزمن في أسوأ حالة.
مثال عملي: الفرز السريع العشوائي (Randomized Quicksort)
أشهر مثال حقيقي وليس مجرّد لعبة تعليمية هو نسخة الفرز السريع التي تختار العنصر المحوري (pivot) عشوائيًا:
- اختَر عنصرًا عشوائيًا من المصفوفة ليكون المحور.
- قسّم العناصر إلى ما هو أصغر من المحور وما هو أكبر منه.
- كرّر العملية نفسها على كل قسم حتى تُرتَّب المصفوفة بالكامل.
النتيجة مصفوفة مرتّبة ترتيبًا صحيحًا دائمًا — لا مجال لخطأ. لكن سرعة الوصول تعتمد على مدى «توفيق» المحاور العشوائية: في المتوسّط الزمن ممتاز، وفي حالة نادرة جدًا قد يبطؤ. هذا هو جوهر لاس فيغاس: صحّة مؤكّدة وزمن متغيّر.
بالمقابل، فكرة «ترتيب المصفوفة بتجربة ترتيبات عشوائية حتى تصادف الترتيب الصحيح» (وتُعرف بـ Bogosort) هي تقنيًا خوارزمية لاس فيغاس، لكنها مثال على سوء الاستخدام لأنها بطيئة إلى حدّ العبث، ولا يستعملها أحد عمليًا.
Las Vegas أم Monte Carlo؟
هذا هو الالتباس الأهم. كلاهما خوارزمية عشوائية، لكنهما يتبادلان الضمانات:
| المعيار | خوارزمية Las Vegas | خوارزمية Monte Carlo |
|---|---|---|
| صحّة النتيجة | صحيحة دائمًا | قد تكون خاطئة باحتمال صغير |
| زمن التنفيذ | متغيّر (غير مضمون) | محدود ومضمون |
| ما الذي «نضحّي» به | بالزمن | بالدقّة |
| مثال شائع | الفرز السريع العشوائي | اختبار أوّلية الأعداد (Miller–Rabin) |
| متى نختارها | حين لا نتحمّل أي خطأ | حين نحتاج زمنًا مضمونًا ونقبل هامش خطأ ضئيل |
قاعدة سريعة للتذكّر: لاس فيغاس تضحّي بالوقت لتضمن الصحّة، ومونت كارلو تضحّي بالصحّة لتضمن الوقت. ويمكن أحيانًا تحويل إحداهما إلى الأخرى: إذا وضعت حدًّا زمنيًا لخوارزمية لاس فيغاس وأوقفتها عند بلوغه، تحصل على خوارزمية شبيهة بمونت كارلو.
متى تُستخدم خوارزمية لاس فيغاس فعليًا؟
تظهر هذه الخوارزميات في مواضع محدّدة داخل علوم الحاسب، لا في «كل مكان» كما يُقال أحيانًا:
- الفرز والاختيار العشوائي: مثل Randomized Quicksort وخوارزمية Quickselect لإيجاد العنصر ذي الترتيب k.
- جداول التقطيع (Hashing): مثل Universal Hashing حيث تُختار دالة تقطيع عشوائية لتقليل التصادمات مع ضمان صحّة النتيجة.
- الخوارزميات الهندسية والرسومية: كبناء أغلفة محدّبة أو أشجار بحث عشوائية متوازنة (مثل Treap).
الفائدة المشتركة أنّ العشوائية تجعل الأداء المتوقّع جيّدًا وتُبعِد احتمال «أسوأ حالة» التي قد يستغلّها مدخل خبيث، مع الحفاظ على نتيجة صحيحة تمامًا.
خطأ شائع ينبغي تجنّبه
لا تخلط بين «الخوارزمية العشوائية» و«الخوارزمية التقريبية». التقريبية (Approximation) تعطي حلًّا قريبًا من الأمثل عمدًا. أمّا لاس فيغاس فلا تعطي حلًّا تقريبيًا أبدًا؛ نتيجتها دقيقة مئة بالمئة، والعشوائية تمسّ الزمن فقط. الخلط بين المفهومين يقود إلى اختيار أداة خاطئة لمشكلتك.
الأسئلة الشائعة
هل يمكن أن تُرجع خوارزمية لاس فيغاس نتيجة خاطئة؟ لا. هذا هو تعريفها بالذات؛ إمّا أن تُرجع نتيجة صحيحة، أو (في بعض الصياغات) تُعلن صراحةً أنها فشلت وتُعيد المحاولة، لكنها لا تعطي إجابة خاطئة صامتة.
ما الفرق باختصار بينها وبين مونت كارلو؟ لاس فيغاس: صحّة مضمونة وزمن متغيّر. مونت كارلو: زمن مضمون واحتمال خطأ صغير.
من أين جاء الاسم؟ اقترحه الباحث لاسلو باباي عام 1979 على سبيل التشبيه بكازينوهات لاس فيغاس، تمييزًا لها عن خوارزميات مونت كارلو الأقدم.
هل هي مفيدة عمليًا أم مجرّد نظرية؟ مفيدة جدًا؛ فالفرز السريع العشوائي وجداول التقطيع العشوائية تُستعمل في أنظمة ومكتبات برمجية حقيقية يوميًا.