 |
כצפוי, הפתרון לבעית המוניות תלוי במודל שמייצר את מחירי הנסיעה, וגם בפונקציית המטרה.
יש כמה מודלים מעניינים (התפלגות ידועה, התפלגות לא ידועה אבל ממשפחה מוכרת (למשל, אחידה עם טווח לא ידוע), או התפלגות לא ידועה), וכמה פונקציות מטרה רלוונטיות: אפשר לנסות למקסם את הסיכוי לתפוס את המונית המשתלמת ביותר (או אחת מבין 2 או 7 הטובות ביותר), אפשר לנסות למקסם את תוחלת הרווח, ואפשר לנסות למקסם את תוחלת המקום של המונית שנבחרה מבין כל n המועמדים.
לא כל צירוף אפשרי; למשל, קל לראות שאין אלגוריתם שממקסם את תוחלת הרווח עבור כל התפלגות של המחירים (ולכן, אם רוצים אלגוריתם שמטפל בכל התפלגות, סביר יותר לנסות למקסם משהו אחר).
בגירסה המוכרת של השאלה, רוצים לתפוס דווקא את המונית הטובה ביותר (ואם לא - כאשר אבדתי אבדתי). מכיוון1 שבכל צעד יש רק שתי אפשרויות (לקחת את המונית או לחכות), האסטרטגיה האופטימלית תהיה לצפות ב- a*n המוניות הראשונות, ואז לחטוף את הראשונה שטובה יותר מכל המדגם הזה. מצד אחד כדאי ש- a יהיה גדול (כדי שכאשר ניגש לשלב הבחירה נדע מה אנחנו מחפשים), ומצד שני אם a גדול מדי, עלול להיות שהפסדנו את המונית האופטימלית בשלב הראשון. מתברר1 שהסיכוי להצליח (במובן הזה) הוא (a*log(1/a; המקסימום מתקבל (כפי שכבר ציינו כאן) אם קובעים (a=exp(-1 ואז הסיכוי להצליח גם הוא (exp(-1.
הנה מודל אחר, שגם הוא מביא לתוצאות מעניינות. נניח שהרווח הצפוי מכל מונית מתפלג באופן אחיד בין 0 ל- 1. לא רק בגלל שזו התפלגות קלה לטיפול, אלא משתי סיבות: ראשית, ב*כל* התפלגות של X, ההסתברות של Y (מאותה התפלגות) להיות גדול מ- X, היא בעלת התפלגות אחידה. כלומר, בחישוב עבור התפלגות אחידה אנחנו מחשבים בעצם את "ההסתברות הממוצעת" עבור כל ההתפלגויות בבת-אחת. הסיבה השניה היא שההתפלגות האחידה קלה יותר לטיפול.
ובכן, נניח שמחירי המוניות הם בעלי התפלגות אחידה בין 0 ל- 1, ונניח שאנחנו רוצים למקסם לא את הסיכוי לתפוס את המונית הטובה ביותר, אלא את תוחלת הרווח.
אם נשארה רק מונית אחת, ברור שהאסטרטגיה הקבילה היחידה היא "קח מה שנותנים לך". תוחלת הרווח: חצי.
אם נשארו שתי מוניות, נחכה לראשונה מביניהן, ונשווה את הרווח האפשרי לזה הצפוי אם נחכה למונית השניה. אם הרווח גדול מחצי (הסיכוי לזה הוא 0.5), נקפוץ על המציאה (ונרוויח, בתוחלת, 0.75). אחרת (סיכוי 0.5) נחכה (ואז תוחלת הרווח שחישבנו קודם היא 0.5). בסך-הכל, תוחלת הרווח משתי מוניות היא חמש-שמיניות.
על התרגיל הזה אפשר לחזור k פעמים, ולגלות שאם תוחלת הרווח מ- k מוניות היא (a(k, אז האסטרטגיה האופטימלית כשלפנינו נהג מספר k+1 (מהסוף) היא לבחור בו אם הרווח גדול מ- (a(k, ולוותר אם לא. הרווח מן האסטרטגיה הזו הוא a(k+1)=(1+a(k)*a(k))/2. קל להשתכנע (גם מתוך המשוואה וגם מתוך המשמעות של המספרים האלה) שכאשר k גדל, (a(k מתקרב ל- 1.
אפשר לחשב כמה מהר (a(k מתקרב ל- 1. בעזרת כמה קירובים מסמרי-שיער, אפשר גם לחשב כמה זמן נצטרך להמתין עד שתעצור לנו מונית k שהרווח ממנה עולה על (a(n-k (זו המונית שתיקח אותנו לארלוזרוב). מתברר שכאשר n גדול, תוחלת זמן ההמתנה היא n/3.
(לדוגמא, המספר המדוייק עבור n=1000 הוא 335.7).
1 אני משמיט פרטים טכניים; וגם די הרבה 1-ים.
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש