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

תוכן שנמחק תוכן שנוסף
←‏שימושים: שגיאת כתיב - נכתב אלגוריטם, המוסכמה היא אלגוריתם
←‏שימושים: הוספת יתרון
שורה 10:
 
==שימושים==
לאלגוריתם החיפוש לעומק יתרונות על [[אלגוריתם חיפוש לרוחב]] אם קיימת [[היוריסטיקה]] שמסוגלת לעזור לחיפוש. למשל, בחיפוש היציאה ממבוך, אם יופעל חיפוש לרוחב מאמצע המבוך תימצא היציאה רק בשלב האחרון של האלגוריתם. לעומת זאת, בחיפוש לעומק ניתן יהיה למצוא את היציאה כבר בתחילת ריצת האלגוריתם, עוד לפני שיהיה עליו לשוב על עקבותיו, ובפרט אם יש לו דרך טובה להעריך מהו הכיוון הנכון של היציאה. עוד יתרון הוא שסיבוכיות הזיכרון של אלגוריתם חיפוש לעומק היא לכל היותר לינארית ביחס לרמה בו הוא נמצא ברגע נתון וכמות הפיצולים הממוצעת, בעוד שבחיפוש לעומק היא אקספוננציאלית ביחס אליהם.
 
לעומת זאת, אלגוריתם חיפוש לעומק סובל מחסרונות כאשר הגרפים עליהם הוא פועל הם גדולים מאוד. בפרט, בגרפים בעלי מסלולים אינסופיים, האלגוריתם עלול שלא לעצור גם אם האיבר שהוא מחפש נמצא בגרף (כי המסלול שבו הוא יבחר עלול להיות מסלול אינסופי שבו האיבר שמחפשים לא נמצא, ואז האלגוריתם יתקדם ללא הפסקה באותו מסלול מבלי לחזור על עקבותיו., וזאת להבדיל מחיפוש לרוחב שמובטח בו שיגיע אל האיבר אותו מחפשים, עם זאת, {{אנ|Iterative deepening depth-first search|חיפוש לעומק איטרטיבי-מעמיק}} ימנע בעיה זו), וזאת להבדיל מחיפוש לרוחב, שמובטח לו שיגיע מתישהו אל האיבר שאותו מחפשים.
 
ניתן להשתמש באלגוריתם חיפוש לעומק בתור בסיס לאלגוריתמים רבים שפועלים על גרפים. למשל, מציאת [[רכיב קשיר היטב|רכיבים קשירים היטב]] בגרף, מציאת [[מסלול אוילרי]] ומעגלים בגרף או [[מיון טופולוגי]] שלו.