TechCodeview

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

סוכנים לפתרון בעיות:

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

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

לחפש:חיפוש הוא הליך צעד אחר צעד לפתרון בעיית חיפוש במרחב חיפוש נתון. לבעיית חיפוש יכולים להיות שלושה גורמים עיקריים:
מרחב חיפוש:מרחב החיפוש מייצג קבוצה של פתרונות אפשריים, שיכולים להיות למערכת.מצב התחלה:זה מצב שממנו מתחיל הסוכן החיפוש .מבחן מטרה:זוהי פונקציה אשר צופה במצב הנוכחי ומחזירה אם מצב המטרה הושג או לא.
עץ חיפוש:ייצוג עץ של בעיית חיפוש נקרא עץ חיפוש. השורש של עץ החיפוש הוא צומת השורש המתאים למצב ההתחלתי.פעולות:זה נותן את התיאור של כל הפעולות הזמינות לסוכן.מודל מעבר:תיאור של מה שכל פעולה עושה, יכול להיות מיוצג כמודל מעבר.עלות נתיב:זוהי פונקציה אשר מקצה עלות מספרית לכל נתיב.פִּתָרוֹן:זהו רצף פעולה שמוביל מצומת ההתחלה לצומת המטרה.פתרון אופטימלי:אם לפתרון יש את העלות הנמוכה ביותר מבין כל הפתרונות.

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

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

שְׁלֵמוּת: אומרים שאלגוריתם חיפוש הוא שלם אם הוא מבטיח להחזיר פתרון אם קיים לפחות פתרון כלשהו עבור קלט אקראי כלשהו.

השבת את מצב המפתח

אופטימליות: אם מובטח שפתרון שנמצא לאלגוריתם הוא הפתרון הטוב ביותר (עלות הנתיב הנמוכה ביותר) מבין כל שאר הפתרונות, אזי פתרון כזה הוא פתרון אופטימלי.

מורכבות זמן: מורכבות הזמן היא מדד של זמן עבור אלגוריתם להשלים את המשימה שלו.

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

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

בהתבסס על בעיות החיפוש נוכל לסווג את אלגוריתמי החיפוש לאלגוריתמים לא מושכלים (חיפוש עיוור) וחיפוש מושכל (חיפוש היוריסטי).

הבדל תאריכים באקסל

חיפוש לא מושכל/עיוור:

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

ניתן לחלק אותו לחמישה סוגים עיקריים:

• חיפוש רוחב ראשון
• חיפוש עלות אחיד
• חיפוש עומק ראשון
• העמקה איטרטיבית עומק-חיפוש ראשון
• חיפוש דו כיווני

חיפוש מושכל

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

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

חיפוש מושכל יכול לפתור בעיות מורכבות רבות שלא ניתן היה לפתור בדרך אחרת.

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

1. חיפוש חמדן
2. חיפוש