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

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

האם תוכלו למצוא את הדרך החוצה?

אתם בוחנים את מפת המבוך ורואים לשמחתכם שכל הדלתות והמעברים שבו הם דו-כיווניים: אפשר תמיד לחזור אחורה. אתם נושמים לרווחה - הרי בשנת 2008 הוכיח עומר ריינגולד [1] שניתן לפתור את המבוך בתנאים הללו. 

מרגש, נכון? עכשיו מספיק עם הדרמה.

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

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

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

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

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

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

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

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

ובכן, לצערנו איננו יודעים אם אפשר לפתור את הבעיה בשימוש בזיכרון לוגריתמי. אנחנו כן יודעים שאפשר לבדוק בזיכרון לוגריתמי אם מסלול נתון הוא אכן מסלול מהכניסה ליציאה. הקשר בין בעיית הבדיקה הזו לבעיה המקורית הוא אותו קשר מפורסם בין P ל-NP (ראו [3]).

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

עם זאת, בעיות רבות הן לא מכוונות - כלומר, אפשר לחזור אחורה. מכאן עולה השאלה, האם אפשר לפתור את בעיית הישיגות הלא-מכוונת, בשימוש בזיכרון לוגריתמי?

הבעיה הזו סיקרנה חוקרים החל משנות ה-80 [4], בפרט כי אפשר לתאר בעזרתה בעיות רבות. אוסף הבעיות האלו, שנקרא "מחלקת סיבוכיות", זכה לשם SL (מגיע מ- Symmetric Logarithmic Space).

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

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

עריכה: ינון קחטן

הערות והרחבות:

[1]. Reingold, Omer. "Undirected connectivity in log-space." Journal of the ACM (JACM) 55.4 (2008): 1-24.

[2]. תורת הגרפים 

[3]. P=NP?   

[4]. Lewis, Harry R., and Christos H. Papadimitriou. "Symmetric space-bounded computation." Theoretical Computer Science 19.2 (1982): 161-187.