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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

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

מבנה האלגוריתמים[עריכת קוד מקור | עריכה]

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

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

הדגמה על ידי חישוב פאי[עריכת קוד מקור | עריכה]

אנימציה של חישוב פאי באמצעות הטלת 30,000 נקודות אקראיות אל רבע עיגול החסום בריבוע

דוגמה פשוטה למימוש שיטה זו היא השיטה הבאה לחישוב π:

  1. על לוח עץ נצייר ריבוע שאורך צלעו יחידה אחת. נצייר מעגל חסום בריבוע זה (זהו מעגל שקוטרו שווה ליחידה אחת)
  2. נתחיל להטיל חצים אל הריבוע (לא נכוון את החץ למרכז הריבוע, אלא אל הריבוע כולו, באופן אקראי). פונקציית ההסתברות במקרה זה היא אחידה, כלומר יש הסתברות שווה לפגיעה בכל נקודה על פני הריבוע.
  3. כל חץ שפגע נבדק האם הוא בתוך העיגול או מחוץ לעיגול. במקרה זה, זהו החישוב הדטרמיניסטי שמבוצע.
  4. נבדוק כמה חיצים היו בתוך העיגול מתוך כמות החצים הכוללת. לאחר מספר רב של הטלות, היחס בין מספר הפעמים שהחצים פגעו בתוך המעגל, למספר הפעמים שבהם פגעו בתוך הריבוע שואף ליחס שבין שטחי שתי הצורות, שהוא 4 / π . ככל שזורקים יותר חיצים, הערך של מספר החצים בתוך העיגול חלקי מספר החצים הכללי, יתקרב יותר ויותר לערך פאי חלקי ארבע. אם נכפיל את התוצאה הסופית בארבע נקבל קירוב למספר פאי.

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

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

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