הועלה לאתר:  
מספר עמודים: 47
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

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

ספר אלקטרוני מאת: ניר אדר

4.4.3. קבילות של A*

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

סימונים:

plot:\[{g^*}\left( n \right)\] - המחיר הנמוך ביותר של מסלולים מהמצב ההתחלתי plot:\[{S_i}\] למצב plot:\[n\].

plot:\[{h^*}\left( n \right)\] - המחיר הנמוך ביותר של מסלולים ממצב plot:\[n\] למצב כלשהו ב-plot:\[{S_g}\]

plot:\[{C^*} = {h^*}\left( {{S_i}} \right)\] - מחיר אופטימלי לפתרון

plot:\[{f^*}\left( n \right) = {g^*}\left( n \right) + {h^*}\left( n \right)\] - מחיר מינימלי של מסלול מ-plot:\[{S_i}\] למצב כלשהו ב-plot:\[{S_g}\].

הגדרה: פונקציה יוריסטית נקראת פונקציה קבילה אם לכל plot:\[n\] מתקיים: plot:\[0 \leqslant h\left( n \right) \leqslant {h^*}\left( n \right)\] (plot:\[h\] תמיד אופטימית בהערכת המחיר למטרה).

מתקיים כי עבור כל פונקציה קבילה,plot:\[\forall s,s \in {S_g}\] מתקיים בהכרח plot:\[h\left( s \right) = 0\].

דוגמאות ליוריסטיקות קבילות: עבור בעיות מפה – מרחק אווירי, עבור בעיות סריג – מרחקי מנהטן.

למה 1: בכל שלב לפני ש-A* עוצרת, קיים צומת plot:\[n\] ברשימת ה-OPEN השיך למסלול אופטימלי המקיים plot:\[f\left( n \right) \leqslant {C^*}\].



הגדרה: נאמר שפונקציה יוריסטית plot:\[{h_2}\] יותר מיודעת מפונקציה יוריסטית plot:\[{h_1}\] אם שתיהן קבילות, ולכל plot:\[n\] שאינו מטרה מתקיים plot:\[{h_2}\left( n \right) > {h_1}\left( n \right)\].

משפט: A* המשתמש ב-plot:\[{h_1}\] יפתח כל צומת שיפתח A* המשתמש ב-plot:\[{h_2}\] (כלומר שימוש ביוריסטיקה יותר מיודעת מביא לחיפוש יעיל יותר).

הגדרה: פונקציה יוריסטית plot:\[h\] תקרא פונקציה מונוטונית אם plot:\[\forall s \in S,\forall s' \in SUCC\left( s \right)\] מתקיים כי plot:\[\left[ {h\left( s \right) - h\left( {s'} \right) \leqslant COST\left( {s,s'} \right)} \right]\].

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

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

טענה: שימוש ביוריסטיקה מונוטונית מבטיח שהפונקציה plot:\[f\] תהיה מונוטונית עולה.

משפט: עבור plot:\[{A^*}\] המשתמש -plot:\[h\] מונוטונית מתקיים: plot:\[\forall n \in CLOSED\left[ {g\left( n \right) = {g^*}\left( n \right)} \right]\] (כלומר מובטח שכל צומת שפותח מצביע למסלול האופטימלי אל מצב ההתחלה).

מסקנה: אין צורך להעביר צמתים מ-CLOSE ל-OPEN ופיתוחם מחדש נחסך.

משפט: עבור יוריסטיקה מונוטונית, plot:\[{A^*}\] היא גם אופטימלית במשאבי חיפוש.

תגיות המסמך:

לפרק הקודם4.4.2. תכונות פורמליות של A*
לפרק הבא4.4.4. השוואה בין plot:[{A^*}] עם פונקציה קבילה ל-Uniform Cost Search:
מאת: אוריה

אבל הוא עדיין לא נפתח...

מאת: אוריה

סליחה, זה ב-9

והקובץ יורד בסדר
מאת: ניר

אני עם אקרובט 8.1.1

הקובץ נפתח בלי שום בעייה
מאת: shoshan

אני מציע שתנסה שוב ב-acrobat 8

כי זה עובד לי בסדר גמור ב-Acrobat 9 וב-Foxit...

יכול להיות שהקובץ ירד לך לא טוב או חתוך או קטן מידי ?
מאת: אוריה

ב-5 זה נפתח

מאת: אוריה

לא נפתח

לא נפתח ב Acrobat Reader 8, הוא כותב שהקובץ לא נתמך או שהוא ניזוק.
שיתוף:
| עוד