Tip:
Highlight text to annotate it
X
הנה התשובות.
חיפוש לרוחב, כמו ששמו רומז, מרחיב קוקודים בסדר הבא:
אחד, 2, 3, 4, 5, 6, 7.
כך שהוא עובד מצד לצד, פס אחד כל פעם, חיפוש לרוחב.
נאם הוא אופטימלי?
טוב, הוא תמיד מרחיב את המסלול הקצר ביותר,
כך שבכל מקום שתתחבא המטרה, הוא הולך למצוא אותה ע"י בחינת
מסלולים שאינם ארוכים יותר בלבד. אז, אכן, הוא אופטימלי.
בחיפוש זול, קודם נרחיב את המסלול באורך 0,
אחר כך את האורך 2,
עכשיו את המסלול באורך 4, המסלול באורך 5,
המסלול באורך 6, המסלול באורך 7, המסלול באורך 8.
וכמו שראינו, הוא בוודאות ימצא את המסלול הזול מכולם.
זאת בהנחה שעלות של כל צעד כשלעצמו אינה שלילית.
חיפוש לעומק מנסה להגיע הכי עמוק שהוא יכול קודם כל,
אז הוא הולך 1, 2, 3, ואז חזרה למעלה, 4,
אז חזרה למעלה, 5, 6, 7.
ואתם יכולים לראות שהוא בהכרח מוצא את המסלול הקצר מכולם.
בואו נגיד שהיו מטרות במקום החמישי והשלישי.
הוא ימצא את המסלול הארוך יותר אל המקום השלישי וימצא שם את המטרה.
ולא ימצא את המטרה שבמקום החמישי.
אז, הוא אינו אופטימלי.