אלגוריתם חיפוש לעומק

סדר סריקת הקודקודים בחיפוש לעומק

במדעי המחשב, אלגוריתם חיפוש לעומק (באנגלית: Depth-first search, ראשי תיבות: DFS) הוא אלגוריתם המשמש למעבר על גרף או לחיפוש בו.

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

תיאור אינטואיטיבי

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

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

שימושים

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

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

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

אלגוריתם זה נמצא בשימוש באופטימיזציה הרמונית.

תיאור פורמלי

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

קטע הקוד הבא הוא פסאודו קוד.

function DFS(Start, Goal)
        Color(Start, Grey)
        if Start = Goal
            return True
        for Child in Expand(Node)
            if not Colored(Child)
                if DFS(Child, Goal)=True
                    return True
        Color(Start, Black)
        return False

ראו גם

• אלגוריתם חיפוש לרוחב
• אלגוריתם חיפוש A*

קישורים חיצוניים

מדיה וקבצים בנושא אלגוריתם חיפוש לעומק בוויקישיתוף

• אלגוריתם חיפוש לעומק, באתר MathWorld (באנגלית)

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

אלגוריתם חיפוש לעומק30366247