חיפוש לעומק איטרטיבי מעמיק – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
קישור פנימי תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
סקריפט החלפות (ליניארי), החלפה (הוא) |
||
שורה 2:
==חיפוש לעומק וחיפוש לרוחב==
===חיפוש לעומק===
{{ערך מורחב|חיפוש לעומק}}
חיפוש לעומק הוא אלגוריתם המתחיל את החיפוש משורש בגרף ומתקדם לאורך הגרף עד אשר הוא נתקע, לאחר מכן הוא חוזר על עקבותיו עד שהוא יכול לבחור להתקדם לצומת אליו טרם הגיע. אחד מיתרונותיו הוא בכך שסיבוכיות הזיכרון בו הוא משתמש
===חיפוש לרוחב===
שורה 19 ⟵ 18:
האלגוריתם עובד באיטרציות בכל איטרציה i מריצים את אלגוריתם חיפוש לעומק שיסרוק את כל העץ עד לעומק i, אם הפתרון נמצא הוא יחזיר אותו, אם לא נשארה עוד רמה לפתח מחזיר שאין פתרון, אחרת עובר לאיטרציה i+1.
האלגוריתם מבטיח שאם הפתרון בעומק המינימלי נמצא בעומק k הוא יימצא באיטרציה k מאחר שעד לאיטרציה זו האלגוריתם לא סורק בעומקים k ומעלה ובעומק k הצומת עם הפתרון תיסרק ותוחזר. סיבוכיות הזיכרון באיטרציה i
[[קטגוריה : אלגוריתמי חיפוש]]
|