Dynamic programming — תכנות דינמי

תכנות דינמי (ת"ד; אנגל. dynamic programming, DP) — הוא שיטה לפתרון בעיות אופטימיזציה מורכבות, המבוססת על פירוק הבעיה המקורית לרצף של תת-בעיות פשוטות יותר. השיטה מיושמת על תהליכי קבלת החלטות רב-שלביים, שבהם הפתרון האופטימלי של הבעיה כולה ניתן לבנייה מתוך הפתרונות האופטימליים של תת-הבעיות שלה.

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

תכונות ומשפטים מרכזיים

ישימות התכנות הדינמי לבעיה נקבעת על פי קיום שתי תכונות יסודיות.

עקרון האופטימליות של בלמן

המושג המרכזי של השיטה הוא עקרון האופטימליות של בלמן (אנגל. Bellman's principle of optimality). הוא קובע: יהיו אשר יהיו המצב הראשוני וההחלטה הראשונית, ההחלטות הבאות חייבות להוות אסטרטגיה אופטימלית ביחס למצב שנוצר כתוצאה מההחלטה הראשונה.

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

תת-בעיות חופפות

בעיה מכילה את התכונה של תת-בעיות חופפות (אנגל. overlapping subproblems) אם בפתרונה הרקורסיבי אותן תת-בעיות מתעוררות שוב ושוב. ת"ד מאפשר להימנע מחישובים חוזרים על ידי שמירת פתרונות תת-הבעיות שכבר נפתרו (טכניקה הנקראת memoization או tabulation), מה שמגביר משמעותית את היעילות בהשוואה לחיפוש רקורסיבי נאיבי.

משוואת בלמן

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

$V_{k-1}(x)=\underset{y\in U(x)}{max}\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

שבו:

• $k$ — מספר השלב (מ-$m$ עד 1);
• $x$ — מצב המערכת בשלב $k-1$;
• $y$ — ההחלטה הנשלטת המתקבלת בשלב $k$;
• ${\phi }_k(x,y)$ — הרווח (או העלות) בשלב ה-k;
• $f_k(x,y)$ — פונקציה הקובעת את המצב החדש של המערכת;
• $V_k(s)$ — הערך האופטימלי של פונקציית המטרה עבור תת-הבעיה המתחילה בשלב $k$ במצב $s$.

המשוואה נפתרת ברצף, בדרך כלל "מהסוף", בתנועה מהשלב האחרון אל הראשון.

דוגמאות ליישום

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

מגבלות

המגבלה העיקרית של השיטה היא קללת הממדיות (אנגל. curse of dimensionality) — מונח שהוכנס על ידי בלמן לציון הגידול האקספוננציאלי במספר המצבים ובהתאם גם במורכבות החישובית, עם הגדלת מספר המשתנים המתארים את מצב המערכת. הדבר מגביל את הישימות המעשית של ת"ד מדויק לבעיות בממדיות גבוהה מאוד.

מושגים קשורים

• מחקר ביצועים (חקר פעולות)
• תורת הבקרה האופטימלית
• תהליך קבלת החלטות מרקובי (הכללה סטוכסטית)
• משוואת המילטון — ז'קובי — בלמן (האנלוג לזמן רציף)

הערות

</references>