الرئيسيةعريقبحث

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

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

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

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

مصادر

  1. Hoare, C. A. R. (July 1961). "Algorithm 64: Quicksort". Commun. ACM. 4 (7): 321–. doi:10.1145/366622.366644. ISSN 0001-0782. مؤرشف من الأصل في 18 ديسمبر 2019.
  2. Kudelić, Robert (2016-04-01). "Monte-Carlo randomized algorithm for minimal feedback arc set problem". Applied Soft Computing. 41: 235–246. doi:10.1016/j.asoc.2015.12.018. مؤرشف من الأصل في 16 نوفمبر 2018.
  3. "Probabilistic algorithms should not be mistaken with methods (which I refuse to call algorithms), which produce a result which has a high probability of being correct. It is essential that an algorithm produces correct results (discounting human or computer errors), even if this happens after a very long time." Henri Cohen (2000). A Course in Computational Algebraic Number Theory. Springer-Verlag, p. 2
  4. "In اختبار أولية عدد ما of very large numbers chosen at random, the chance of stumbling upon a value that fools the اختبار فيرما لأولية عدد ما is less than the chance that أشعة كونية will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering." هال أبيلسون and Gerald J. Sussman (1996). Structure and Interpretation of Computer Programs. MIT Press, section 1.2 - تصفح: نسخة محفوظة 28 ديسمبر 2017 على موقع واي باك مشين.

موسوعات ذات صلة :