יחידה 9: תכנון דינאמי

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

הרעיון המרכזי: פירוק בעיות ושימוש חוזר

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

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

• תת-מבנה אופטימלי (Optimal Substructure): פתרון אופטימלי לבעיה המקורית מכיל פתרונות אופטימליים לתת-בעיות שלה.
• תת-בעיות חופפות (Overlapping Subproblems): אותן תת-בעיות מופיעות שוב ושוב בחישוב הפתרון.

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

בניית אלגוריתם תכנון דינאמי דורשת הבנה שיטתית של הבעיה. הנה השלבים המומלצים:

1. אפיין את מבנה הפתרון האופטימלי: הראה שפתרון אופטימלי לבעיה מכיל פתרונות אופטימליים לתת-בעיות שלה.
2. הגדר את ערך הפתרון האופטימלי באופן רקורסיבי: הגדר את המצב (state) של הבעיה (מהם הפרמטרים שמשתנים בין תת-בעיות) וכתוב יחס רקורסיבי (recurrence relation) המבטא את הפתרון לבעיה במונחים של פתרונות לתת-בעיות קטנות יותר. אל תשכח את מקרי הבסיס.
3. חשב את ערך הפתרון האופטימלי (בדרך כלל מלמטה למעלה): מלא טבלה (או מערך) באופן איטרטיבי, החל ממקרי הבסיס, תוך שימוש ביחס הרקורסיבי.
4. בנה פתרון אופטימלי (אם נדרש): לעיתים קרובות, נדרש לא רק הערך האופטימלי, אלא גם הפתרון עצמו. ניתן לשחזר אותו על ידי מעקב אחר הבחירות שנעשו בטבלה במהלך מילוי הפתרונות.

דוגמאות קלאסיות וחשובות

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

• סדרת פיבונאצ'י (Fibonacci Sequence): דוגמה פשוטה המדגימה תת-בעיות חופפות (F(n) = F(n-1) + F(n-2)). פתרון נאיבי הוא אקספוננציאלי, בעוד שפתרון DP הוא לינארי.
• התת-סדרה המשותפת הארוכה ביותר (Longest Common Subsequence - LCS): נתונות שתי סדרות, מצא את אורך התת-סדרה המשותפת הארוכה ביותר שלהן. זו דוגמה מצוינת לבעיה דו-ממדית עם יחס רקורסיבי מורכב יותר.
• בעיית תרמיל הגב (0/1 Knapsack Problem): נתון תרמיל בעל קיבולת משקל W וקבוצת פריטים, לכל אחד משקל וערך. בחר תת-קבוצה של פריטים למילוי התרמיל כך שסך הערך יהיה מקסימלי, וסך המשקל לא יעלה על W. כל פריט ניתן לבחור פעם אחת בלבד (0 או 1).

שאלות לדיון

• הסבר מתי כדאי להשתמש בתכנון דינאמי לעומת גישת "הפרד ומשול". תן דוגמה לבעיה שמתאימה לכל אחת מהגישות.
• כיצד ניתן לזהות שבעיה מסוימת ניתנת לפתרון באמצעות תכנון דינאמי? מהם שני המאפיינים העיקריים שיש לחפש?
• האם תמיד עדיף להשתמש בגישת ה-Tabulation על פני Memoization? נמק.
• תאר את השלבים העיקריים לפתרון בעיה באמצעות תכנון דינאמי. מהו השלב המאתגר ביותר לדעתך?

נקודות לתשובת מודל

• הפרד ומשול מול תכנון דינאמי: הפרד ומשול מתאים לבעיות שבהן תת-הבעיות אינן חופפות (לדוגמה, מיון מיזוג, חיפוש בינארי). תכנון דינאמי מתאים לבעיות עם תת-בעיות חופפות ותת-מבנה אופטימלי (לדוגמה, פיבונאצ'י, LCS).
• זיהוי DP: חפש תת-מבנה אופטימלי (פתרון אופטימלי נבנה מפתרונות אופטימליים של תת-בעיות) ותת-בעיות חופפות (אותן תת-בעיות נפתרות שוב ושוב).
• Tabulation מול Memoization: Tabulation (מלמטה למעלה) בדרך כלל קל יותר למימוש איטרטיבי, נמנע מעומס קריאות רקורסיביות (stack overflow), ולעיתים קרובות יעיל יותר בזמן ריצה (ללא תקורה של קריאות פונקציה). Memoization (מלמעלה למטה) קרוב יותר לדרך החשיבה הרקורסיבית הטבעית, ופותר רק את תת-הבעיות הנחוצות בפועל. במבחן, לרוב מצפים לפתרון Tabulation.
• שלבי פתרון DP: אפיין תת-מבנה אופטימלי, הגדר יחס רקורסיבי (כולל מקרי בסיס), חשב את הפתרון (בדרך כלל מלמטה למעלה), ובנה את הפתרון אם נדרש. השלב המאתגר ביותר הוא לרוב הגדרת המצב והיחס הרקורסיבי.