מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

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

דף זה עוסק בתכנון דינמי. תכנון דינמי אינו אלגוריתם, אלא רעיון כללי ליצירת אלגוריתמים יעילים.

כדאי לדעת: בספר הקורס, הפרק "Dynamic Programming" עוסק בנושאים אלה. אנו נתמקד ברעיון הmemoization. הפרק כאן מתאר (בקצרה) רעיון כללי מאד. בדג הסלמון והכפלת שרשרת מטריצות נראה יישומים שלו.

[עריכה] הרעיון הבסיסי

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

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

[עריכה] שלבי הפתרון בתכנון דינאמי

באופן כללי, הדרך לפתור בעיות תכנון דינמי היא כך:

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

(לאחר ניסיון מה, אפשר לדלג ישירות לשלב 3.)

מימוש C++ comp.lang.c++

הפרק הקודם: אלגוריתמים למיון בזמן לינארי

תכנון דינאמי תרגילים

הפרק הבא: תכנון דינאמי - דג הסלמון