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

חדשות מדע בשפה ידידותית
01.03.2005

שתף

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

 

 דגל שחור, דגל לבן

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

 

 אישי

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

שתף