מגדלי האנוי

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

מגדלי האנוי הוא משחק חידה מתמטי. אף שמקורו בסוף המאה ה-19, הוא משמש להמחשת מושגי יסוד אחדים במדעי המחשב.

פתרון לשלוש דיסקיות

פתרון לארבע דיסקיות

תוכן עניינים

1 תיאור המשחק
2 מקור המשחק
3 פתרונות
- 3.1 הפתרון הרקורסיבי (הנסיגתי)
- 3.2 הפתרון האיטרטיבי (הלולאתי)
4 קישורים חיצוניים

[עריכה] תיאור המשחק

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

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

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

[עריכה] מקור המשחק

המשחק הומצא על ידי המתמטיקאי הצרפתי אדוארד לוקאס בשנת 1883. הוא הציג את המשחק בצורת אגדה על מקדש הינדי שבו הכהנים עוסקים בהעברת 64 דיסקיות על פי חוקי המשחק. על פי האגדה, כאשר הכהנים יסיימו את עבודתם, יגיע סוף העולם. אל חשש, גם אם הכהנים מעבירים את הדיסקיות בקצב של דיסקית בשנייה, ומשתמשים במספר ההעברות המינימלי האפשרי להשלמת המשימה, יידרשו להם 18,446,744,073,709,551,615 צעדים שיימשכו בערך 584,942,417,355 שנים לסיימו - למעלה מגילו המוערך של היקום.

[עריכה] פתרונות

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

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

מספר ההעברות המינימלי להעברת n דיסקיות הוא $2 n - 1$ , כלומר הגדלת אורך הקלט ב-1 מביאה להכפלת הזמן הנחוץ לפתרון הבעיה, ולכן זהו אלגוריתם בעל סיבוכיות מעריכית $\ O(2^n)$ , - לבעיה אין פתרון "יעיל".

[עריכה] הפתרון הרקורסיבי (הנסיגתי)

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

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

בצורה פורמלית, האלגוריתם יוגדר כך:

העבר-דיסקיות (קלט: מספר-דיסקיות, מוט-מקור, מוט-ביניים, מוט-יעד)

אם מספר-דיסקיות=1 העבר את הדיסקית ממוט-מקור למוט-יעד.
אחרת, בצע:
1. העבר-דיסקיות (מספר-דיסקיות פחות אחת, מוט-מקור, מוט-יעד, מוט-ביניים): מעביר את כל הדיסקיות פרט לתחתונה למוט הביניים.
2. העבר-דיסקיות (1, מוט-מקור, מוט-ביניים, מוט-יעד) : מעביר את הדיסקית התחתונה למוט היעד.
3. העבר-דיסקיות (מספר דיסקיות פחות אחת, מוט-ביניים, מוט-מקור, מוט-יעד): מעביר את כל הדיסקיות שעל מוט הביניים למוט היעד.

[עריכה] הפתרון האיטרטיבי (הלולאתי)

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

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

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

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

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