מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי
 |
שקלו לדלג על נושא זה נושא זה מניח שאתה חש בנוח עם חשיבה רקורסיבית ותכנות רקורסיבי. אם זה אינו המצב, שקול לדלג לחשיבה רקורסיבית ולחזור לכאן מאוחר יותר. |
דף זה עוסק בתכנון דינמי. תכנון דינמי אינו אלגוריתם, אלא רעיון כללי ליצירת אלגוריתמים יעילים.
|
כדאי לדעת: #בספר הקורס, הפרק "Dynamic Programming" עוסק בנושאים אלה. אנו נתמקד ברעיון הmemoization.
|
הרעיון הבסיסי
[עריכה]חיפוש בינרי, מיון מיזוג וQuicksort - כל אחד מאלגוריתמים אלה השתמש ברעיון divide-and-conquer (הפרד ומשול): כדי לפתור בעיה "גדולה", משתמשים בפתרון בעיות "קטנות". זה אחד הרעיונות המרכזיים של הקורס.
כשמתרגמים רעיון זה לאלגוריתם, טבעי לעשות זאת ע"י רקורסיה. לעתים יש מצבים בהם הרקורסיה מאד לא יעילה, מפני שהיא פותרת אותן בעיות שוב ושוב. במצבים אלה, טוב לשמור את פתרון הבעיות הקטנות בפעם הראשונה שפותרים אותן.
שלבי הפתרון בתכנון דינאמי
[עריכה]באופן כללי, הדרך לפתור בעיות תכנון דינמי היא כך:
- תרגום רעיון divide and conquer לרקורסיה
- זיהוי המצב בו הרקורסיה פותרת אותן בעיות שוב ושוב
- הכנסת מנגנון לשמירת הפתרון לבעיות שכבר נפתרו
(לאחר ניסיון מה, אפשר לדלג ישירות לשלב 3.)
 |
מימוש C++ |
| הפרק הקודם: אלגוריתמים למיון בזמן לינארי |
תכנון דינאמי תרגילים |
הפרק הבא: תכנון דינאמי - דג הסלמון |