אלגוריתם מונטה קרלו
במדעי המחשב, אלגוריתם מונטה קרלו הוא אלגוריתם אקראי שהפלט שלו עשוי להיות שגוי בהסתברות מסוימת (בדרך כלל קטנה). שתי דוגמאות לאלגוריתמים כאלה הן אלגוריתם קרגר[1] ואלגוריתם מונטה קרלו עבור בעיית FAS מינימלית.[2]
השם מתייחס לקזינו במונטה קרלו שבנסיכות מונקו, אשר ידוע ברחבי העולם כסמל להימורים.
המחלקה הקשורה של אלגוריתמים מסוג לאס וגאס היא אקראית גם כן, אבל בדרך אחרת: זמן הריצה שלהם משתנה באופן אקראי, אך הם תמיד מחזירים את התשובה הנכונה. ניתן להמיר אלגוריתם מונטה קרלו לאלגוריתם לאס וגאס במקרים בהם קיימת פרוצדורה שיכולה לוודא כי הפלט הניתן על ידי אלגוריתם הוא אכן נכון. אם המצב הוא כזה, אז האלגוריתם מסוג לאס וגאס שמתקבל הוא רק להריץ את האלגוריתם מסוג מונטה קרלו שוב ושוב עד שאחת הריצות מייצרת פלט שניתן לוודא שהוא נכון.
שגיאה חד-צדדית, לעומת דו-צדדית
בעוד התשובה המוחזרת על ידי אלגוריתם דטרמיניסטי צפויה להיות נכונה תמיד, זה לא המצב באלגוריתם מונטה קרלו. עבור בעיות הכרעה, אלגוריתמים אלו מסווגים בדרך כלל ל"נוטה ל-לא" או "נוטה ל-כן". אלגוריתם מונטה קרלו הנוטה ל-לא צודק תמיד כשהוא מחזיר לא; אלגוריתם נוטה ל-כן צודק תמיד כשהוא מחזיר כן. החלוקה מתארת אלגוריתמים עם שגיאה חד-צדדית, אך לאלגוריתמים אחרים ייתכן שלא תהיה נטייה לאחד הצדדים; לאלגוריתמים אלו נאמר שיש שגיאה דו-צדדית. התשובה שהם מספקים (או כן או לא) תהיה נכונה או לא נכונה, בהסתברות חסומה כלשהי.
למשל, בדיקת הראשוניות של Solovay–Strassen משמשת כדי לקבוע אם מספר נתון הוא מספר ראשוני. היא תמיד עונה כן עבור קלט שהוא מספר ראשוני; עבור מספר פריק, היא מחזירה לא בהסתברות לפחות בהסתברות קטנה מ ½ . לפיכך, תשובה לא מהאלגוריתם היא נכונה בוודאות, ואילו תשובה כן נשארת בספק; זה הוא אמר להיות אלגוריתם ½ נכון-נוטה-ללא.
אמפליפיקציה (הגברה)
עבור אלגוריתם מונטה קרלו עם שגיאה חד-צדדית, ניתן להקטין את ההסתברות לכישלון (ולהגביר את הסתברות ההצלחה) על ידי הרצת האלגוריתם k פעמים. נקח לדוגמה שוב את אלגוריתם Solovay–Strassen שהוא ½ נכון-נוטה-ללא. ניתן להריץ את האלגוריתם מספר פעמים ולהחזיר כתשובה לא אם הוא קיבלנו תשובה לא תוך k איטרציות, אחרת נחזיר כן. לכן, אם המספר הוא ראשוני, אז התשובה תמיד נכונה, ואם המספר הוא פריק אז התשובה נכונה בהסתברות לפחות .
עבור אלגוריתם מונטה קרלו עם שגיאה דו-צדדית, גם כן ניתן להפחית את ההסתברות לכישלון על ידי הפעלת האלגוריתם k פעמים, והחזרת פונקציית רוב (majority) על התשובות.
מחלקות סיבוכיות
מחלקת הסיבוכיות BPP מתארת בעיות הכרעה שניתן לפתור על ידי אלגוריתם מונטה קרלו בזמן פולינומי עם הסתברות שגיאה דו-צדדית חסומה, ומחלקת הסיבוכיות RP מתארת את הבעיות שניתן לפתור על ידי אלגוריתם מונטה קרלו עם הסתברות שגיאה חד-צדדית חסומה: אם התשובה הנכונה היא לא, האלגוריתם תמיד אומר כך, אבל הוא עשוי לענות לא באופן שגוי על כמה מקרים שבהם התשובה הנכונה היא כן. לעומת זאת, מחלקת הסיבוכיות ZPP מתארת בעיות פתירות על ידי אלגוריתם לאס וגאס שתוחלת הזמן שלהם פולינומית. ZPP ⊆ RP ⊆ BPP, אך לא ידוע אם מחלקה כלשהי מהן נבדלת מהאחרות; זאת אומרת, ייתכן שלאלגוריתמים מסוג מונטה קרלו יש יותר כח חישובי מאשר לאלגוריתמים מסוג לאס וגאס, אך זה לא הוכח. מחלקת סיבוכיות נוספת, PP, מתארת בעיות הכרעה להן קיים אלגוריתם מונטה קרלו עם זמן פולינומי, שהוא מדויק יותר מאשר הטלת מטבע אך שלא ניתן בהכרח לחסום בהן את הסתברות השגיאה כקטנה ממש מ- ½ .
יישומים בתורת המספרים החישובית
אלגוריתמים ידועים מסוג מונטה קרלו כוללים את בדיקת הראשוניות של Solovay–Strassen, בדיקת הראשוניות Baillie-PSW, בדיקת הראשוניות של מילר–רבין, וכמה גרסאות מהירות מסוימות של אלגוריתם Schreier–Sims בתורת הקבוצות החישובית.
ראו גם
- שיטת מונטה קרלו, אלגוריתמים המשמשים סימולציות על מערכות פיזיקליות או מתמטיות בהתבסס על דגימה אקראית.
- אלגוריתם אטלנטיק סיטי
- אלגוריתם לאס וגאס
לקריאה נוספת
- Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. New York: Cambridge University Press. ISBN 0-521-47465-5.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Ch 5. Probabilistic Analysis and Randomized Algorithms". Introduction to Algorithms (2nd ed.). Boston: MIT Press and McGraw-Hill. ISBN 0-262-53196-8.
- Berman, Kenneth A; Paul, Jerome L. (2005). "Ch 24. Probabilistic and Randomized Algorithms". Algorithms: Sequential, Parallel, and Distributed. Boston: Course Technology. ISBN 0-534-42057-5.
הערות שוליים
- ^ Karger, David R.; Stein, Clifford (ביולי 1996). "A New Approach to the Minimum Cut Problem". J. ACM. 43 (4): 601–640. doi:10.1145/234533.234534. ISSN 0004-5411.
{{cite journal}}: (עזרה) - ^ 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.
