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

נתונה רשימה של $n$ תיבות מלבניות: לכל $1 \leq i \leq n$ נתון האורך $\ell(i)$, הרוחב $w(i)$ והגובה $h(i)$ של התיבה מספר $i$. כל הרוחבים שונים, כל האורכים שונים וכל הגבהים שונים. ברצוננו לבנות מגדל בגובה מרבי באמצעות הנחה של תיבות זו מעל זו. המגדל נחשב יציב כאשר תיבה $j$ מונחת רק מעל תיבה $i$ שמקיימת $w(j) < w(i)$ וגם $\ell(j) < \ell(i)$ (כלומר, כשמימדי הבסיס של התיבה התחתונה גדולים מאלו של העליונה). הציגו אלגוריתם תכנון-דינמי לבניית מגדל יציב בגובה מרבי, לרבות ניסוח של נוסחת נסיגה מתאימה. האלגוריתם נדרש לרוץ בזמן $\Theta(n^2)$. (בהקשר זה פעולות חיבור, חיסור והשוואה של מימדים $\ell(i), w(i), h(i)$ נחשבות פעולות אלמנטריות, שמתבצעות בזמן $\Theta(1)$.)

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

פתרון: **מיון מקדים.** נמיין את התיבות לפי רוחב עולה, $w(1) < w(2) < \cdots < w(n)$. המיון חד-משמעי כי כל הרוחבים שונים. מעתה האינדקסים נתונים בסדר זה. **תת-הבעיה.** לכל $1 \leq i \leq n$ נגדיר $$D[i] = \text{הגובה המרבי של מגדל יציב שהתיבה } i \text{ היא בסיסו}$$ **נוסחת הנסיגה.** $$D[i] = h(i) + \max\Big(\{0\} \cup \big\{\, D[j] \;:\; j < i,\ \ell(j) < \ell(i) \,\big\}\Big)$$ הנמקה: תיבה $j$ יכולה להיות מונחת ישירות מעל $i$ אם ורק אם $w(j) < w(i)$ וגם $\ell(j) < \ell(i)$. אחרי המיון $w(j) < w(i)$ שקול ל-$j < i$, ולכן נותר לבדוק רק את $\ell(j) < \ell(i)$. הקבוצה $\{0\}$ מטפלת במקרה שבו לא ניתן להניח דבר מעל $i$, ואז המגדל הוא התיבה $i$ בלבד. **הפלט.** $\displaystyle\max_{1 \leq i \leq n} D[i]$. **האלגוריתם.** 1. מיין את התיבות לפי $w$ עולה. 2. לכל $i = 1, \dots, n$: אתחל $D[i] \leftarrow h(i)$ ו-$\mathrm{par}[i] \leftarrow \mathrm{NIL}$; לכל $j < i$, אם $\ell(j) < \ell(i)$ וגם $h(i) + D[j] > D[i]$, עדכן $D[i] \leftarrow h(i) + D[j]$ ו-$\mathrm{par}[i] \leftarrow j$. 3. יהי $i^\ast = \arg\max_i D[i]$. החזר $D[i^\ast]$; לשחזור המגדל עצמו עקוב אחר $\mathrm{par}$ החל מ-$i^\ast$. **נכונות.** באינדוקציה על $i$ בסדר הממוין. עבור $i$, כל מגדל יציב שבסיסו $i$ הוא או התיבה $i$ לבדה (גובה $h(i)$), או שמעליה מונחת תיבה $j$ המקיימת $w(j) < w(i)$ ו-$\ell(j) < \ell(i)$ — ואז שאר המגדל הוא מגדל יציב שבסיסו $j$, שגובהו המרבי הוא $D[j]$ לפי הנחת האינדוקציה ($j < i$). לכן המקסימום על פני כל האפשרויות הוא בדיוק אגף ימין של הנסיגה. שימו לב שהיחס "ניתן להניח מעל" הוא **סדר חלקי חסר מעגלים** (שני הרכיבים יורדים ממש), ולכן כל תיבה מופיעה במגדל לכל היותר פעם אחת. **זמן ריצה.** המיון $\Theta(n \log n)$; הלולאה הכפולה מבצעת $\Theta(1)$ עבודה לכל זוג $(i,j)$, כלומר $\Theta(n^2)$; שחזור המגדל $O(n)$. סה"כ $\Theta(n^2)$ כנדרש. $\blacksquare$