יסודות תכנות דינמיים


רמת קושי קַל
נשאל לעתים קרובות אינפוסיס מאק
תכנות דינמי תֵאוֹרִיָה

ביסודות תכנות דינמי, נסקור את היסודות של DP וההבדלים בינה לבין השיטה החמדנית, Divide and Conquer and Recursion.

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

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

כמה בעיות בסיסיות של DP

  • בעיית מספרים מכוערת
  • החלפת מטבע
  • מספרי פיבונאצ'י
  • בעיית מספרי פעמונים
  • מגדל האנוי
  • מספרי פעמונים
  • בעיית כנאפה

תכנות דינמי (DP) לעומת שיטת חמדן

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

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

תכנות דינמי (DP) לעומת שיטת חלוקה וכיבוש

בחלוקה ובכיבוש אנו מחלקים בעיה לבעיות משנה ופותרים כל בעיית משנה באופן עצמאי. עם זאת, ב- DP במקום לפתור בעיות באופן עצמאי, אנו משתמשים בתוצאות שהושגו בעבר לצורך חישובים חדשים. במילים אחרות, אנו יכולים לומר Divide and Conquer + Memoization = גישה דינמית מלמעלה למטה.

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

תכנות דינמי (DP) לעומת שיטת רקורסיה

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

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

במאמר זה סקרנו בערך תכנות דינמי יסודות. במאמרים הבאים נעסוק בכמה בעיות בסיסיות בנושא DP.

התייחסות שאלות ראיון