תכנון דינמי

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

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

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

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

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

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

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

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

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

סדרת פיבונאצ'י היא סדרה המוגדרת באמצעות כלל הנסיגה הבא -

$\ 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$ האלגוריתם יפעל כך -

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

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

מקור: http://he.wikipedia.org../../../%D7%AA/%D7%9B/%D7%A0/%D7%AA%D7%9B%D7%A0%D7%95%D7%9F_%D7%93%D7%99%D7%A0%D7%9E%D7%99.html

קטגוריה: אלגוריתמים

תכנון דינמי

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

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

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

Views

ניווט

קהילה

חיפוש

שפות אחרות