תכנון דינמי

במדעי המחשב, שיטת התכנון הדינמי לבניית אלגוריתם משמשת לפתרון בעיות שאינן ניתנות לפתרון יעיל בשיטת הפרד ומשול נאיבית. (הפותרת בעיה על ידי חלוקתה לתת-בעיות הנפתרות בתורן על ידי חלוקתן לתת-בעיות קטנות אף יותר, עד שמתקבלות בעיות קטנות מספיק שיהיה ניתן לפתור אותן באופן ישיר).

שיטה זו הוצגה לראשונה בשנת 1953 על ידי ריצ'רד בלמן.

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

האלטרנטיבה שמציעה שיטת התכנון הדינמי היא פתרון של כל תת-הבעיות בזו אחר זו, כאשר פתרון כל אחת מתת-הבעיות מאוחסן לשימוש עתידי.

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

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

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

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

דוגמאות

חישוב איבר כללי בסדרת פיבונאצ'י

סדרת פיבונאצ'י היא סדרה המוגדרת באמצעות נוסחת הנסיגה הבאה:

$\ fib(n)=fib(n-1)+fib(n-2)$

כאשר שני האיברים הראשונים בסדרה נתונים:

$\ fib(1)=fib(2)=1$

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

לדוגמה, נחשב בצורה זו את האיבר החמישי בסדרה בצורה זו:

$\ fib(5)=fib(4)+fib(3)=fib(3)+fib(2)+fib(2)+fib(1)=$

$\ =fib(2)+fib(1)+1+1+1=1+1+3=5$

קל לראות בדוגמה זו שהערך $\ fib(2)$ מחושב שוב ושוב פעמים רבות, ושהחישוב ייעשה בלתי יעיל להפליא עבור ערכים גדולים של $\ n$.

אלגוריתם תכנון דינמי לפתרון הבעיה יעבוד בכיוון ההפוך – הוא ינוע מערכי הקצה $\ fib(1),fib(2)$ לערך הרצוי על ידי חישוב סדרתי של כל מספרי פיבונאצ'י עד אליו. למשל עבור הדוגמה הקודמת שלנו, כאשר $\ n=5$ האלגוריתם יפעל כך:

1. חישוב $\ fib(3)$ באמצעות $\ fib(1),fib(2)$ הנתונים.
2. חישוב $\ fib(4)$ באמצעות $\ fib(3)$ (שחושב בצעד הקודם) ו-$\ fib(2)$ (הנתון).
3. חישוב $\ fib(5)$ באמצעות $\ fib(4),fib(3)$ (שחושבו בצעדים הקודמים).

ניתן לשים לב שבעוד שהאלגוריתם הרקורסיבי שתואר קודם לכן ביצע 9 קריאות רקורסיביות, האלגוריתם החדש ביצע 3 צעדים בלבד, מאחר שחישב את כל אחד מהערכים $\ fib(3)...fib(5)$ פעם אחת בלבד.

כך ניתן לחשב את פונקציית פיבונאצ'י של כל n בסיבוכיות ליניארית וזאת באמצעות "זכירה" של 2 מספרים בלבד.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

32669436תכנון דינמי