שיטת מונטה קרלו

שיטת מונטה קרלו היא שיטה לפתרון בעיות חישוביות באמצעות מספרים אקראיים (בניגוד לאלגוריתמים דטרמיניסטיים הנהוגים בדרך כלל).

אלגוריתמי מונטה קרלו הם אלגוריתמים חישוביים שמגרילים מספרים אקראיים מספר גדול של פעמים ומבצעים חישובים על המספרים שהוגרלו. לעתים קרובות משתמשים באלגוריתמי מונטה-קרלו כדי לבצע סימולציות על מערכות פיזיקליות או מתמטיות מורכבות. השימוש העיקרי בהם הוא כדי לפתור בעיות שאינן ניתנות לפתרון מתמטי מדויק, או כדי לחסוך בכוח חישוב.

אלגוריתמים אלו מוצלחים במיוחד עבור מערכות שבהם יש הרבה דרגות חופש שתלויות אחת בשנייה, כמו בהידרודינמיקה, מבנים תאיים ובפיזיקת חלקיקים. שימוש נוסף חשוב שנעשה בהם הוא לצורך חישוב אינטגרלים רב ממדיים. זו שיטה מצוינת לחישוב של סיכונים, טובה יותר משיטות מתמטיות אחרות ומאינטואיציה אנושית.

השם "שיטות מונטה קרלו" (Monte-Carlo methods) ניתן לאלגוריתמים אלו על ידי פיזיקאים אמריקאיים במעבדה הלאומית לוס אלמוס. שם זה נובע מהטכניקה האקראית שביסוד השיטה, ומהמוניטין שיצא לקזינו של מונטה קרלו, והוא ניתן לשיטה על ידי חלוציה: הפיזיקאי אנריקו פרמי והמתמטיקאים סטניסלב אולם, ג'ון פון נוימן וניק מטרופוליס.

שיטות אקראיות לביצוע חישובים היו בשימוש עוד לפני המצאת המחשב. בשנת 1930 השתמש פרמי בשיטה כזו לחישוב תכונותיו של הנייטרון, שהתגלה באותה עת. עם זאת, המצאת המחשב, שאיפשרה ביצוע סימולציות בקלות רבה, נתנה דחיפה עיקרית לחקירתן של שיטות אלה ולהתפתחותן. בפרט, שיטות אלה שימשו בהיקף נרחב בפרויקט מנהטן לייצור פצצת אטום.

שיטה דומה היא שיטת לאס-וגאס שבה האלגוריתמים מניבים תמיד תוצאה נכונה, אך זמן החישוב לרוב ארוך יותר.

מבנה האלגוריתמים

ישנה קבוצה גדולה של אלגוריתמים שנמצאים בשימוש נרחב שנקראים אלגוריתמי מונטה-קרלו. לרוב האלגוריתמים האלו המבנה הבא:

  1. מוגדר מרחב של קלטים אפשריים לאלגוריתם.
  2. הקלטים נבחרים על ידי מחשב מתוך מרחב הקלטים האפשריים על ידי שימוש בפונקציית הסתברות מסוימת המופעלת על מרחב זה.
  3. על קלטים אלו מחושב חישוב דטרמיניסטי מסוים.
  4. הסטטיסטיקה של כל התוצאות נאספת ומוצגת.