خوارزمية عشوائية

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