Skip to main content

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) מחושב שלוש פעמים. זה בזבוז. אם חישבנו זאת פעם אחת נוכל להשתמש בערך בפעמים הבאות.




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

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


Comments

Popular posts from this blog

Best freeware - XML editor

As a software developer, I open XML files all the time. I a heavy commercial XML editor. But nothing can compare to a small, thin and free XML editor like 'foxe'. A great feature is has is the alignment of long XML strings to readable XML format (Shift-F8). It help lot of times when the XML file was generated by some tool and was not readable. Homepage: http://www.firstobject.com/dn_editor.htm

Jenkins error: groovy.lang.MissingPropertyException

I tried to run groovy build step and got below error. This post will describe how I solved the problem. Caught: groovy.lang.MissingPropertyException: No such property: hudson for class: script

SSL in pictures

Here is my summary on SSL (or as I like to call it 'SSL for dummies')