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

נתון גרף מכוון $G = (V, E)$ עם משקלים אי-שליליים $c(e) \geq 0$ על הצלעות ונתון קדקוד מסוים $r \in V$. הביטו באלגוריתם הבא: (i) מאתחלים מערך חד-ממדי $A$ באמצעות הכלל: $$A[v] = \begin{cases} 0, & v = r \\ \infty, & v \neq r \end{cases}$$ (ii) לולאה חיצונית: חוזרים שוב ושוב על הפעולה הבאה. (ii.1) לולאה פנימית: סורקים את הצלעות בסדר לקסיקוגרפי. לכל צלע $e = (u, v) \in E$ מבצעים: אם $A[v] > A[u] + c(e)$ אז מעדכנים $A[v] \leftarrow A[u] + c(e)$. (ii.2) אם בהרצה הנוכחית של כל הלולאה הפנימית לא בוצע אף עדכון, אז האלגוריתם מסיים. (א) רישמו מה מחשב האלגוריתם (אין צורך להוכיח נכונות). (ב) יהי $B(n)$ המספר המרבי של איטרציות שמתבצעות בלולאה החיצונית על גרפים בעלי $n$ קדקודים. חשבו את $B(n)$, והציגו סדרת גרפים $G_n$ עליהם מתבצעות בדיוק $B(n)$ איטרציות. (ג) הציגו סדרת גרפים אחרת $G'_n$, עבורם נכנסים ללולאה החיצונית פעמיים בלבד, וזאת למרות ששמספר הצלעות שלהם זהה לגרפים מהסעיף הקודם, כלומר $|E(G'_n)| = |E(G_n)|$ לכל $n$.

רמז: שימו לב כיצד המידע על המרחקים מתקדם מהמקור $r$ לאורך המסלולים בגרף בכל איטרציה של הלולאה החיצונית. מהו המבנה הגרפי שיגרום להתקדמות האיטית ביותר (הגרועה ביותר) של מידע זה?

פתרון: (א) האלגוריתם מחשב את **אורכי המסלולים הקצרים ביותר** מהקדקוד המקור $r$ לכל שאר הקדקודים בגרף, $G$. המערך $A$ בסיום האלגוריתם יכיל את המרחקים הללו, כלומר $A[v] = \delta(r, v)$ לכל $v \in V$, כאשר $\delta(r, v)$ הוא אורך המסלול הקצר ביותר מ-$r$ ל-$v$. אלגוריתם זה הוא וריאציה של אלגוריתם **בלמן-פורד**. הפעולה הפנימית (ii.1) היא פעולת **ריפוי (relaxation)**, והאלגוריתם מפסיק כאשר איטרציה שלמה על כל הצלעות אינה מניבה שיפור באורכי המסלולים הנשמרים במערך $A$. (ב) המספר המרבי של איטרציות הוא $B(n) = n$. סדרת גרפים $G_n$ המשיגה חסם זה היא **גרף מסלול (path graph)** בעל $n$ קדקודים. * **קדקודים**: $V_n = \{v_1, v_2, \ldots, v_n\}$. * **צלעות**: $E_n = \{(v_i, v_{i+1}) \mid 1 \le i < n\}$. * **מקור**: $r = v_1$. * **משקלים**: $c(v_i, v_{i+1}) = 1$ לכל צלע. **מעקב אחר האלגוריתם על $G_n$:** * **אתחול**: $A[v_1]=0$ ו-$A[v_i]=\infty$ לכל $i > 1$. * **איטרציה 1**: רק הצלע $(v_1, v_2)$ תגרום לעדכון: $A[v_2] \leftarrow A[v_1] + 1 = 1$. בסוף האיטרציה, $A = [0, 1, \infty, \ldots, \infty]$. * **איטרציה 2**: כעת $A[v_2]$ סופי, ולכן הצלע $(v_2, v_3)$ תגרום לעדכון: $A[v_3] \leftarrow A[v_2] + 1 = 2$. בסוף האיטרציה, $A = [0, 1, 2, \infty, \ldots, \infty]$. * תהליך זה נמשך, כאשר בכל איטרציה $k$ (עבור $k < n$), הערך $A[v_{k+1}]$ מתעדכן לראשונה לערך $k$. * **איטרציה $n-1$**: הערך $A[v_n]$ מתעדכן ל-$n-1$. בשלב זה, כל ערכי המרחק במערך $A$ הם אורכי המסלולים הקצרים ביותר מהמקור. * **איטרציה $n$**: תתבצע סריקה מלאה של כל הצלעות, אך אף עדכון לא יתבצע. למשל, עבור הצלע $(v_i, v_{i+1})$, התנאי $A[v_{i+1}] > A[v_i] + c(v_i, v_{i+1})$ הופך ל- $i > (i-1) + 1$, שהוא שקר. מכיוון שלא בוצע אף עדכון באיטרציה זו, האלגוריתם מסיים. סה"כ, הלולאה החיצונית רצה $n$ פעמים. (ג) סדרת גרפים $G'_n$ שעבורה האלגוריתם מבצע שתי איטרציות בלבד היא **גרף כוכב (star graph)**, שהמקור $r$ במרכזו. * **קדקודים**: $V'_n = \{v_1, v_2, \ldots, v_n\}$. * **צלעות**: $E'_n = \{(v_1, v_i) \mid 2 \le i \le n\}$. * **מקור**: $r = v_1$. * **משקלים**: $c(v_1, v_i) = 1$ לכל צלע. מספר הצלעות בגרף זה הוא $|E'_n| = n-1$, הזהה למספר הצלעות ב-$G_n$. **מעקב אחר האלגוריתם על $G'_n$:** * **אתחול**: $A[v_1]=0$ ו-$A[v_i]=\infty$ לכל $i > 1$. * **איטרציה 1**: בלולאה הפנימית, כל צלע $(v_1, v_i)$ תיסרק. עבור כל $i \in \{2, \ldots, n\}$, התנאי $A[v_i] > A[v_1] + c(v_1, v_i)$ (כלומר, $\infty > 0+1$) מתקיים, ולכן יתבצע עדכון $A[v_i] \leftarrow 1$. בסוף האיטרציה, כל ערכי המרחק הנכונים חושבו: $A = [0, 1, 1, \ldots, 1]$. מכיוון שבוצעו עדכונים, האלגוריתם ממשיך. * **איטרציה 2**: בלולאה הפנימית, כל צלע $(v_1, v_i)$ תיסרק שוב. הפעם, התנאי $A[v_i] > A[v_1] + c(v_1, v_i)$ (כלומר, $1 > 0+1$) אינו מתקיים לאף צלע. לכן, לא יתבצע אף עדכון. מכיוון שלא בוצע עדכון באיטרציה זו, האלגוריתם יסיים. סה"כ, הלולאה החיצונית רצה 2 פעמים בלבד.