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

ברצוננו לערוך מסע לאורך מסלול ישר מנקודת-התחלה $s$ (במיקום $0$) לנקודת-סיום. נתונה רשימה $p_1<p_2<\cdots<p_n$ של מיקומי-מלונות, כך שמלון $i$ ממוקם בדיוק $p_i$ קילומטרים מתחילת-המסלול, והמלון האחרון $p_n$ הוא היעד. בכל לילה לנים במלון (אחר). ידוע שכמות-המאמץ שנדרשת ביום-הליכה הינה $d^2$ — הריבוע של המרחק $d$ שהולכים באותו יום. ברצוננו לבחור את נקודות-הלינה כך שנמזער את סכום המאמצים בכל המסע, תוך השלמתו בלכל היותר $t$ ימים ($t<n$ נתון). הציגו אלגוריתם תכנון-דינמי יעיל ככל האפשר, שזמן ריצתו פולינומי ב-$t$ וב-$n$.

רמז: הגדירו $\text{Opt}(i,j)$ = מאמץ מזערי להגיע למלון $i$ ב-$j$ ימים. חלקו לפי מלון הלינה הקודם $k<i$: $\text{Opt}(i,j)=\min_{k<i}\big(\text{Opt}(k,j-1)+(p_i-p_k)^2\big)$, ואתחלו $\text{Opt}(i,1)=p_i^2$.

פתרון: נגדיר $\text{Opt}(i,j)$ = כמות-המאמץ המזערית הנדרשת כדי להגיע למלון $i$ תוך **בדיוק** $j$ ימים (לינות). **נוסחת נסיגה:** עבור מלון $i$ ו-$j\ge 2$, בוחרים באיזה מלון $k<i$ לנו בלילה הקודם: $$\text{Opt}(i,j)=\min_{k<i}\Big(\text{Opt}(k,\,j-1)+(p_i-p_k)^2\Big).$$ **אתחול:** $\text{Opt}(i,1)=(p_i-0)^2=p_i^{\,2}$ (ביום הראשון הולכים מנקודת-ההתחלה, במיקום $0$, אל מלון $i$). **סדר מילוי:** $j=1,\dots,t$, ולכל $j$ עבור $i=1,\dots,n$. **פלט:** $\min_{1\le j\le t}\text{Opt}(n,j)$ — המאמץ המזערי להגיע למלון האחרון $n$ בתוך $\le t$ ימים. (חלוקה לעוד ימים אף פעם לא מגדילה את סכום ריבועי-המרחקים, ולכן המינימום מתקבל למעשה ב-$j=t$.) **זמן ריצה:** טבלה בגודל $n\times t$, וכל תא דורש מינימום על פני $<n$ אפשרויות — סה"כ $\Theta(n^2 t)$. $\blacksquare$