2.2.1. חיפוש לעומק עם הגבלת עומקנשים לב כי האלגוריתם עלול להיתקע במקרה שבגרף שלנו קיים ענף אינסופי או מעגל. מכאן ניתן להסיק: אלגוריתם DFS אינו שלם. בגלל הבעיות הנ"ל משתמשים בד"כ בהגבלה על עומק החיפוש. שלמות: בגלל הגבלת העומק מובטח לנו שהאלגוריתם יעצור. נסמן: סיבוכיות זיכרון: נסמן: מתקיים: סיבוכיות הזיכרון הינה: סיבוכיות זמן: במקרה הגרוע ביותר האלגוריתם מייצר עץ מלא בעומק יעילות: האלגוריתם יעיל כאשר קיימים מצבי מטרה רבים המפוזרים אחיד על פני המרחב. חיפוש לעומק בגרף: ניתן להוסיף לאלגוריתם רשימה של צמתים שפותחו בצורה דומה לזו של חיפוש לרוחב. עם זאת, הוספה זו תבטל את יתרונו המרכזי של אלגוריתם זה – זיכרון ליניארי לעומת מערכי. DFS-L (state, goal-test,depth) |
תוכן העניינים:
קישורים רלוונטיים:שיתוף: |
אבל הוא עדיין לא נפתח...