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

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

4.4.7. אלגוריתם Iterative-deepening A*

אחד מחסרונותיו של A* הוא דרישת הזיכרון שלו.

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

האלגוריתם:

קבע את $plot:\[h\left( {{s_i}} \right)\]$ כעומק המקסימלי.
ערוך חיפוש לעומק. עצור בכל ענף עבורה $plot:\[f\]$ גדולה מהסף. אם מצאת פתרון, החזר אותו.
אם בחיפוש לעומק לא נמצא פתרון, הגדל את הסף בחריגה המינימלית שנמצאה בשלב 2, וחזור לשלב 2.

DFS-C (state, g, path)
f $plot:\[ \leftarrow \]$ g+h(state)
if f > max-f then new-max-f $plot:\[ \leftarrow \]$ min(new-max-f,f)
else
    if goalp(state) return(path)
    else
      for c in succ(state)
        DFS-C(c, g+cost(state,c), path state)

IDA* (state)
max-f $plot:\[ \leftarrow \]$ h(state)
new-max-f $plot:\[ \leftarrow \]$ infinity
loop while resources are available
    solution $plot:\[ \leftarrow \]$ DFS-C(state,0,())
    if solution <> () then return (solution)
    max-f $plot:\[ \leftarrow \]$ new-max-f

לפרק הקודם4.4.6. משקלות דינמיים

לפרק הבא4.5. חיפוש דו כיווני

תגובות:

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