מבוכים ומחשבים

 

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

 

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

 

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

 

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

 

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