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

מתוך ויקיפדיה, האנציקלופדיה החופשית

במדעי המחשב, אלגוריתם חיפוש לעומק (DFS) הוא אלגוריתם המשמש למעבר על גרף או לחיפוש בו.

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

[עריכה] תיאור אינטואיטיבי

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

[עריכה] שימושים

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

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

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

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

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

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

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