ברוכים הבאים לשיעור בנושא "חיפוש בלתי מושכל" – אחד מעמודי התווך של תחום הבינה המלאכותית. יחידה זו עוסקת באלגוריתמים לפתרון בעיות באמצעות חיפוש במרחב מצבים, כאשר אין לנו ידע מוקדם (היוריסטיקה) שיכול לכוון את החיפוש. הבנה מעמיקה של אלגוריתמים אלו, יתרונותיהם, חסרונותיהם ומאפייניהם התאורטיים (שלמות, אופטימליות, סיבוכיות זמן ומקום) היא קריטית להצלחה בקורס ובמבחן.
יסודות החיפוש במרחב מצבים
בעיות רבות בבינה מלאכותית ניתנות לניסוח כבעיות חיפוש במרחב מצבים. כדי לפתור בעיה כזו, עלינו למצוא מסלול ממצב התחלתי נתון למצב יעד.
האלגוריתם הכללי לחיפוש
כל אלגוריתמי החיפוש הבלתי מושכל פועלים על פי עקרונות דומים:
- שמירה על רשימת מצבים "פתוחים" (Frontier/Open List) שטרם נבדקו, אך ניתנים להרחבה.
- שמירה על רשימת מצבים "סגורים" (Explored/Closed List) שכבר נבדקו והורחבו, כדי למנוע חזרות וחיפוש אינסופי.
- בכל איטרציה, בחירת מצב מהרשימה הפתוחה, הרחבתו (יצירת מצבים חדשים באמצעות אופרטורים), והוספת המצבים החדשים לרשימה הפתוחה (אם אינם ברשימה הסגורה).
- ההבדל בין האלגוריתמים השונים טמון באופן בחירת המצב הבא להרחבה מהרשימה הפתוחה.
אלגוריתמי חיפוש בלתי מושכל מרכזיים
ארבעת האלגוריתמים המרכזיים בקטגוריה זו הם BFS, DFS, UCS ו-IDS. לכל אחד מהם מאפיינים ייחודיים המשפיעים על ביצועיו.
חיפוש לרוחב (BFS - Breadth-First Search)
מנגנון: מרחיב את כל הצמתים בעומק d לפני שהוא מרחיב צמתים בעומק d+1. משתמש בתור (Queue) לניהול הרשימה הפתוחה (FIFO).
שלמות: כן, אם קיים פתרון והמרחב סופי (או אם עלות כל צעד חיובית). ימצא את הפתרון בעל המספר המינימלי של צעדים.
אופטימליות: כן, אם עלות כל צעד זהה (לדוגמה, 1). במקרה כזה, הפתרון הראשון שיימצא יהיה הקצר ביותר.
סיבוכיות זמן: O(bd), כאשר b הוא גורם ההסתעפות ו-d הוא עומק הפתרון.
סיבוכיות מקום: O(bd), מכיוון ששומר את כל הצמתים בעומק d בתור.
חיפוש לעומק (DFS - Depth-First Search)
מנגנון: מרחיב את הענף העמוק ביותר האפשרי לפני חזרה לאחור. משתמש במחסנית (Stack) לניהול הרשימה הפתוחה (LIFO).
שלמות: לא, אם קיים מסלול אינסופי או לולאה במרחב המצבים, הוא עלול לא למצוא פתרון.
אופטימליות: לא, יכול למצוא פתרון ארוך מאוד לפני פתרון קצר יותר.
סיבוכיות זמן: O(bm), כאשר m הוא עומק מקסימלי של העץ.
סיבוכיות מקום: O(bm), הרבה יותר יעיל מ-BFS מבחינת מקום.
חיפוש בעלות אחידה (UCS - Uniform Cost Search)
מנגנון: מרחיב תמיד את הצומת בעל עלות המסלול הנמוכה ביותר מהמצב ההתחלתי. משתמש בתור עדיפויות (Priority Queue) לניהול הרשימה הפתוחה.
שלמות: כן, אם עלות כל צעד חיובית (או אפסית, בתנאי שאין לולאות בעלות אפס). ימצא את הפתרון בעל העלות הנמוכה ביותר.
אופטימליות: כן, תמיד מוצא את הפתרון האופטימלי (בעל העלות הנמוכה ביותר).
סיבוכיות זמן: O(bC*/ε), כאשר C* היא עלות הפתרון האופטימלי ו-ε היא עלות הצעד המינימלית.
סיבוכיות מקום: O(bC*/ε), דומה ל-BFS במקרים רבים.
חיפוש איטרטיבי מעמיק (IDS - Iterative Deepening Search)
מנגנון: שילוב של DFS ו-BFS. מבצע סדרת חיפושי DFS עם עומק מוגבל הולך וגדל (מ-0 ועד d). בכל איטרציה, אם הפתרון לא נמצא, מגדיל את מגבלת העומק ומבצע DFS מחדש.
שלמות: כן, כמו BFS.
אופטימליות: כן, כמו BFS (אם עלות כל צעד זהה).
סיבוכיות זמן: O(bd), למרות החיפושים החוזרים, רוב העבודה מתבצעת בעומק d האחרון.
סיבוכיות מקום: O(bd), כמו DFS, יעיל מאוד מבחינת מקום.
שאלות לדיון
- הסבירו מדוע חיפוש לרוחב (BFS) הוא שלם ואופטימלי כאשר עלות כל צעד היא 1, אך חיפוש לעומק (DFS) אינו בהכרח שלם או אופטימלי.
- תארו מצב שבו חיפוש בעלות אחידה (UCS) ימצא פתרון מהר יותר מחיפוש לרוחב (BFS), ומצב שבו BFS עשוי להיות עדיף.
- הסבירו את היתרון המרכזי של חיפוש איטרטיבי מעמיק (IDS) על פני BFS ו-DFS בנפרד, בהתחשב במגבלות זיכרון וזמן.
- כיצד ניתן להתמודד עם מצבים חוזרים (repeated states) במרחב המצבים, ואיזה מבנה נתונים משמש בדרך כלל למטרה זו?
נקודות לתשובת מודל
לשאלה: "הסבירו מדוע חיפוש לרוחב (BFS) הוא שלם ואופטימלי כאשר עלות כל צעד היא 1, אך חיפוש לעומק (DFS) אינו בהכרח שלם או אופטימלי."
- שלמות BFS: BFS מבטיח שלמות מכיוון שהוא בודק את כל הצמתים בעומק d לפני שהוא ממשיך לעומק d+1. אם קיים פתרון בעומק סופי, BFS ימצא אותו בסופו של דבר. הוא לא יכול להיתקע בלולאה או במסלול אינסופי מבלי לבדוק ענפים אחרים.
- אופטימליות BFS (עלות 1): כאשר עלות כל צעד היא 1, BFS מוצא את המסלול הקצר ביותר (מספר צעדים מינימלי). מכיוון שהוא מרחיב את העץ שכבה אחר שכבה, הפתרון הראשון שיימצא יהיה בהכרח בעל העומק הנמוך ביותר, ולכן בעל העלות הנמוכה ביותר.
- חוסר שלמות DFS: DFS עלול לא להיות שלם במרחבי מצבים עם מסלולים אינסופיים או לולאות. הוא ימשיך לחקור ענף אחד עד הסוף, ועלול להיתקע בו לנצח מבלי למצוא פתרון קיים בענף אחר.
- חוסר אופטימליות DFS: DFS אינו אופטימלי מכיוון שהוא עשוי למצוא פתרון בעומק רב (ועלות גבוהה) לפני שהוא בודק ומגלה פתרון קצר וזול יותר שנמצא בענף אחר, קרוב יותר למצב ההתחלתי.
- פתרון לבעיות DFS: ניתן לשפר את DFS על ידי הגבלת עומק החיפוש (DFS עם הגבלת עומק) או על ידי שימוש ברשימת מצבים סגורים למניעת לולאות, אך זה עדיין לא מבטיח אופטימליות.