שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2022 - תכנות דינמי

נתונה קבוצה של $n$ ערים $a_1, \ldots, a_n$ ומטריצה $C[i,j]$ עבור $n \geq i,j \geq 1$ שנותנת את עלות הנסיעה הישירה מ$a_i$ ל$a_j$ (בלי תחנות ביניים). אם אין אפשרות לנסיעה ישירה מ$a_i$ ל$a_j$, אז $C[i,j] = \infty$. נרצה לבנות מטריצה $D[i,j]$ שנותנת את עלות הנסיעה הזולה ביותר מ$a_i$ ל$a_j$, כאשר מותר להשתמש בתחנות ביניים (אין צורך לפרט מיהן התחנות על המסלול). רמז: תכנות דינמי. א. (13) הגדירו נוסחה רקורסיבית $E(i,j,k)$ עבור $n \geq k \geq 0$, $n \geq i,j \geq 1$, שתחזיר את עלות הנסיעה הזולה ביותר מ$a_i$ ל$a_j$, כאשר מותר להשתמש בתחנות ביניים רק מתוך הקבוצה $\{1,2,\ldots,k\}$; יש לכלול את תנאי העצירה בנוסחה. ב. (6) הגדירו את המטריצה $D$ שברצוננו לבנות במונחים של הנוסחה הרקורסיבית $E(i,j,k)$. ג. (6) מהן סיבוכיות הזמן וסיבוכיות המקום הנדרשות עבור אלגוריתם התכנות הדינמי? נמקו. שימו לב כי אין צורך לשחזר את המסלולים.

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

פתרון: ### סעיף א: נוסחה רקורסיבית נגדיר את **התת-בעיה** באופן הבא: $E(i,j,k)$ היא עלות המסלול הזול ביותר מהעיר $a_i$ לעיר $a_j$, כאשר מותר להשתמש בתחנות ביניים רק מתוך הקבוצה $\{a_1, a_2, obreakspace ldots, a_k\}$. **מקרה הבסיס (תנאי העצירה):** עבור $k=0$, אין תחנות ביניים מותרות. לכן, המסלול היחיד האפשרי מ-$a_i$ ל-$a_j$ הוא המסלול הישיר, שעלותו נתונה במטריצת הקלט $C$. לכן, עבור $k=0$ וכל $1 \leq i,j \leq n$: $E(i,j,0) = C[i,j]$ **הצעד הרקורסיבי:** עבור $k > 0$, נרצה לחשב את $E(i,j,k)$ בהתבסס על ערכים עם אינדקס $k$ קטן יותר. המסלול הזול ביותר מ-$a_i$ ל-$a_j$ המשתמש בתחנות ביניים מתוך $\{a_1, obreakspace ldots, a_k\}$ יכול להיות משני סוגים: 1. **המסלול אינו עובר דרך העיר $a_k$.** במקרה זה, המסלול משתמש רק בתחנות ביניים מתוך הקבוצה $\{a_1, obreakspace ldots, a_{k-1}\}$. עלות המסלול המיטבי במקרה זה היא, על פי ההגדרה, $E(i,j,k-1)$. 2. **המסלול כן עובר דרך העיר $a_k$.** במקרה זה, ניתן לפרק את המסלול לשניים: מסלול מ-$a_i$ ל-$a_k$, ומסלול מ-$a_k$ ל-$a_j$. כדי שהמסלול הכולל יהיה הזול ביותר, כל אחד מהקטעים חייב להיות הזול ביותר האפשרי. תחנות הביניים בכל אחד מהקטעים יכולות להיות רק מתוך הקבוצה $\{a_1, obreakspace ldots, a_{k-1}\}$ (מכיוון ש-$a_k$ היא נקודת החיבור, לא תחנת ביניים באף אחד מהקטעים). לכן, עלות המסלול במקרה זה היא סכום העלויות של שני הקטעים: $E(i,k,k-1) + E(k,j,k-1)$. העלות המינימלית $E(i,j,k)$ היא המינימום מבין שני המקרים הללו. **הנוסחה הרקורסיבית המלאה:** $$ E(i,j,k) = \begin{cases} C[i,j] & k=0 \\ \min \{ E(i,j,k-1), E(i,k,k-1) + E(k,j,k-1) \} & 1 \leq k \leq n \end{cases} $$ $\blacksquare$ ### סעיף ב: הגדרת המטריצה D המטריצה $D[i,j]$ מייצגת את עלות הנסיעה הזולה ביותר מ-$a_i$ ל-$a_j$ כאשר מותר להשתמש **בכל** עיר כתחנת ביניים. קבוצת כל הערים היא $\{a_1, a_2, obreakspace ldots, a_n\}$. על פי הגדרת הנוסחה הרקורסיבית מסעיף א', $E(i,j,n)$ היא בדיוק עלות הנסיעה הזולה ביותר מ-$a_i$ ל-$a_j$ כאשר מותר להשתמש בתחנות ביניים מתוך הקבוצה $\{a_1, obreakspace ldots, a_n\}$. לכן, ניתן להגדיר את המטריצה $D$ באופן הבא: $$ D[i,j] = E(i,j,n) \quad \forall 1 \leq i,j \leq n $$ $\blacksquare$ ### סעיף ג: ניתוח סיבוכיות האלגוריתם המבוסס על **תכנות דינמי** יבנה טבלה תלת-ממדית (או מערך) כדי לאחסן את הפתרונות של כל תתי-הבעיות $E(i,j,k)$ ויחשב אותם באופן איטרטיבי (bottom-up), החל מ-$k=0$ ועד $k=n$. **סיבוכיות זמן:** האלגוריתם ירוץ בשלוש לולאות מקוננות: 1. לולאה חיצונית על $k$ מ-1 עד $n$. 2. לולאה אמצעית על $i$ מ-1 עד $n$. 3. לולאה פנימית על $j$ מ-1 עד $n$. בכל איטרציה של הלולאה הפנימית ביותר, מתבצע חישוב של $E(i,j,k)$ אשר דורש מספר קבוע של פעולות (השוואת מינימום וחיבור). לכן, הפעולה בתוך הלולאות היא $O(1)$. סך הפעולות הוא $n \times n \times n = n^3$. לכן, **סיבוכיות הזמן היא $O(n^3)$**. **סיבוכיות מקום:** במימוש נאיבי, נצטרך לשמור את כל ערכי $E(i,j,k)$ בטבלה תלת-ממדית בגודל $n \times n \times (n+1)$, מה שדורש **סיבוכיות מקום של $O(n^3)$**. *נימוק לאופטימיזציה:* ניתן לשים לב שהחישוב של שכבה $k$ (כלומר, כל הערכים $E(i,j,k)$ עבור $k$ קבוע) תלוי אך ורק בערכים מהשכבה הקודמת, $k-1$. לכן, אין צורך לשמור את כל $n+1$ השכבות בזיכרון בו-זמנית. ניתן להסתפק בשתי מטריצות דו-ממדיות בגודל $n \times n$ (אחת עבור שכבה $k-1$ ואחת עבור שכבה $k$), ולהעתיק ביניהן. זה מוריד את סיבוכיות המקום ל-$O(n^2)$. ניתן אפילו לבצע את העדכון במקום (in-place) עם מטריצה אחת בלבד בגודל $n \times n$, ולכן סיבוכיות המקום המיטבית היא **$O(n^2)$**. $\blacksquare$