קרוסקל את פרים - בוני מבוכים בע"מ

נתחיל מהשורה התחתונה - בפוסט הזה אני רוצה להסביר איך אפשר לכתוב תוכנית מחשב שמייצרת מבוכים כמו זה:

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

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

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

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

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

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

הדרך הטובה יותר היא לתחזק מבנה נתונים שמכיל מידע שעונה על השאלה שלנו, והמחיר של ביצוע פעולות מהסוג שמעניין אותנו עליו הוא זול יחסית. כל מה שאנחנו צריכים לדעת הוא בהינתן שתי משבצות, האם יש מסלול ביניהן; לא חשוב לנו למצוא את המסלול עצמו, רק לדעת אם הוא קיים או לא. לכן מספיק לנו לתחזק מבנה נתונים שמכיל קבוצות זרות, כשכל תא במבוך שייך לאחת מהקבוצות, ושיש מסלול בין שני תאים אם ורק אם הם שייכים לאותה קבוצה. כעת, כדי לבדוק אם קיר הוא “חוקי להסרה” אנחנו בודקים אם שני התאים שסמוכים אליו לא נמצאים כרגע באותה קבוצה; אם הם כן, לא מסירים את הקיר; ואם הם לא, מסירים את הקיר ואז מאחדים את הקבוצות של שני התאים הללו. אם כן, הפעולות שאני דורש ממבנה הנתונים שלי הן למצוא לאיזו קבוצה שייך איבר נתון, ולאחד שתי קבוצות; לכן מבנה הנתונים הרלוונטי נקרא לפעמים Union/Find, ולפעמים סתם Disjoint Sets Data Structure. מסתבר שמבנה נתונים כזה קל מאוד לממש, עם התחכמות או שתיים שהופכות אותו ליעיל מאוד. גם את זה אציג בהמשך באופן פורמלי, כולל קוד.

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

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

קרוסקל פרים