מבוא לבינה מלאכותית — מרחב למידה אישי

ברוכים הבאים לשיעור בנושא "חיפוש מושכל" בקורס "מבוא לבינה מלאכותית". יחידה זו מתמקדת בשיטות חיפוש המנצלות ידע ספציפי לבעיה כדי למצוא פתרונות בצורה יעילה יותר משיטות חיפוש בלתי מושכלות. נלמד כיצד היוריסטיקות ופונקציות הערכה מאפשרות לאלגוריתמים כמו A* וחיפוש חמדן לנווט במרחב המצבים ביעילות, תוך הבנת התכונות הקריטיות שלהן והשפעתן על אופטימליות ושלמות הפתרון.

יסודות החיפוש המושכל

בניגוד לחיפוש בלתי מושכל (כמו BFS או DFS) שבוחן מצבים באופן "עיוור", חיפוש מושכל משתמש בידע נוסף על הבעיה כדי להנחות את תהליך החיפוש. ידע זה מתבטא לרוב באמצעות היוריסטיקות.

היוריסטיקה (Heuristic): פונקציה, המסומנת לרוב כ-h(n), המעריכה את העלות המשוערת מהמצב הנוכחי n למצב המטרה. היוריסטיקה טובה מספקת הערכה קרובה לעלות האמיתית, אך אינה חייבת להיות מדויקת.

פונקציית הערכה (Evaluation Function): פונקציה, המסומנת לרוב כ-f(n), המעריכה את "הטוב" של מצב מסוים n. באלגוריתמי חיפוש, היא משמשת לקביעת סדר הרחבת הצמתים. עבור אלגוריתם A*, פונקציית ההערכה היא f(n) = g(n) + h(n), כאשר g(n) היא העלות הידועה מהמצב ההתחלתי למצב n.

היוריסטיקות הן הליבה של חיפוש מושכל, ומאפשרות לאלגוריתמים להתמקד בנתיבים מבטיחים ולהימנע מבדיקה מיותרת של נתיבים פחות סבירים.

אלגוריתמי חיפוש מרכזיים

נכיר שני אלגוריתמי חיפוש מושכלים בולטים המשתמשים בהיוריסטיקות:

חיפוש חמדן (Greedy Best-First Search)

אלגוריתם זה מרחיב תמיד את הצומת שנראה "הקרוב ביותר" למטרה, כפי שמוערך על ידי הפונקציה ההיוריסטית h(n). הוא מתמקד בהקטנת המרחק המשוער למטרה בכל צעד, ללא התחשבות בעלות שהצטברה עד כה. הוא מהיר ויעיל במקרים רבים, אך אינו מבטיח מציאת הפתרון האופטימלי או אפילו שלמות (מציאת פתרון אם קיים).

אלגוריתם A* (A* Search)

A* נחשב לאחד מאלגוריתמי החיפוש המושכלים היעילים והנפוצים ביותר. הוא משלב את העלות שהצטברה עד כה (g(n)) עם הערכה היוריסטית של העלות הנותרת למטרה (h(n)). פונקציית ההערכה שלו היא f(n) = g(n) + h(n). A* מבטיח למצוא את הפתרון האופטימלי (הזול ביותר) אם ההיוריסטיקה שלו מקיימת תנאים מסוימים.

היוריסטיקות ועקרונות אופטימליות

האיכות והתכונות של ההיוריסטיקה קריטיות לביצועי אלגוריתם A*.

קבילות (Admissibility): היוריסטיקה h(n) נקראת קבילה אם היא לעולם אינה מעריכה יתר על המידה את העלות האמיתית מהמצב n למצב המטרה. כלומר, h(n) ≤ h*(n) לכל n, כאשר h*(n) היא העלות האמיתית המינימלית מ-n למטרה. היוריסטיקה קבילה מבטיחה ש-A* ימצא פתרון אופטימלי.

עקביות (Consistency): היוריסטיקה h(n) נקראת עקבית אם לכל צומת n ולכל צומת n' שניתן להגיע אליו מ-n בצעד אחד בעלות c(n, n'), מתקיים: h(n) ≤ c(n, n') + h(n'). תנאי זה חזק יותר מקבילות, ומשמעותו שהערכת העלות למטרה לא יורדת ביותר מעלות הצעד עצמו. היוריסטיקה עקבית היא תמיד קבילה (בגרפים עם עלויות קשתות אי-שליליות), והיא מאפשרת ל-A* לעבוד ביעילות רבה יותר (אין צורך לעדכן צמתים שכבר הורחבו).

עקרון האופטימליות (Optimality Principle): עקרון זה קובע כי כל תת-נתיב של נתיב אופטימלי הוא גם נתיב אופטימלי. בהקשר של A*, עקרון זה מיושם באופן מובנה: אם A* מוצא נתיב אופטימלי לצומת מסוים, הוא לא ימצא נתיב טוב יותר לאותו צומת מאוחר יותר, בתנאי שההיוריסטיקה עקבית.

חשיבות קבילות ועקביות במבחן: הבנה מעמיקה של קבילות ועקביות היא קריטית לבחינה. שאלות רבות בוחנות את היכולת לזהות האם היוריסטיקה נתונה היא קבילה/עקבית, ולהסביר מדוע תכונות אלו מבטיחות את אופטימליות הפתרון של A*. זכרו: קבילות מספיקה לאופטימליות של A*, ועקביות היא תנאי חזק יותר המאפשר גם את יעילות האלגוריתם.

שאלות לדיון

הסבירו את ההבדל בין חיפוש חמדן לאלגוריתם A* מבחינת פונקציית ההערכה, שלמות ואופטימליות.
תארו מצב שבו היוריסטיקה קבילה אינה עקבית. האם A* עדיין ימצא פתרון אופטימלי במקרה כזה? נמקו.
כיצד עקרון האופטימליות בא לידי ביטוי באלגוריתם A*, ומדוע הוא חשוב להבטחת אופטימליות הפתרון?
תנו דוגמה להיוריסטיקה עבור בעיית "שמונה המלכות" (Eight Queens) והסבירו האם היא קבילה.

נקודות לתשובת מודל

הגדרות מדויקות של היוריסטיקה, פונקציית הערכה, חיפוש חמדן, A*, קבילות, עקביות ועקרון האופטימליות.
השוואה ברורה בין חיפוש חמדן ל-A* תוך התייחסות ל-f(n), g(n), h(n), שלמות ואופטימליות.
הסבר על הקשר בין קבילות/עקביות היוריסטיקה לאופטימליות של A*.
הבנת המשמעות של עקרון האופטימליות בהקשר של חיפוש והשפעתו על A*.
יכולת לנתח היוריסטיקה נתונה ולקבוע את תכונותיה (קבילה/עקבית).

מצאתם טעות או שחסר משהו?