בתשובה לראובן, 20/01/05 10:20
 |
|
 |
||
|
||||
 |
הה, זה די קרוב לאפשרות שזרקתי שתודעה היא משהו שצץ מעצמו אצל מכונה חישובית מסובכת מספיק. אני רק רוצה להזכיר שמידול "התגובות של עצמו" הוא עניין רקורסיבי שכן המסכן צריך למדל גם את התגובות שלו על המידול הראשוני וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הלאה, וכך הל IHG0056D STORAGE OVERFLOW HAS OCCURRED IN WHOAMI () FUNCTION איפה היינו? אה, כן, העפתי מבט חטוף בלינק שהבאת וזה נראה מעניין.היתה פעם חידה שקשורה לעניין (ואני מנסח אותה כאן ברוח קרב המוניות מדיון אחר): אתה חי בעולם של מוניות לא-מפוקחות, אין לך מושג מה המחיר המקובל להגיע מ A ל B, ואתה מוכן לחכות לכל היותר עד שיעצרו לך n מוניות. מהי האיסטרטגיה הטובה להחלטה מתי לקבל את הצעת המחיר ולהכנס למונית התורנית? (וזה לא היה הג"א, זה היה גדוד נהגי הפרדות) |
 |
 |
 |
|
|
|
||
|
||||
|
החידה של המוניות מזכירה לי את החידה שאלון פתר פעם באייל תגובה 161200 (השאלה המקורית היא של גלעד ברזילי)וגם ליובל נוב היתה בעיה דומה תגובה 162120 עם פיתרון של מ.השור תגובה 162498 . חוץ מזה, אני מכיר שאלה אחרת "פרקטית"- במלחמת העולם השנייה , כוחות הברית היו מנסים לאמוד כמה טנקים גרמנים יוצרו בפס ייצור מסויים, על ידי אומדנים המבוססים על המספרים הסידוריים של טנקים שנשבו (בעצם שהושמדו). זה גם קרוב ברוח לבעיות תמחור אופציות. ועכשיו, לאחר הקונטקסט ההסטורי- אני לא בדיוק יודע איך פותרים, תמיד אפשר לחכות למונית האחרונה.במקרה כזה בממוצע אני משלם את המחיר הממוצע( כמובן) ,אבל מה שהייתי עושה זה רושם את ההצעה הטובה ביותר כפונקציה של מספר המוניות שבדקתי, בונה מזה אקסטרפולציה ( לפי התפלגות גומבל, או איך שקוראים לזה) ומסכים לקחת את המונית הבאה אם לפי הנוסחא המצב שלי לשפר יקטן. אני מתאר לעצמי שיש תשובה יותר אלגנטית, אחרת זאת לא היתה חידה. אמשיך לחשוב עליה. באשר לרקורסיה, אני חושב שהרעיון הוא שכדי לקבל תודעה *כלשהי* אין צורך לפוצץ את ה STACK . מי שיש לו יותר יכולת רקורסיבית אולי רק יותר מודע. בכל אופן אני לא כל כך מחזיק מהרעיונות האילו, הן מופיעות אצלי תחת הקטגוריה "קריירה אחת-תאוריה אחת". |
|
|
|
|
|
|
||
|
||||
|
ודאי שכולנו מומחים גדולים בעצירת הרקורסיה, וחוץ ממתי מעט קטטונים יש לנו, לכל הפחות, interrupt handler משובח. אל תחפש תשובה אלגנטית, "חידה" לא היה המינוח הנכון. אני יודע רק מה שמישהו סיפר לי בתור התשובה, אין לי מושג אם היא נכונה (ובטח צריך גם כל מיני השערות על התפלגות המחירים שתקבל בעולם היעקוביאני). רוצה לדעת מה התשובה שנתנו לי (כאמור, בלי שאני יודע אם היא שווה משהו?) |
|
|
|
|
|
|
||
|
||||
|
עוד לא. תן לי כמה ימים. | |
|
|
|
|
|
||
|
||||
|
כולנו נתקלים בחידה הזו כל פעם שאנחנו צריכים לקנות ירקות (או מוצר לא מפוקח אחר). | |
|
|
|
|
|
||
|
||||
|
למה? אתה לא יודע לחזור אחורה ? | |
|
|
|
|
|
||
|
||||
|
למה? מישהו מבטיח לי שהמחיר ישאר קבוע? | |
|
|
|
|
|
||
|
||||
|
בשווקים שאני מבקר בהם, אין בעיה אמיתית להסתובב בין הדוכנים ולהשוות מחירים. מעולם לא נתקלתי במחיר שהשתנה תוך כדי השיטוטים שלי (אם נוציא את שוק ההון מהתמונה). | |
|
|
|
|
|
||
|
||||
|
assuming the price offered is normally distributed, use n-9 samples to get a good estimation of the first 2 moments (mean and variance), and then take the first offer which is more then a sigma below the mean. (since a third are, 9 samples will get you there with high probability).
if n is big enough, use n-k (k>9), and demand more then a sigma as your threshold. or simply take the first one - you'll get the mean price, and you don't have to waist any more time. |
|
|
|
|
|
|
||
|
||||
|
אם הכל יקבלו את ההצעה האחרונה שלך, מחירי הנסיעה במונית יאמירו לגבהים כאלה שיש סכנה להתנגשות עם אסטרואידים. עסק ביש, כי גם בגבהים האלה עדיין יהיה נכון להשתמש באותה עצה. | |
|
|
|
|
|
||
|
||||
|
no no, the others are piegons - very smart consumers publishing comperative reaserch on the web etc. I'm the only hawk.
|
|
|
|
|
|
|
||
|
||||
|
רגע, אנחנו מדברים על *שוק* אמיתי, שמגיב לאסטרטגיה שלי, או שמדובר בסתם שורה של מספרים עם התפלגות לא ידועה אבל קבועה? | |
|
|
|
|
|
||
|
||||
|
השני. (החידה המקורית עסקה בהרמון ונשים, כשהמארח הנדיב מעביר אותן לנגד עיניך עד שאתה אומר ''זותי'', בלי חרטות ובלי חזרות) |
|
|
|
|
|
|
||
|
||||
|
כן, האמת שכשקראתי את החידה מיד חשבתי על הבעיה של בחירת בת(או בן) זוג- האם להשקיע בקשר קיים או לנסות שוב. | |
|
|
|
|
|
||
|
||||
|
החידה המקורית גם דרשה שאתה תהיה מעוניין במונית הזולה ביותר וזהו, כלומר מבחינתך אין הבדל בין השניה הזולה ביותר והיקרה ביותר. אם לא הצלחת לקלוע לזולה (האישה היפה ביותר) אז נכשלת. ואז הפתרון הוא כמובן &*%&#^@!!%^*@)&@ |
|
|
|
|
|
|
||
|
||||
|
לא. אני אמנם מעוניין באישה היפה ביותר (סתאאאם. כבר יש לי) אבל מנסה למקסם את תוחלת היופי בהנחה שלא אצליח לפגוע בול. ברור שאין אלגוריתם שמבטיח למצוא את האישה היפה ביותר לפני שראיתי את כולן, ואם היא לא האחרונה זה כבר מאוחר מדי. | |
|
|
|
|
|
||
|
||||
|
עליך להשתמש במחצית הראשונה של n המוניות כקבוצת מדגם. המונית הזולה ביותר בקבוצה זו תהיה נקודת הבקרה שלך, וברגע שיש מונית שמציעה מחיר זול יותר, קחנה מהר! אם נסתכל על הזולה ביותר ועל השניה הזולה ביותר, יש הסתברות של 25% שהשניה הזולה ביותר תהיה בחצי הראשון והזולה ביותר בחצי השני - ואז הצלחת. כעקרון, הסיכויים מגיעים למקסימום כשאתה משתמש ב-n/e המוניות הראשונות בקבוצת מדגם (יעזור אם המוניות מגיעות בצורה לא רציונלית). |
|
|
|
|
|
|
||
|
||||
|
הפתרון שניתן לי דומה, אבל לא לגמרי זהה. | |
|
|
|
|
|
||
|
||||
|
בגדול זה הגיוני לחלק לשלושה חלקים: בראשון אתה לומד את השטח ומאתר מטרות. בשני אתה מחפש מישהו נורא זול ( נניח שיותר זול מהשיא בחלק הראשון) בחלק השלישי אתה מפעיל נוהל פאניקה: השעון הביולוגי מתקתק ועוד לא מצאת כלה (טייב- או חתן). נוהל פאניקה זה, ( כמו שתארתי מקודם) יכול להיות מבוסס על פשרות הולכות ומעמיקות ככל שמספר האפשרויות מצטמצם. מעבר לשאלות על איך לחלק את שלושת החלקים ( ברור שאם תבלה יותר מדי בכיול, כל מונית נוספת תהיה אכזבה - תסמונת האקס המיתולוגית כמו שעירית לינור קוראת לזה) עדיין צריך להחליט על מנגנון התפשרות בסוף. | |
|
|
|
|
|
||
|
||||
|
אני חושב שההנחה הגאוסית היא לא טובה, ואני גם חושב שהניסיון למצוא ערכי שיא על ידי אומדנים של סטית תקן היא לא לעניין. אפשר להראות בקלות ש*אם* אתה יודע את ההסתברות pלמצוא מונית עם מחיר פחות מ Z, ההסתברות *לא* למצוא כזה מחיר ב K ניסיונות דועכת אקספוננציאלית ב K. קבוע הדעיכה הוא אחד פחות p. משמע, אם יש לפניך עוד K ניסיונות, כדאי לך להמר על מחיר שהסיכוי למצוא אותו הוא (פחות או יותר) אחד חלקי K או יותר. עכשיו, איך מוצאים אמדן טוב להתפלגות, שהרי אין לנו מושג מהי? הניחוש שלי זה שטוב נעשה עם נסתכל על תוצאות השיאים עד עכשיו. בגדול אפשר להניח שערכי השיא ( שיא הזולות) ישתפרו בהתחלה מהר, ואז לאט. אפשר גם לאמוד את ההתנהגות הזאת כפונקציה של מספר הניחושים ושל הנהגות ההתפלגות קרוב לתחתית. היוריסטית מה שהיית עושה, זה דוגם איזה שלושה ארבעה, אבנה רשימה ממוינת, ואז מחכה עד שאני פוגש מונית עם מחיר יותר נמוך מכל ארבעה. אם נשארו לי עו שלושה ניסיונות, אתפשר ואלך על השני הכי נמוך וכן הלאה. אבל, כאמור, אני עוד צריך לחשוב על זה. |
|
|
|
|
|
|
||
|
||||
|
כצפוי, הפתרון לבעית המוניות תלוי במודל שמייצר את מחירי הנסיעה, וגם בפונקציית המטרה. יש כמה מודלים מעניינים (התפלגות ידועה, התפלגות לא ידועה אבל ממשפחה מוכרת (למשל, אחידה עם טווח לא ידוע), או התפלגות לא ידועה), וכמה פונקציות מטרה רלוונטיות: אפשר לנסות למקסם את הסיכוי לתפוס את המונית המשתלמת ביותר (או אחת מבין 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-ים. |
|
|
|
|
|
|
||
|
||||
|
יפה. בשעתו מי שהציג לי את השאלה טען שהתוחלת המכסימלית היא לבדוק את n/e הראשונות, ואז לבחור את הראשונה שמחירה זול מ*הממוצע* שלהן (או, בהרמון, את הראשונה שיפה מהממוצע של אלה שכבר ראיתי). | |
|
|
|
|
|
||
|
||||
|
כנראה שהוא התבלבל. הממוצע של n/e המוניות הראשונות קרוב מאד לממוצע הכללי, וזו לא חוכמה למצוא מישהו שזול מן הממוצע. כתבתי את התגובה הקודמת כי זו הפעם הראשונה שאני נתקל ב- n/3 בהקשר דומה. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |