בינה מלאכותית

ספר אלקטרוני מאת: ניר אדר

2.2.1. חיפוש לעומק עם הגבלת עומק

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

מכאן ניתן להסיק: אלגוריתם DFS אינו שלם.

בגלל הבעיות הנ"ל משתמשים בד"כ בהגבלה על עומק החיפוש.

שלמות: בגלל הגבלת העומק מובטח לנו שהאלגוריתם יעצור.

נסמן: $plot:\[D\]$ - הגבלת העומק , $plot:\[L\]$ - עומק הפתרון. האלגוריתם שלם כאשר מתקיים $plot:\[D \geqslant L\]$ . האלגוריתם אינו שלם כאשר $plot:\[D < L\]$ .

סיבוכיות זיכרון: נסמן: $plot:\[b\]$ מקדם הסיעוף, $plot:\[d\]$ העומק הנוכחי, $plot:\[D\]$ הגבלת העומק, $plot:\[b \cdot d\]$ מספר הצמתים שנשמר בזיכרון בכל רגע.

מתקיים: סיבוכיות הזיכרון הינה: $plot:\[O\left( {b \cdot D} \right)\]$ . במקרה הגרוע ביותר.

סיבוכיות זמן: במקרה הגרוע ביותר האלגוריתם מייצר עץ מלא בעומק $plot:\[D\]$ ולכן סיבוכיות הזמן היא $plot:\[O\left( {{b^D}} \right)\]$ .

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

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

DFS-L (state, goal-test,depth)
if goal-test(state) then return ((state))
else
    if depth=0 then return FAIL
    for c in succ(state)
      solution $plot:\[ \leftarrow \]$ DFS(c, goal-test,depth-1)
      if solution $plot:\[ \ne \]$ FAIL then
        return(state || solution)
    return(FAIL)

DFS-L-search (problem)
DFS(problem[init-state], problem[goal-test], L)