בעיית הנהגים הגחמנים

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

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

הבעיה[עריכת קוד מקור | עריכה]

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

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

פונקציה, המתאימה את הנהגים למקומות החניה, כך שלכל נהג יש מקום חניה, קרויה פונקציית חניה. הדיון בפונקציות כאלה החל במאמר
A.G. Konheim, B. Weiss, An occupancy discipline and applications, SIAM J. Applied Math. 14 (1966) 1266-1274.

דוגמה[עריכת קוד מקור | עריכה]

נניח שהנהג הראשון מעדיף את המקום 2, ושני הנהגים הבאים מעדיפים את המקום 1. הנהג הראשון יתפוס את המקום 2; אחריו יתפוס הנהג השני את המקום 1; הנהג השלישי לא יוכל לחנות במקום המועדף עליו, אבל יוכל לחנות במקום זאת במקום 3. הבחירות 2,1,1 מאפשרות חניה מסודרת.

לעומת זאת, אם הנהג הראשון מעדיף את המקום 1 ושני האחרים מעדיפים את 3, אז הראשון יחנה במקום 1, השני יסע למקום 3 ויחנה בו, והשלישי, שיסע בתחילה למקום 3, יאלץ לוותר ולעזוב. הבחירות 1,3,3 אינן מאפשרות חניה מסודרת.

פתרון הבעיה[עריכת קוד מקור | עריכה]

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

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

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

רשימה של העדפות (כמתואר מלמעלה) היא פונקציית חנייה, אם ורק אם אף נהג אינו חונה במקום חנייה ה:

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

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

כלומר, כל פונקציית חנייה מופיעה ברשימות של ההעדפות האפשריות פעמים:

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

כעת נסתכל על מספר הרשימות של ההעדפות האפשריות עם מקום החנייה הנוסף: ישנן כאלה (כי לכל נהג יש אפשרויות למקום מועדף, ויש נהגים.

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