ההבדל בין חיפוש מושכל וחסר מידע
תוֹכֶן
חיפוש הוא תהליך של מציאת רצף של צעדים הדרושים לפיתרון כל בעיה. ההבדל הקודם בין חיפוש מושכל ללא מידע הוא שחיפוש מושכל מספק את ההנחיות היכן ואיך למצוא את הפיתרון. לעומת זאת, החיפוש הלא-מידע אינו מספק מידע נוסף על הבעיה למעט המפרט שלה.
עם זאת, בין טכניקות חיפוש מושכלות והן ללא טכניקות חיפוש, החיפוש המושכל יעיל וחסכוני יותר.
-
- טבלת השוואה
- הגדרה
- הבדלים עיקריים
- סיכום
טבלת השוואה
| בסיס להשוואה | חיפוש מידע | חיפוש ללא מידע |
|---|---|---|
| בסיסי | משתמש בידע כדי למצוא את השלבים לפיתרון. | אין שימוש בידע |
| יעילות | יעיל מאוד שכן גוזל פחות זמן ועלות. | היעילות היא מתווכת |
| עלות | נמוך | יחסית גבוה |
| ביצועים | מוצא פיתרון מהר יותר | המהירות איטית יותר מחיפוש מושכל |
| אלגוריתמים | עומק היוריסטי חיפוש ראשון ורוחב ראשון, וחיפוש A * | חיפוש עומק ראשון, חיפוש רוחב ראשון וחיפוש ראשון בעלות נמוכה ביותר |
הגדרת חיפוש מידע
טכניקת החיפוש המושכלת עושה שימוש בידע הספציפי לבעיות על מנת לתת מושג לפיתרון הבעיה. אסטרטגיית חיפוש מסוג זה למעשה מונעת מאלגוריתמים למעוד על המטרה והכיוון לפתרון. חיפוש מושכל יכול להיות יתרון מבחינת העלות בה מושגת האופטימיות בעלויות חיפוש נמוכות יותר.
כדי לחפש בעלות מסלול אופטימלית בתרשים על ידי יישום אסטרטגיית חיפוש מושכלת, הצמתים המבטיחים ביותר n מוכנסים לפונקציה היוריסטית h (n). ואז הפונקציה מחזירה מספר אמיתי שלילי שאינו עלות נתיב משוער המחושב מהצומת n לצומת היעד.
כאן החלק החשוב ביותר של הטכניקה המושכלת הוא הפונקציה ההיוריסטית המאפשרת להעביר את הידע הנוסף לבעיה לאלגוריתם. כתוצאה מכך, זה עוזר במציאת הדרך אל המטרה דרך הצמתים השכנים השונים. ישנם אלגוריתמים שונים המבוססים על חיפוש מושכל כמו חיפוש היוריסטי-עומק ראשון, חיפוש היוריסטי-רוחב-ראשון, חיפוש A * וכו '. הבה כעת להבין את החיפוש העומק היוריסטי הראשון.
עומק היוריסטי חיפוש ראשון
בדומה לשיטת חיפוש עומק ראשונה שניתנה להלן עומק היוריסטי חיפוש ראשון בוחר נתיב אך חוצה את כל הנתיבים מהנתיב שנבחר לפני בחירת נתיב אחר. עם זאת, הוא בוחר את הדרך הטובה ביותר באופן מקומי. במקרים שבהם הערך היוריסטי הקטן ביותר הוא העדיפות לגבול, אז זה ידוע כחיפוש הראשון הטוב ביותר.
אלגוריתם חיפוש מושכל אחר הוא חיפוש * שממזג את מושג החיפוש הראשון והמחירים הטובים ביותר. שיטה זו מתחשבת הן בעלות הנתיב והן במידע היוריסטי בתהליך חיפוש ובחירת הנתיב להרחבה. עלות הנתיב הכוללת המשוערת המשמשת לכל נתיב השוכן בגבול מההתחלה לצומת היעד. לכן הוא משתמש בשתי פונקציות בו זמנית - עלות (p) היא עלות הנתיב שהתגלה ו h (p) הוא הערך המשוער של עלות הנתיב מצומת ההתחלה לצומת המטרה.
הגדרה של חיפוש לא מידע
החיפוש הלא-מידע שונה מחיפוש מושכל באופן שהוא רק מספק את הגדרת הבעיה אך אין שום צעד נוסף במציאת הפיתרון לבעיה. המטרה העיקרית של חיפוש ללא מידע היא להבדיל בין מצב היעד למצב שאינו היעד, והוא מתעלם לחלוטין מהיעד אליו הוא פונה בדרך עד שהוא יגלה את המטרה ודיווח על היורש. אסטרטגיה זו ידועה גם כחיפוש עיוור.
ישנם קטגוריות חיפוש שונות בקטגוריה זו כמו חיפוש עומק ראשון, חיפוש עלות אחיד, חיפוש רוחב ראשון וכדומה. הבה כעת להבין את המושג שמאחורי החיפוש הלא-מידע בעזרת חיפוש ראשון לעומק.
חיפוש עומק ראשון
בחיפוש העמוק הראשון, מחסנית אחרונה בחוץ משמשת להוסיף ולהסרת הצמתים. רק צומת אחד מתווסף או מוסר בכל פעם והרכיב הראשון שמוסר מגבול הערימה יהיה האלמנט האחרון שנוסף לערימה. על ידי שימוש בערימה בגבול התוצאות של חיפוש השבילים התקדמו בצורה ראשונה לעומק. כאשר מחפשים דרך קצרה ואופטימלית באמצעות חיפוש עומק ראשון, הנתיב שנוצר על ידי הצמתים הסמוכים הושלם תחילה גם אם הוא לא הנתיב הרצוי. ואז מחפשים את הנתיב האלטרנטיבי באמצעות מעקב אחורי.
במילים אחרות, האלגוריתם בוחר את האלטרנטיבה הראשונה בכל צומת ואז עוקב אחר מסלול אלטרנטיבה אחרת עד שהוא חצה את כל הנתיבים מהבחירה הראשונה. זה גם מעלה בעיה שבה החיפוש עשוי להפסיק להפסיק בגלל לולאות (מחזורים) אינסופיים שנמצאים בתרשים.
- טכניקת החיפוש המודעת לשעבר משתמשת בידע על מנת למצוא את הפיתרון. מצד שני, טכניקת החיפוש הלא-ידיעת האחרונה אינה עושה שימוש בידע. במונחים פשוטים יותר אין מידע נוסף אודות הפיתרון.
- היעילות של החיפוש המודוע טובה יותר מהחיפוש הבלתי מודע.
- חיפוש ללא מידע גוזל יותר זמן ועלות מכיוון שאין לו מושג לגבי הפיתרון לעומת חיפוש מושכל.
- חיפוש עומק ראשון, חיפוש רוחב ראשון וחיפוש נמוך ביותר במחיר הנמוך ביותר הם האלגוריתמים הנמצאים תחת הקטגוריה של החיפוש הלא-מידע. לעומת זאת, חיפוש מושכל מכסה את האלגוריתמים כמו עומק היוריסטי ראשון, חיפוש היוריסטי רוחב ראשון וחיפוש A *.
סיכום
החיפוש המושכל מספק את הכיוון לגבי הפיתרון בעוד שבחיפוש ללא מידע לא ניתן שום הצעה לגבי הפיתרון. זה הופך את החיפוש הלא-ממושך לממושך יותר בעת יישום האלגוריתם.
