מבני נתונים ואלגוריתמים - מחברת קורס/גרפים/אלגוריתם "הכפלת מטריצות"

דף זה הוא השני מבין שלושה דפים העוסקים באלגוריתמים למציאת המסלול הזול ביותר בגרף מכוון בין כל שני צמתים.

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

הרעיון הכללי

שימו לב: נזכר שבמהלך החומר על גרפים, מסלול זול מתייחס לסכום מחירי הקשתות, ומסלול קצר מתייחס למספר הקשתות.

נצמצם מעט את הבעיה בכך שלא נחפש את המסלול הזול ביותר באופן כללי, אלא המסלול הזול ביותר בעל אורך מסויים.

הגדרה: נגדיר כ$\displaystyle d^{(m)}(u,v)$ את מחיר המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ שארכו בדיוק $\displaystyle m$.

מעניין לראות שבגרף ה"מוסף", אפשר להרחיב את משמעות ההגדרה. המשפט הבא מפרט זאת.

משפט: בגרף ה"מוסף", $\displaystyle d^{(m)}(u,v)$ שווה בדיוק למחיר המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ שארכו לכל היותר $\displaystyle m$.

לפני שנוכיח את המשפט, להלן דוגמה.

דוגמה: להלן הגרף המקורי לבעיה: בעיית המסלולים הזוגים לכלל הזוגות. (נזכר שהגרף ה"מוסף" נוצר על ידי הוספת קשתות במחירים 0 ואינסוף.) בגרף המקורי: המסלול הזול ביותר מ$\displaystyle 1$ ל$\displaystyle 2$ הוא $\displaystyle 1\rightarrow 4\rightarrow 2$, ועלותו 2. אין מסלול מ$\displaystyle 1$ ל$\displaystyle 2$ באורך 4. בגרף ה"מוסף": המסלול הזול ביותר מ$\displaystyle 1$ ל$\displaystyle 2$ גם הוא $\displaystyle 1\rightarrow 4\rightarrow 2$, ועלותו 2. המסלול הזול ביותר (אך לא היחידי) מ$\displaystyle 1$ ל$\displaystyle 2$ באורך 4 הוא $\displaystyle 1\rightarrow 4\rightarrow 2\rightarrow 2\rightarrow 2$, ועלותו 2.

כעת נוכיח את המשפט.

הוכחה: נניח בשלילה ש$\displaystyle P$, המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ הוא בעל אורך $\displaystyle m'$ הקטן (ממש) מ$\displaystyle m$. אם זה המצב, נוכל לבנות מסלול בדיוק באותו מחיר, שארכו בדיוק $\displaystyle m$; המסלול מורכב משני חלקים: החלק הראשון הוא $\displaystyle P$, שארכו $\displaystyle m'$, והחלק השני מורכב מ$\displaystyle m-m'$ "סיבובים" מהסוג $\displaystyle v\rightarrow v$, שעלותם 0.

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

משפט: נקבע את $\displaystyle n$ כמספר הצמתים בגרף. אז מחיר המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ הוא $\displaystyle d^{(n-1)}(u,v)$.

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

משפט: לכל $\displaystyle m$,‏ $\displaystyle d^{(m)}(u,v)$ הוא: Edge-Costs[u][v], אם $\displaystyle m=1$. $\displaystyle min_{w\in V}\{d^{(m-1)}(u,w)+$ Edge-Costs[w][v]$\displaystyle \}$, אם $\displaystyle m>1$.

הוכחה: אם $\displaystyle m=1$, אז מחיר המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ הוא בדיוק מחיר הקשת מ$\displaystyle u$ ל$\displaystyle v$ (נזכר שבגרף ה"מוסף" בהכרח יש קשת כזו).

אם $\displaystyle m>1$, אז המסלול הזול ביותר בהכרח מתחלק לשני חלקים:

1. חלק ראשון, מ$\displaystyle u$ ועד $\displaystyle w$ כלשהו, באורך $\displaystyle m-1$.
2. חלק שני, מ$\displaystyle w$ ל$\displaystyle v$, באורך 1.

נשים לב גם שבהכרח משתמשים במסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle w$ באורך $\displaystyle m-1$ - אם לא כן, היינו יכולים למצוא מסלול זול יותר.

היות שאיננו יודעים מיהו $\displaystyle w$, לוקחים את המינימום על פני כל האפשרויות.

פסוודו-קוד

להלן הפסוודו-קוד לאלגוריתם:

Matrix-Multiplication(G, Edge-Costs, m)
1	if m == 1
2		return Edge-Costs

3	D' = Matrix-Multiplication(G, Edge-Costs, m - 1)

4	n = Length( V(G) )

5	D = Make-Matrix(n, n)
	
6	for u in V(G)
7		for v in V(G)
8			D[u][v] = ∞

9			for w in V(G)
10				if D[u][v] > D'[u][w] + Edge-Costs[w][v]
11					D[u][v] = D'[u][w] + Edge-Costs[w][v]
	
12	return D

ולהלן דוגמה לשימוש בו:

1	n = Length( V(G) )

2	D = Matrix-Multiplication(G, Edge-Costs, n - 1)

	# Prints 2.
3	Print( D[1][2] )

	# Prints ∞.
4	Print( D[2][1] )

בMatrix-Multiplication, שורות 1-2 מזהות את תנאי העצירה. כפי שהוכחנו מקודם, אם $\displaystyle m=0$ אז המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ הוא בדיוק הכניסה ה$\displaystyle (u,v)$ במטריצה Edge-Costs; לכן אנו מחזירים מטריצה זו במקרה זה.

שורה 3 מחשבת את המסלולים הזולים ביותר עבור המקרה הקצר באחת (כלומר $\displaystyle m-1$), ושומרת את התוצאה במטריצה זמנית D'. כעת 5-12 מייצרות את המטריצה עבור המרחק $\displaystyle m$, וממלאות אותה. נשים לב שעבור כל $\displaystyle u$ ו$\displaystyle v$ (הלולאות ב6 ו7), עוברים על כל צומת ביניים $\displaystyle w$ אפשרי, בדיוק כפי שראינו ברעיון הכללי.

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

ניתוח סיבוכיות

ראשית, קל לראות כי 6-11 הן $\displaystyle \Theta (n^{3})$, וזאת עפ"י הדמיון לקוד להכפלת שתי מטריצות (במובן אלגברה לינארית). , קל גם לראות שהן למעשה קובעות את זמן הריצה של קריאה יחידה של הפונקציה. נגדיר כ$\displaystyle n$ את מספר צמתי הגרף, וכ$\displaystyle T(m)$ את זמן הריצה של Matrix-Multiplication(G, Edge-Costs, m). אז $\displaystyle T(m)=T(m-1)+\Theta (n^{3})$, ולכן $\displaystyle T(n-1)=\Theta (n^{4})$.

כדאי לדעת: בספר הקורס ישנה גרסה שסיבוכיותה $\displaystyle \Theta (n^{3}\cdot \log(n))$, אלא שבאלגוריתם Floyd-Warshall נראה פתרון שעובד בזמן $\displaystyle \Theta (n^{3})$, ולכן זה אינו מעניין יותר מדי.

הפרק הקודם: מסלולים זולים לכלל הזוגות

אלגוריתם "הכפלת מטריצות"

הפרק הבא: אלגוריתם Floyd-Warshall