תכנות דינמית: מאפיינים, דוגמה, יתרונות, חסרונות - טֶכנוֹלוֹגִיָה - 2025

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

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

תכנות דינמי. תתי-בעיות שהונחו ברצף פיבונאצ'י. מקור: המפקח בויקימדיה, en: משתמש: Dcoatzee, מעקב אחר המשתמש: Stannered / Public Public

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

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

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

תכונות של תכנות דינמי

המאפיינים המהותיים הבאים הם מה שעליך להיות לך עם בעיה לפני שתוכל ליישם תכנות דינמית:

תת מבנה אופטימלי

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

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

כלומר, בדרך הקצרה הזו r ניתן לקחת כל קודקוד ביניים i. אם r הוא באמת המסלול הקצר ביותר, אז אפשר לחלק אותו לתת-הכבישים r1 (מ- s ל- i) ו- r2 (מ- i ל- t), באופן כזה שאלו הם בתורם המסלול הקצר ביותר בין הקודקודים המתאימים.

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

בעיות משנה חופפות

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

לדוגמה, כדי ליצור את סדרת פיבונאצ'י, אנו יכולים לשקול ניסוח רקורסיבי זה: Fn = F (n - 1) + F (n - 2), אם ניקח כמקרה בסיס ש- F1 = F2 = 1. אז יהיה לנו: F33 = F32 + F31, ו- F32 = F31 + F30.

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

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

גישה מלמעלה למטה

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

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

גישה מלמטה למעלה

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

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

השוואה עם טכניקות אחרות

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

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

דוגמא

צעדים מינימליים כדי להגיע ל -1

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

- חיסור 1 מהמספר. (e = e-1).

- אם זה מתחלק ב -2, הוא מחולק ב -2 (אם e% 2 == 0, אז e = e / 2).

- אם זה מתחלק ב -3, הוא מחולק על ידי 3 (אם e% 3 == 0, אז e = e / 3).

בהתבסס על הצעדים שלעיל, יש למצוא את המספר המינימלי של שלבים אלה כדי להביא e ל 1. לדוגמה:

- אם e = 1, תוצאה: 0.

- אם e = 4, תוצאה: 2 (4/2 = 2/2 = 1).

- כאשר e = 7, תוצאה: 3 (7-1 = 6/3 = 2/2 = 1).

מוֹקֵד

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

לדוגמה, אם e = 10, הצעדים יהיו: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 שלבים). עם זאת, הצורה האופטימלית היא: 10-1 = 9/3 = 3/3 = 1 (3 שלבים). לכן, יש לנסות את כל הצעדים האפשריים שניתן לבצע עבור כל ערך של n שנמצא, תוך בחירת המספר המינימלי של אפשרויות אלה.

הכל מתחיל ברקורסיה: F (e) = 1 + דקות {F (e-1), F (e / 2), F (e / 3)} אם e> 1, לוקח כמקרה בסיסי: F (1) = 0. לאחר שמשוואת הישנות תוכלו להתחיל לקוד את הרקורסיה.

עם זאת ניתן לראות שיש בו בעיות משנה חופפות. יתר על כן, הפיתרון האופטימלי עבור קלט נתון תלוי בפתרון האופטימלי של בעיות המשנה שלה.

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

שינון

תכנות דינאמי מלמטה למעלה

יתרון

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

אלגוריתמים קודרים לעומת תכנות דינמיות

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

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

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

חסרונות

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

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

- בתכנות דינאמי נקראות פונקציות רקורסיביות. זה שומר על זיכרון הערימה גדל ללא הרף.

רקורסיה לעומת תכנות דינמיות

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

אם אתה רוצה שהתוכנית תפעל מהר יותר ואין לה מגבלות זיכרון, עדיף להשתמש בתכנות דינמיות.

יישומים

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

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

אלגוריתמים המבוססים על תכנות דינמיות

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

- סדרת מספרים של פיבונאצ'י.

- מגדלי האנוי.

- כל זוגות המסלולים הקצרים יותר דרך פלויד-ורשל.

- בעיית תרמיל.

- תזמון פרויקטים.

הדרך הקצרה ביותר דרך Dijkstra.

- בקרת טיסה ובקרת רובוטיקה.

- בעיות מיטוב מתמטיות.

- Timeshare: תזמן את העבודה כדי למקסם את השימוש במעבד.

סדרת מספרי פיבונאצ'י

מספרי פיבונאצ'י הם המספרים שנמצאים ברצף הבא: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 וכו '.

בטרמינולוגיה מתמטית, רצף Fn של מספרים פיבונאציים מוגדר על ידי נוסחת הישנות: F (n) = F (n -1) + F (n -2), כאשר F (0) = 0 ו- F ( 1) = 1.

גישה מלמעלה למטה

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

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

גישה מלמטה למעלה

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

הפניות

1. Vineet Choudhary (2020). מבוא לתכנות דינמי. Insider Developer. נלקח מ: Developerinsider.co.
2. אלכס אליין (2020). תכנות דינמית ב- C ++. C תכנות. נלקח מ: cprogramming.com.
3. אחרי האקדמיה (2020). רעיון התכנות הדינמי. נלקח מ: afteracademy.com.
4. Aniruddha Chaudhari (2019). תכנות ושחזור דינמי - הבדל, יתרונות עם דוגמא. ערכת CSE. נלקח מ: csestack.org.
5. קוד שף (2020). הדרכה לתכנות דינמי. נלקח מ: codechef.com.
6. תכנות (2020). תכנות דינמי. נלקח מ: programiz.com.