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

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

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

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

תיאור אינטואיטיבי[עריכת קוד מקור | עריכה]

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

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

שימושים[עריכת קוד מקור | עריכה]

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

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

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

תיאור פורמלי[עריכת קוד מקור | עריכה]

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

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

function DFS(Start, Goal)
    push(Stack,Start)
    while Stack is not empty
        var Node := Pop(Stack)
        Color(Node, Grey)
        if Node = Goal
            return True
        for Child in Expand(Node)
            if Child.color = White
               push(Stack, Child)
        Color(Node, Black)