שיטת חיפוש היוריסטית

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

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

Hill-Climbing

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

האלגוריתם:
1. קבע את T כשורש העץ.
2. צרף את T לרשימת המסלול המוביל אל המטרה.
3. כל זמן ש-T אינו צומת מטרה בצע:

3.1 מבין כל הבנים של T אתר את הבן B בעל הציון הטוב ביותר.

3.2 קבע את T כ-B.

3.3 צרף את T לרשימת המסלול המוביל אל המטרה.

Hill Climbing עם Backtracking

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

1. הכנס את שורש העץ למחסנית.
2. כל זמן שהמחסנית לא ריקה וכן לא הגענו עדיין לצומת המטרה בצע:

2.1 שלוף את ראש המחסנית T.

2.2 אם T הוא צומת המטרה בצע:

2.2.1 הדפס הודעה ועצור.

2.3 אחרת:

2.3.1 מיין את הבנים של T והכנס למחסנית את הבנים כך שהבן בעל הציון הגרוע ביותר נכנס ראשון, והבן בעל הציון הטוב ביותר נכנס אחרון.

Beam-Search

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

להלן האלגוריתם (R מייצג את שורש העץ, הראשון בתור Q מייצג את הצומת הנוכחי, L מייצג את רשימת הבנים של S):

1. הכנס את R לתוך Q‏.
2. כל זמן שהתור לא ריק בצע:

2.1 הוצא צומת S מהתור.

2.2 הדפס את S.

2.3 קבע את L כרשימת הבנים של S‏.

2.4 הורד מ-L את הבנים שציונם אינו מתאים להמשך החיפוש.

2.5 הכנס לתור Q את L לפי סדר הופעתם של הבנים.

Best First

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

ראו גם

• אלגוריתם חיפוש A*
• היוריסטיקה קבילה

לקריאה נוספת

• ברוריה הברמן, מבוא לבינה מלאכותית, המחלקה להוראת המדעים, מכון ויצמן למדע, 1998