בינה מלאכותית

1.2. אלגוריתמים לחיפוש במרחב מצבים

• אלגוריתמי החיפוש מתחילים מהמצב ההתחלתי.
• בתחילה הגרף מוגדר רק בצורה לא מפורשת.
• אלגוריתמי החיפוש חושפים בהדרגה חלקים מהגרף והופכים אותו לגרף מפורש.

פתרון לבעיית חיפוש

הפתרון לבעית חיפוש היא סדרת אופרטורים המובילים מהמצב ההתחלתי למצב סופי.

פעולת פיתוח צומת

הפעולה הבסיסית של אלגוריתמי החיפוש היא פעולת פיתוח צומת.

פעולה זו מקבלת צומת ומחזירה את קבוצת הצמתים העוקבים.

אסטרטגיות חיפוש

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

מבנה הנתונים צומת

צומת הוא מבנה נתונים המכיל: state – המצב במרחב המצבים אותו מייצג הצומת. parent – מצביע לצומת ממנו נוצר הצומת הנוכחי.

צומת מייצג שלב בתהליך החיפוש של הסוכן. כל צומת מייצג מצב אולם ייתכן שכמה צמתים ייצגו את אותו המצב.

פונקציות עזר

path – פרוצדורה המקבלת צומת, עוקבת אחרי מצביעי ההורים עד שמגיעה לצומת ההתחלה ומחזירה את המסלול.

op-path - פרוצדורה המקבלת צומת, עוקבת אחרי מצביעי ההורים עד שמגיעה לצומת ההתחלה ומחזירה את האופרטורים שייצרו את המסלול.

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

בתחום משאבי החיפוש נדבר על:

• זמן הריצה – בד"כ מדד שאינו תלוי במחשב ספציפי, כגון מספר הצמתים שפותחו.
• צריכת הזכרון של האלגוריתם.

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

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

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

סוגי אלגוריתמי חיפוש

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