תכנון דינמי

התכנון הדינמי הוא שיטה אלגוריתמית שהוצגה ב-1953 על ידי ריצ'רד בלמן. השיטה מתאימה לבעיות שמתקבל להן פתרון רקורסיבי (רקורסיה = פתרון שמתבסס על פתרונות של תת-בעיות קטנות) אך פתרון רקורסיבי ישיר אינו יעיל, כי אותו תת-בעיה נחשבת שוב ושוב.

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

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

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

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

1. מציגים פתרון רקורסיבי לבעיה.
2. מגלים שזמן הריצה הרקורסיבי הוא מעריכי בגלל קריאות חוזרות.
3. בודקים שהמספר הכולל של תת-הבעיות הוא פולינומי.
4. פותרים את כל התת-הבעיות מהבסיס (מקרי קצה) כלפי מעלה עד לבעיה המקורית, ושומרים תוצאות לשימוש חוזר.

בסדרת פיבונאצ'י fib(n) מוגדרות הנסיגות fib(n)=fib(n-1)+fib(n-2) עם fib(1)=fib(2)=1. חישוב רקורסיבי "מלמעלה למטה" מחזיר חזרות רבות של אותם ערכים. לדוגמה החישוב הרקורסיבי של fib(5) כולל חישובים חוזרים רבים, בעוד ששיטת התכנון הדינמי מחשבת כל ערך פעם אחת בלבד על ידי חישוב סדרתי מהבסיס כלפי מעלה. בדוגמה זו האלגוריתם הרקורסיבי ביצע 9 קריאות רקורסיביות, ואילו הגישה הדינמית ביצעה רק 3 צעדים. כך אפשר לחשב fib(n) בזמן ליניארי תוך שמירה של שני ערכים בלבד בזיכרון.

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

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

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

1. נותנים פתרון רקורסיבי קצר.
2. רואים שיש חזרות רבות.
3. בונים את כל התת-הבעיות מהבסיס ומזכירים את התשובות.

בסדרת פיבונאצ'י כל מספר הוא סכום שני הקודמים.
לדוגמה fib(1)=1 ו-fib(2)=1. כדי למצוא fib(5) אפשר לחשב בזה אחר זה: 1, 1, 2, 3, 5.
התכנון הדינמי מחשב כל מספר פעם אחת ומזכיר אותו. כך נחסך הרבה חישוב.
התהליך שומר רק שני מספרים בזיכרון כדי להמשיך קדימה.