תכנון דינמי

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

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

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

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

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

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

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

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

דוגמאות[עריכת קוד מקור | עריכה]

חישוב איבר כללי בסדרת פיבונאצ'י[עריכת קוד מקור | עריכה]

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

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

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

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

קל לראות בדוגמה זו שהערך מחושב שוב ושוב פעמים רבות, ושהחישוב ייעשה בלתי יעיל להפליא עבור ערכים גדולים של .

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

  1. חישוב באמצעות הנתונים.
  2. חישוב באמצעות (שחושב בצעד הקודם) ו- (הנתון).
  3. חישוב באמצעות (שחושבו בצעדים הקודמים).

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

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