חיפוש לעומק איטרטיבי מעמיק
חיפוש לעומק איטרטיבי מעמיק (באנגלית: Iterative deepening depth-first search) הוא אלגוריתם חיפוש בגרף שנועד לאפשר חיפוש לרוחב בדומה לאלגוריתם חיפוש לרוחב, אך ללא דרישות הזיכרון הגבוהות שלו, על ידי שימוש חוזר במתודולוגיית אלגוריתם חיפוש לעומק לעומק גדל והולך בכל איטרציה.
חיפוש לעומק וחיפוש לרוחב
חיפוש לעומק
ערך מורחב – חיפוש לעומק
חיפוש לעומק הוא אלגוריתם המתחיל את החיפוש משורש בגרף ומתקדם לאורך הגרף עד אשר הוא נתקע, לאחר מכן הוא חוזר על עקבותיו עד שהוא יכול לבחור להתקדם לצומת אליו טרם הגיע. אחד מיתרונותיו הוא בכך שסיבוכיות הזיכרון בו הוא משתמש ליניארית ביחס לעומק המסלול אותו הוא בודק באותו שלב, כי הוא רק נדרש לזכור איך הגיע לכל צומת ואילו בנים של כל צומת סרק כבר. חסרונותיו הם שאף אם קיים פתרון במרחק קטן יותר מהקדקוד, אם האלגוריתם לא פנה לכיוונו בהתחלה יכול לעבור הרבה זמן אם העץ מאוד עמוק עד שהוא יימצא, ואף לא לעצור אם העומק אינסופי. כמו כן המסלול הראשון אותו מוצא האלגוריתם לעבר פתרון לא מובטח שהוא המסלול הקצר ביותר אל פתרון.
חיפוש לרוחב
- ערך מורחב – חיפוש לרוחב
האלגוריתם סורק בצורה שיטתית את העץ רמה אחרי רמה עד למציאת פתרון, וזאת על ידי הכנסת כל הבנים של כל צומת שנסרק לתור, ועל ידי כך צמתים מרמה כלשהי יסרקו לאחר שהצמתים מהדרגה שלפניה נסרקו. יתרונותיו של אלגוריתם זה הם שהאלגוריתם ימצא את המסלול הקצר ביותר אל הפתרון, בסיבוכיות זמן אופטימלית. אחד מחסרונותיו הם שסיבוכיות המקום של התור היא כמספר הצמתים שבעומק הנוכחי, שהיא אקספוננציאלית ביחס לעומק (בהנחה שיש בממוצע יותר מבן אחד לכל צומת).
אלגוריתם חיפוש לעומק איטרטיבי מעמיק
האלגוריתם עובד באיטרציות בכל איטרציה i מריצים את אלגוריתם חיפוש לעומק שיסרוק את כל העץ עד לעומק i, אם הפתרון נמצא הוא יחזיר אותו, אם לא נשארה עוד רמה לפתח הוא יחזיר שאין פתרון, אחרת הוא עובר לאיטרציה i+1.
האלגוריתם מבטיח שאם הפתרון בעומק המינימלי נמצא בעומק k הוא יימצא באיטרציה k מאחר שעד לאיטרציה זו האלגוריתם לא סורק בעומקים k ומעלה ובעומק k הצומת עם הפתרון תיסרק ותוחזר. סיבוכיות הזיכרון באיטרציה i ליניארית ב-i כי מריצים חיפוש לעומק עד עומק i. סיבוכיות הזמן פולינומית בכמות הצמתים עד עומק k.
אלגוריתם A* איטרטיבי מעמיק
בדומה לאלגוריתם חיפוש לרוחב, קיים אלגוריתם A* מקביל בעל תור עדיפויות כדי לפתור בעיות חיפוש בגרף ממושקל, שגם בו קיימת בעיה של זיכרון. כדי לפתור בעיה זו משתמשים באלגוריתם חיפוש לעומק איטרטיבי מעמיק IDA* כשהעומק המוגדר בכל איטרציה הוא העומק הכי נמוך של בן שפותח שהיה עמוק יותר מהעומק 'המותר' באיטרציה הקודמת.
29432550חיפוש לעומק איטרטיבי מעמיק