4.4.3. קבילות של A*הגדרה: אלגוריתם חיפוש הוא קביל אם מובטח שהוא ימצא פתרון אופטימלי (בעל מחיר מינימלי) כאשר קיים פתרון. סימונים:
הגדרה: פונקציה יוריסטית נקראת פונקציה
קבילה אם לכל מתקיים כי עבור כל פונקציה קבילה, דוגמאות ליוריסטיקות קבילות: עבור בעיות מפה – מרחק אווירי, עבור בעיות סריג – מרחקי מנהטן. למה 1: בכל שלב לפני ש-A*
עוצרת, קיים צומת הגדרה: נאמר שפונקציה יוריסטית משפט: A* המשתמש ב- הגדרה: פונקציה יוריסטית כלומר, איננו מסתפקים בכך שהפונקציה היוריסטית תהיה אופטימית באופן גלובלי אלא דורשים שהיא תהיה אופטימית ביחס לכל צעד בדרך אל המטרה. (הפונקציה יכולה לעלות ולרדת, ועדיין תמיד להיות אופטימית ביחס למרחק אל המטרה. פונקציה כזו אינה מונוטונית). טענה: שימוש ביוריסטיקה מונוטונית מבטיח
שהפונקציה משפט: עבור מסקנה: אין צורך להעביר צמתים מ-CLOSE ל-OPEN ופיתוחם מחדש נחסך. משפט: עבור יוריסטיקה מונוטונית, |
תוכן העניינים:
קישורים רלוונטיים:שיתוף: |
אבל הוא עדיין לא נפתח...