מה הוא סידור האולם האולטימטיבי?
מה הוא, לפי דעתכם, הדרך הכי טובה לסדר אנשים בתוך אולם קולנוע כאשר ניתנת לכם כמות מוגבלת של מקום, כמות של אנשים קטנה ממש מכמות הכסאות ואתם רוצים לסדר לכל אדם נוסף שמגיע את המקום הכי טוב שקיים באותו הרגע?
לשם הדיון, נניח כי קיים לנו אולם של 11 שורות שכל אחת מכילה 11 מושבים (בשביל המספר הראשוני הנחמד שיאפשר לנו מושב מרכזי במיוחד) ויש לכם זרם באורך n של אנשים כאשר n << 121.
אני מניח שהסידור שרוב האנשים יחשבו עליו הוא לשים את הבן אדם הראשון בכיסא המרכזי, את השניים הבאים מעליו ומתחתיו, את השניים הבאים מצדדיו, את הארבעה הבאים להשלים את הפינות וחוזר חלילה כך שנוצר גוש אנשים במרכז האולם.
אני חושב אחרת, האדם הראשון יישב במושב האמצעי בשורה השנייה או השלישית. הבא יישב מאחוריו, השניים הבאים מצדדיו, השניים הבאים מעל השניים הקודמים וכן הלאה עד שמצטברת פירמידה קטנה שמבוססת בשורה השנייה או השלישית ואם ראש הפירמידה כבר יושב מעבר לשורה החמישית אז צריך להוריד אנשים לשורות התחתונות.
מה דעתכם?
Posted in Practice, Thinking Out Loud by Eran with 7 comments.
למה להתעלל באנשים שהגיעו ראשונים? שורה שניה ושלישית רחוקות מלהיות אופטימליות.
השיטה של בניית מעגל סביב המרכז המועדף והרחבתו היא הכי טובה ומתגמלת את אלו שהגיעו מוקדם.
המרכז המועדף על ידי מי? זאת בדיוק השאלה.
ע”י הרוב- כשמזמינים כרטיסים באינטרנט מקולנוע שנותן לך לבחור בעצמך את מקומות הישיבה אתה מייד רואה את העדפת הרוב לעיגול במרכז והתפשרות על הצדדים והשורות הראשונות. סלקציה זו למקומות ישיבה נובעת רק מהעדפות אישיות של בחירה חופשית לפי diminishing returns.
זה מה שהם רוצים. אבל מה את רוצה?
אמצע כמובן, נמוך מידי גורם לי שרירי צוואר תפוסים כואבים וקשה לחשוב עם כאב צוואר, גבוה מידי פחות מפריע בדרך כלל. אמצע מאפשר שקיעה בחווית הסרט בצורה האופטימלית לטעמי.
נראה שפונקציית המטרה של ניהאו היא: באמצא השורה הכי אמצעית שאפשר כשנסוגים רק כלפי מעלה. בהנתן חוסר מקום אמצעי בשורה שווה או גבוהה מהאמצע אז עדיף מקום בצד של שורה כמה שיותר נמוכה אבל לא נמוכה מהאמצע.
אפשר לנחש שלרוב האנשים פונקציות מטרה דומות לזו ולא לשני הפתרונות האחרים שהצגת. למרות זאת, יש מספיק אנשיפ שיעדיפו שורות נמוכות ואפילו כאלה שיעדיפו כיסאות בצד (או בגלל פסיכוזות כאלה או אחרות או פשוט כדי שיהיה קל לצאת לשרותים).
בהנתן אולם כלשהוא וזרם של אנשים, האלגוריתם הכי טוב הוא להציג לכל אדם מפה של האולם שבה מוצגים הכסאות ואפשר לבחור איזה כסא את רוצה. הפתעה! זה מה שקולנועים בארץ עושים.
הבעיה א השיטה הזאת היא שמי שמגיע ראשון נהנה יותר כשאולי אתה רוצה למטב לפונקצית המטרה המשולבת.
האולם לא ממש מוצג אלא אם כן קונים מראש או באוטומטים. צריך באמת לעשות את זה יותר. בכל מקרה, אני לא מתכוון לכתוב את ה-ICUP הבא.