Page 12 - מגזין הטכניון | אביב 2006

±≤
Âϯ˜≠‰ËÂÓ†˙ËÈ˘Ï†‰˘„Á†‰Ò¯È‚
ωÈ†‰ÈÈ˘Ú˙†˙Ò„‰Ï†‰ËϘى†¨˙‚†È‡ÁÂȆÔÈÈˢȷ¯†Ô·Â‡¯†¯ÂÒÙ¯ن˙‡Ó
Ô Â È  Î Ë ‰ † ˙ Ó È ·
האיור שלפנינו מציג בעיה: כיצד ניתן לאמוד
את שטחן של הצורות האדומות? מאחר שלא
מדובר בצורות גיאומטריות "מסודרות", אין
שום נוסחה לחישוב השטח האמור.
פתרון מקורב לבעיה זו ניתן לפני יותר מששים
שנה עם פיתוחה של שיטת מונטה-קרלו. בשיטה
זו חוסמים את הצורות בצורה גיאומטרית שאת
שטחה קל לחשב - מלבן, במקרה הזה. אחרי
ביצוע החסימה מגרילים באקראי, ובהתפלגות
אחידה, נקודות בכל שטח המלבן. לאחר שנקבעו
הנקודות אין שום בעיה לחשב את היחס בין
מספר הנקודות ש"נפלו" בתוך הצורות לבין
ליחס ‰Ó„ מספר הנקודות הכולל. יחס זה
שבין שטח הצורות לבין שטח המלבן.
שיטת מונטה קרלו נועדה להתמודד עם בעיות
שונות, כגון"בעיות ספירה" - בעיות שהשאלה
שבמרכזן היא כמה פתרונות )או פתרונות בעלי
תכונות מסוימות( יש לבעיה נתונה.
הזמן הנדרש לפתרון בעיות ספירה מסובכות
עולה בקצב מעריכי )אקספוננציאלי( עם
מורכבות הבעיה. לדוגמה, אם הבעיה שלפנינו
היא בכמה דרכים ניתן לסדר סכין, כף ומזלג,
ונדרשות לנו 23 שניות לפתור את הבעיה, הרי
אם נוסיף גם כפית לסיפור הזה העניין יסתבך
מאוד, ויידרשו לנו 24 שניות; כדי לחשב את
מספר הדרכים לסדר סכו"ם לששה סועדים
יידרשו לנו כמה חודשים.
שיטת מונטה-קרלו תוקפת את בעיות הספירה
בגישה אקראית, כפי שראינו בדוגמה. השיטה
פותחה בזמן מלחמת העולם השנייה במסגרת
פרויקט מנהטן - פרויקט הפיתוח של פצצת
האטום. השיטה, שאותה פיתח המתמטיקאי
סטניסלב אולם שעבד בפרויקט, מנצלת את
יכולתו של המחשב )המצאה חדשה באותם
ימים( לבצע חישובים מייגעים במהירות,
ומאפשרת פתרון מקורב של חלק מאותן בעיות
קשות. מכיוון שהקירוב נעשה באמצעות דגימה
סטטיסטית עם מספרים אקראיים והגרלות,
זכתה השיטה לכינוי מונטה-קרלו - על שם עיר
האפשריים כעל חלק מכלל הטיולים )עם חזרות
ובלעדיהן( באותו אורך נתון, שאת מספרם קל
לחשב; ואז נוכל להפעיל את שיטת מונטה-קרלו,
כלומר להגריל באקראי ובהתפלגות אחידה
טיולים, ולחשב את אחוז הטיולים-ללא-חזרות
מתוך כלל הטיולים שהגרלנו.
בטיולים ארוכים אנו נתקלים בבעיה נוספת: על
אף שמספר הטיולים-ללא-חזרות הוא עצום,
חלקם בכלל הטיולים הוא מזערי, וכמוהו הסיכוי
שנגריל טיול ארוך ללא חזרות. לדוגמה, מספר
הטיולים-ללא-חזרות באורך 27 צעדים מהווה
פחות מחמש אלפיות האחוז מכלל הטיולים
באותו אורך. אם ננסה להקביל את זה לדוגמה
הראשונה )הצורות האדומות(, הרי זה כאילו
שטח המלבן גדול פי חצי מיליון משטח הצורות
האדומות. במצב כזה קשה להגריל נקודות בתוך
הצורות ולאמוד את שטחן.
˙¯Ù¢Ӊ†‰Ò¯È‚‰
לאחרונה פותחה בטכניון שיטת מונטה-קרלו
דגם של פתרונותִמשופרת, שבה מגרילים מ
לבעיה, מעדכנים את המנגנון ההסתברותי של
ההגרלה על סמך המדגם, וחוזר חלילה. השיטה
˜ÏÁ‰†Ï„‚ , כך שממדגם למדגםÔÂÈÒÈ‰Ó†˙„ÓÂÏ
של המדגם. במקרה של בעיית הצורות È˘ÂÓÈ˘‰
האדומות יהיה חלק גדול יותר של הנקודות
המוגרלות בתוך הצורות האדומות, ובמקרה של
בעיית הטיולים-ללא-חזרות יתפסו הטיולים
ללא חזרות חלק גדול יותר מכלל הטיולים.
בבעיית הטיולים תלמד השיטה המשופרת
שהליכה כלפי מטה בצעד השישי, המסומן בחץ
אדום, יוצרת טיול עם חזרות, ולכן תבחר ללכת
כלפי מעלה. כך מאפשרת השיטה אומדן של
מספר הטיולים-ללא-חזרות אפילו כשמדובר
בטיול באורך מאה צעדים, בדיוק של כ-%5.
שפותחה בטכניון ˙„ÓÂφÂϯ˜≠‰ËÂÓ†˙ËÈ˘
הינה פריצת דרך. זוהי שיטה כללית המתאימה
לכל בעיית ספירה, ואנו מקווים כי היא תזכה
ליישומים רבים ותגרור אחריה תגליות נוספות.
ההימורים המפורסמת. מאז היא הפכה לאחת
השיטות החישוביות הנפוצות בעולם.
˙¯ÊÁ†‡ÏφÏÂÈË
חסימת הצורות האדומות בדוגמה הקודמת
היתה משימה פשוטה, אולם בבעיות ספירה
אמיתיות הדברים אינם תמיד כה פשוטים.
דוגמה לבעיית ספירה אמיתית היא בעיית
,(Self Avoiding Walkהטיול-ללא-חזרות )
בעיה שיש לה יישומים בביולוגיה מולקולרית,
ובתחום ההנדסה הגנטית בפרט.
טיול-ללא-חזרות הוא סדרת צעדים בין
משבצות, שבה אסור לדרוך על אותה משבצת
יותר מפעם אחת. בבעיית הטיול-ללא-חזרות
ברצוננו לדעת כמה טיולים-ללא-חזרות )מאותה
נקודת מוצא( יש לכל מספר צעדים נתון.
האיור שלמטה מדגים טיולים בני שישה צעדים
- פעם אחת ללא חזרות )מימין( ופעם אחת עם
חזרות. קל לראות שמספר הטיולים-ללא-חזרות
באורך צעד אחד הוא ארבעה, מפני שאפשר
ללכת לאחת מארבע המשבצות השכנות
למשבצת ההתחלתית. לא קשה לספור גם את
שמונת הטיולים-ללא-חזרות באורך שני צעדים.
במאמץ קל אפשר לספור את 001
הטיולים-ללא-חזרות באורך ארבעה צעדים, אך
ספירת 284 הטיולים-ללא-חזרות באורך חמישה
צעדים אינה מלאכה קלה.
אפשר לכתוב תוכנית מחשב פשוטה אשר
תספור את כל הטיולים ללא חזרות באורך
כלשהו. כך אנו יודעים, למשל, שמספר
הטיולים-ללא-חזרות באורך 27 צעדים הוא
881,317,491,628; אך בבואנו להריץ את התוכנית
כדי לספור את הטיולים-ללא-חזרות באורך 28
צעדים, זמן הריצה של התוכנית הינו ארוך כל
כך - אפילו כשמשתמשים במחשבים חזקים
מאוד - שאיש מעולם לא טרח לעשות זאת.
בבעיית הטיולים לא נוכל אמנם להשתמש
בשיטת החסימה, כפי שעשינו בדוגמת השטחים
האדומים, אולם נוכל לחשוב על הטיולים
טיול ללא חזרות טיול עם חזרות