خوارزمية مونت كارلو

في مجال الحوسبة ، تُعدّ خوارزمية مونت كارلو خوارزمية عشوائية قد تكون مخرجاتها غير صحيحة باحتمالية معينة (عادةً ما تكون صغيرة) . ومن الأمثلة على هذه الخوارزميات خوارزمية كارغر-شتاين ^{[ 1 ]} وخوارزمية مونت كارلو لمجموعة أقواس التغذية الراجعة الدنيا ^{[ 2 ]} .

يشير الاسم إلى كازينو مونت كارلو في إمارة موناكو ، والذي يشتهر عالميًا كرمز للمقامرة. وقد استخدم مصطلح "مونت كارلو" لأول مرة عام 1947 من قبل نيكولاس متروبوليس . ^{[ 3 ]}

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

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

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

على سبيل المثال، يُستخدم اختبار سولوفاي-ستراسن لتحديد ما إذا كان عددٌ ما عددًا أوليًا . يُعطي هذا الاختبار دائمًا نتيجة صحيحة للأعداد الأولية؛ أما للأعداد المركبة، فيُعطي نتيجة خاطئة باحتمالية لا تقل عن النصف ، ونتيجة صحيحة باحتمالية أقل من النصف . وبالتالي، فإن الإجابات الخاطئة من الخوارزمية صحيحةٌ حتمًا، بينما تظل الإجابات الصحيحة غير مؤكدة؛ ويُطلق على هذه الخوارزمية اسم خوارزمية متحيزة خاطئة بنسبة خطأ 1/2 .

في خوارزمية مونت كارلو ذات الأخطاء أحادية الجانب، يمكن تقليل احتمال الفشل (وزيادة احتمال النجاح) بتشغيل الخوارزمية k مرة. لنأخذ خوارزمية سولوفاي-ستراسن كمثال، وهي خوارزمية صحيحة بنسبة 1/2 مع تحيز خاطئ . يمكن تشغيل هذه الخوارزمية عدة مرات، حيث تُرجع إجابة خاطئة إذا وصلت إلى استجابة خاطئة خلال k تكرار، وإلا تُرجع إجابة صحيحة . بالتالي، إذا كان العدد أوليًا ، فإن الإجابة صحيحة دائمًا، وإذا كان العدد مركبًا ، فإن الإجابة صحيحة باحتمال لا يقل عن 1 − (1 − 1/2 ) ^k = 1 − 2 ^{− k} .  

بالنسبة لخوارزميات اتخاذ القرار مونت كارلو ذات الخطأ ثنائي الجانب، يمكن تقليل احتمال الفشل مرة أخرى عن طريق تشغيل الخوارزمية k مرة وإرجاع دالة الأغلبية للإجابات.

تصف فئة التعقيد BPP مسائل القرار التي يمكن حلها باستخدام خوارزميات مونت كارلو ذات زمن متعدد الحدود مع احتمال محدود للخطأ من كلا الجانبين، بينما تصف فئة التعقيد RP المسائل التي يمكن حلها باستخدام خوارزمية مونت كارلو مع احتمال محدود للخطأ من جانب واحد: إذا كانت الإجابة الصحيحة خاطئة ، فإن الخوارزمية تُشير إلى ذلك دائمًا، ولكنها قد تُجيب بـ "خطأ" بشكل غير صحيح في بعض الحالات التي تكون فيها الإجابة الصحيحة صحيحة . ^{[ 4 ]} في المقابل، تصف فئة التعقيد ZPP المسائل التي يمكن حلها باستخدام خوارزميات لاس فيغاس ذات زمن متوقع متعدد الحدود. ZPP ⊆ RP ⊆ BPP ، ولكن من غير المعروف ما إذا كانت أي من فئات التعقيد هذه متميزة عن الأخرى؛ أي أن خوارزميات مونت كارلو قد تمتلك قدرة حسابية أكبر من خوارزميات لاس فيغاس، ولكن هذا لم يُثبت بعد. ^{[ 4 ]} فئة تعقيد أخرى، PP ، تصف مشاكل القرار باستخدام خوارزمية مونت كارلو ذات وقت متعدد الحدود ، وهي أكثر دقة من قلب العملة ، ولكن لا يمكن بالضرورة تقييد احتمال الخطأ بعيدًا عن 1/2 . ^{[ 4 ]}

تنقسم الخوارزميات العشوائية بشكل أساسي إلى نوعين رئيسيين، هما مونت كارلو ولاس فيغاس، إلا أن هذين النوعين لا يمثلان سوى قمة التسلسل الهرمي ويمكن تصنيفهما بشكل أكبر. ^{[ 4 ]}

• لاس فيغاس
  • شيروود - "حالة خاصة فعالة ومؤثرة في لاس فيغاس"
  • رقمي — "لاس فيغاس الرقمية"
• مونت كارلو
  • أتلانتيك سيتي - "حالة خاصة من مونت كارلو ذات خطأ محدود"
  • عددي - "تقريب عددي مونت كارلو"

"تتعامل كل من لاس فيغاس ومونت كارلو مع القرارات، أي المشكلات في صيغة القرار الخاصة بهما ." ^{[ 4 ]} "مع ذلك، لا ينبغي أن يُعطي هذا انطباعًا خاطئًا ويحصر هذه الخوارزميات في مثل هذه المشكلات - يمكن استخدام كلا النوعين من الخوارزميات العشوائية في المشكلات العددية أيضًا، وهي المشكلات التي لا تكون فيها المخرجات بسيطة "نعم" / "لا"، ولكن حيث يحتاج المرء إلى الحصول على نتيجة ذات طبيعة عددية." ^{[ 4 ]}

مقارنة بين خوارزميات لاس فيغاس ومونت كارلو

	كفاءة	الأمثل	فشل (LV) / خطأ (MC)
لاس فيغاس (LV)	احتمالي	تأكيد	${\displaystyle <{\tfrac {1}{2}}}$
شيروود	مؤكد، أو احتمالي شيروود (رابط أقوى من الرابط العادي)	تأكيد	0
عددي	احتمالي، أو مؤكد، أو شيروود الاحتمالي	تأكيد	${\displaystyle <{\tfrac {1}{2}}}$أو 0
مونت كارلو (MC)	تأكيد	احتمالي	${\displaystyle <1}$(الاحتمال الذي ينمو بشكل شبه أسي من خلال عمليات التشغيل المتكررة) سيؤدي ذلك إلى الحد من فائدة الخوارزمية؛ والحالة النموذجية هي${\displaystyle <{\tfrac {1}{2}}}$)
مدينة أتلانتيك	تأكيد	احتمالي	${\displaystyle <{\tfrac {1}{4}}}$
عددي	تأكيد	احتمالي	${\displaystyle <1}$(يعتمد على نوع الخوارزمية)

يمثل الجدول السابق إطارًا عامًا لخوارزميات مونت كارلو ولاس فيغاس العشوائية. ^{[ 4 ]} بدلًا من الرمز الرياضي${\displaystyle <}$يمكن للمرء أن يستخدم${\displaystyle \leq }$وبالتالي تتساوى الاحتمالات في أسوأ الحالات. ^{[ 4 ]}

تشمل خوارزميات مونت كارلو المعروفة اختبار سولوفاي-ستراسن الأولي، واختبار بايلي-PSW الأولي ، واختبار ميلر-رابين الأولي ، وبعض المتغيرات السريعة لخوارزمية شراير-سيمز في نظرية المجموعة الحسابية .

بالنسبة للخوارزميات التي تنتمي إلى مجموعة خوارزميات التحسين العشوائي (SO)، حيث لا تُعرف الاحتمالية مسبقًا ويتم تحديدها تجريبيًا، فمن الممكن أحيانًا دمج خوارزمية مونت كارلو مع هذه الخوارزمية "للحصول على كلٍ من حد الاحتمالية المحسوب مسبقًا ومكون التحسين العشوائي". ^{[ 4 ]} "مثال على هذه الخوارزمية هو مونت كارلو المستوحى من النمل ". ^{[ 4 ] [ 5 ]} وبهذه الطريقة، "يتم التخفيف من عيوب التحسين العشوائي، ويتم بناء الثقة في الحل". ^{[ 4 ] [ 5 ]}

• أساليب مونت كارلو ، وهي خوارزميات تُستخدم في المحاكاة الفيزيائية والإحصاءات الحاسوبية القائمة على أخذ عينات عشوائية
• خوارزمية مدينة أتلانتيك
• خوارزمية لاس فيغاس