What is dynamic programming (hebrew)?

תכנון דינמי, תכנות דינמי או באנגלית Dynamic Programming הם שמות לדרך ליצירת אלגוריתמים. המילה "תכנות" בשם כוונות יצירת תוכנית פעולה ולא קידוד בשפת תכנות.

הבסיס של השיטה

שני הרעיונות שעומדים מאחורי השם המרשים הם:

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

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

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

בעיית "תרמיל הגב"  

בעיית "תרמיל הגב" או Knapsack problem היא בעייה כללית שיש לה שימושים שונים. 

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

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

פתרון הבעיה

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

בשפה פורמלית, נכתוב את הפונקציה maxValue (products, maxWeight)

והנה האלגוריתם:

שלב א:  אם יש במערך רק מוצר אחד

אז

אם הוא קטן מהמשקל המירבי

אז נחזיר את הערך שלו

אחרת נחזיר 0

שלב ב (השבירה לתתי בעיות):

            אם המוצר הראשון ברשימה שוקל יותר מהמשקל המירבי

            אז נחזיר את הערך של maxValue (products without first product, maxWeight)

            אחרת

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

Value of product1 + maxValue(products without product1, maxWeight-weight of product1)

נבדוק את האפשרות שלא ניקח את המוצר הראשון ואז הערך שאפשר להגיע אליו הוא               

maxValue (products without first one, maxWeight)

ועכשיו נחזיר את המקסימום בין שני הערכים               

יפה, לא?

עקרון הזכרון

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

זו רקורסיה פשוטה.

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

בדוגמא למטה של עץ חישוב רואים ש f(2) מחושב שלוש פעמים. זה בזבוז. אם חישבנו זאת פעם אחת נוכל להשתמש בערך בפעמים הבאות.

ועד כאן המבוא לתכנון דינמי.

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

ראה https://www.quora.com/Why-is-dynamic-programming-called-dynamic-programming