תכנון דינמי

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

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

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

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

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

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

  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 מספרים בלבד.