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


Edit-undo.svg

שקלו לדלג על נושא זה

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



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


כדאי לדעת:

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

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

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

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

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

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

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

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


 

מימוש C++

comp.lang.c++


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