שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2021 - תכנות דינמי

שאלה 1 – תכנון דינאמי (בחירת מלונות לאורך מסלול) ברצוננו לערוך מסע לאורכו של מסלול ישר מנקודת-התחלה $s$ לנקודת-סיום $f$. נתונה רשימה של מיקומי-מלונות, כך שמלון $i$ ממוקם בדיוק $p_i$ קילומטרים מתחילת-המסלול. $p_1 < ... < p_n$ במהלך המסע לנים בכל לילה במלון אחר. החופשה מוגבלת בזמן, ולכן חייבים להשלים את המסע תוך לכל היותר $t$ ימים ($2 \leq t \leq n$). ידוע שכמות-המאמץ, שנדרש ביום-הליכה הינה הריבוע של המרחק $d$, שהולכים באותו יום. ברצוננו לבחור את נקודות-הלינה, כך שנמזער את סכום המאמצים בכל המסע. הציגו אלגוריתם יעיל ככל האפשר לבעיה, שרץ בזמן פולינומי ביחס ל-$t$ וביחס ל-$n$. נדרשת תשובה שמבוססת על נוסחה רקורסיבית בשיטה של תכנון-דינאמי. מגדירים מערך שמשמעותו ____________________________________________(5 נק׳) נוסחת-הנסיגה עבור המערך הינה (נדרש הסבר קצר)_______________________________ _______________________________________________________________(22 נק׳) איך ממלאים את התאים במערך_________________________________________(3 נק׳) זמן הריצה (הסבר קצרצר)_____________________________________________(3 נק׳)

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

פתרון: ראשית, נגדיר את נקודות המסלול בצורה מסודרת. תהי $p_0$ נקודת ההתחלה, שמרחקה מתחילת המסלול הוא 0. יהיו $p_1, \dots, p_n$ המלונות הנתונים, ונוסיף את נקודת הסיום $f$ בתור $p_{n+1}$. נסמן ב-$d_i$ את המרחק של נקודה $p_i$ מתחילת המסלול. כעת, יש לנו $n+2$ נקודות פוטנציאליות לעצירה, $p_0, p_1, \dots, p_{n+1}$. **מגדירים מערך שמשמעותו:** נגדיר טבלת **תכנון דינמי** $C$ בגודל $(n+2) \times (t+1)$. הערך בתא $C[i][k]$ ייצג את **המאמץ הכולל המינימלי** הנדרש כדי להגיע לנקודה $p_i$ (כאשר $0 \le i \le n+1$) לאחר **בדיוק** $k$ ימי הליכה (כלומר, $k$ מקטעי נסיעה). **נוסחת-הנסיגה עבור המערך הינה:** כדי לחשב את $C[i][k]$, נשים לב שכדי להגיע לנקודה $p_i$ ביום ה-$k$, היינו חייבים לשהות בנקודה קודמת כלשהי $p_j$ ($0 \le j < i$) בסוף היום ה-$(k-1)$. המאמץ של היום ה-$k$ במסלול כזה הוא ריבוע המרחק בין $p_j$ ל-$p_i$, כלומר $(d_i - d_j)^2$. העלות הכוללת להגיע ל-$p_i$ דרך $p_j$ היא סכום העלות המינימלית להגיע ל-$p_j$ ב-$k-1$ ימים, והמאמץ של היום האחרון. כדי למצוא את המאמץ המינימלי האפשרי להגיע ל-$p_i$ ב-$k$ ימים, עלינו לבחור את הנקודה הקודמת $p_j$ אשר ממזערת את העלות הכוללת. מכאן, **נוסחת הנסיגה** היא: $C[i][k] = \min_{0 \le j < i} \{ C[j][k-1] + (d_i - d_j)^2 \}$ עבור $1 \le i \le n+1$ ו-$1 \le k \le t$. **תנאי בסיס:** העלות להישאר בנקודת ההתחלה ($p_0$) לאחר 0 ימים היא 0, כלומר $C[0][0] = 0$. כל שאר התאים בטבלה יאותחלו לערך אינסופי ($\") כדי לציין מסלולים בלתי אפשריים. הפתרון הסופי לבעיה הוא הערך $C[n+1][t]$. הסיבה לכך היא שפונקציית המאמץ, $f(d)=d^2$, היא **פונקציה קמורה**. תכונה זו גורמת לכך שפיצול קטע נסיעה ארוך למספר קטעים קצרים יותר תמיד יקטין (או לא יגדיל) את סך המאמץ. לכן, הפתרון האופטימלי ישאף לנצל את מספר הימים המקסימלי המותר, $t$, כדי לפזר את המרחק הכולל על פני כמה שיותר ימי הליכה. $\blacksquare$ **איך ממלאים את התאים במערך:** נמלא את טבלת ה-DP, $C$, **עמודה אחר עמודה**, החל מ-$k=1$ ועד $k=t$. בכל עמודה $k$, נחשב את הערכים עבור $i=1$ עד $i=n+1$. סדר מילוי זה מבטיח שבכל פעם שנחשב את $C[i][k]$, כל הערכים בעמודה הקודמת, $C[j][k-1]$, שעליהם הוא תלוי, כבר חושבו. **זמן הריצה:** האלגוריתם מורכב משלוש לולאות מקוננות: 1. לולאה חיצונית על מספר הימים, $k$, מ-1 עד $t$ (סיבוכיות $O(t)$). 2. לולאה אמצעית על נקודת היעד הנוכחית, $i$, מ-1 עד $n+1$ (סיבוכיות $O(n)$). 3. לולאה פנימית על הנקודה הקודמת האפשרית, $j$, מ-0 עד $i-1$ (סיבוכיות $O(n)$). הפעולות בתוך הלולאה הפנימית לוקחות זמן קבוע, $O(1)$. לכן, **סיבוכיות הזמן** הכוללת של האלגוריתם היא $O(t \cdot n \cdot n) = O(t n^2)$. זהו זמן ריצה פולינומי בגודל הקלט כנדרש.