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

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

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

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

הבעיה

הכפלת מטריצות

בתכנות, מטריצה היא מערך של מערכים. להלן דוגמה לקטע קוד שמייצר מטריצה בעלת 2 שורות ו5 עמודות, מדפיסה את מספר השורות והעמודות, וקובעת את ערכי השורה הראשונה כולם ל1 וערכי השורה השנייה כולם ל0:

	# Makes a matrix with 2 rows and 5 columns.
1	M = Make-Matrix(2, 5)
	
	# Prints 2.
2	Print( Num-Rows(M) )
	# Prints 5.
3	Print( Num-Cols(M) )

	# Sets all entries in the first row to 1 and all entries
	#	in the second row to 0.
4	for i in [1, ..., 5]
5		M[1][i] = 1	
6		M[2][i] = 0

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

# Takes two matrices (L and R).
# Returns the matrix L * R.
Multiply(L, R)
1	p = Num-Rows(L)
2	q = Num-Cols(L)
3	r = Num-Cols(R)
		
4	M = Make-Matrix(p, r)
		
5	for i = [1, ..., p]
6		for j = [1, ..., r]
7			M[i][j] = 0
				
8			for k = [1, ..., q]
9				M[i][j] = M[i][j] + L[i][k] * R[k][j]

משפט: נניח שמספר השורות של L הוא $\displaystyle p$, מספר השורות של R הוא q, ומספר העמודות של R הוא r. נתן לממש את Multiply בזמן $\displaystyle \Theta (p\cdot q\cdot r)$.

הכפלת שרשרת מטריצות

נניח שמספר השורות של L הוא $\displaystyle p$, מספר השורות של R הוא q, ומספר העמודות של R הוא r. ראינו כבר שנתן לממש את Multiply בזמן $\displaystyle \Theta (p\cdot q\cdot r)$. חברנו, מהנדס אלקטרוניקה במקצועו, מימש את Multiply בחומרה, כך שזמן ההכפלה הוא בדיוק $\displaystyle p\cdot q\cdot r$. מעודד מהצלחתו, מחליט חברנו לפתוח חברת סטארט-אפ כדי להכפיל שרשרת מטריצות. נניח שיש מערך Matrices שבו כל איבר הוא מטריצה. אז הסטארט-אפ של חברנו יחזיר את Matrices[1] * Matrices[2] * ... * Matrices[n]. (נניח ש$\displaystyle n$ הוא אורך Matrices.)

הבעיה היא שהכפלת שרשרת מטריצות מוגדרת היטב מבחינת האלגברה הלינארית, אולם לא מבחינה אלגוריתמית.

דוגמה: נניח שיש לנו שרשרת המטריצות $\displaystyle A_{1}\cdot A_{2}\cdot A_{3}$. המימדים של $\displaystyle A_{1}$ הם $\displaystyle (10,100)$. המימדים של $\displaystyle A_{2}$ הם $\displaystyle (100,5)$. המימדים של $\displaystyle A_{3}$ הם $\displaystyle (5,50)$. אז: אם נכפיל בסדר $\displaystyle (A_{1}\cdot A_{2})\cdot A_{3}$, המחיר יהיה $\displaystyle 10\cdot 100\cdot 5+10\cdot 5\cdot 50=7500$. אם נכפיל בסדר $\displaystyle A_{1}\cdot (A_{2}\cdot A_{3})$, המחיר יהיה $\displaystyle 100\cdot 5\cdot 50+10\cdot 100\cdot 50=75000$.

כפי שמראה הדוגמה, הסדר בו מכפילים את המטריצות יכול להשפיע על הזמן הכולל בצורה מכריעה. לחברנו אין מושג קלוש באיזה סדר להכפיל, ועל כן הוא מבקש מאיתנו לפתור את הבעיה. נניח שברשותינו מערך גלובאלי Matrices של $\displaystyle n$ מטריצות במימדים מתאימים להכפלה. עלינו להדפיס מה זמן ההכפלה הכולל הקצר ביותר, ואת סדר המכפלות שיביא לזמן זה.

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

הרקורסיה הפשוטה

נגדיר כ$\displaystyle m(i,j)$ את הזמן המינימאלי הנדרש להכפלת תת-השרשרת מ$\displaystyle i$ (כולל) ל$\displaystyle j$ (כולל).

עכשיו תורכם: עפ"י הגדרה זו, $\displaystyle m(1,n)$ הנו הזמן שאנו מחפשים. וודא שהנך מבין מדוע.

משפט: $\displaystyle m(i,j)$ מקיים את הנוסחה הבאה: אם $\displaystyle i=j$, אז $\displaystyle m(i,j)=0$.‏ אם $\displaystyle i<j$, אז $m(i,j)=\min _{i\leq k<j}(m(i,k)+m(k+1,j)+pqr(i,k,j))$, כאשר $\displaystyle pqr(i,k,j)$ = Num-Rows(Matrices[i]) * Num-Rows(Matrices[k + 1]) * Num-Cols(Matrices[j]).

הוכחה: המקרה $\displaystyle i=j$ ברור.

אם $\displaystyle i<j$, אז בהכרח מכפילים מ$\displaystyle i$ ל$\displaystyle k$ כלשהו, מ$\displaystyle k+1$ ל$\displaystyle j$, ולבסוף את שתי התוצאות. בלי קשר לדרך בה מכפילים מ$\displaystyle i$ ל$\displaystyle k$, מקבלים מטריצה בעלת מימדים (Num-Rows(Matrices[i]), Num-Cols(Matrices[k])). באותו אופן, בלי קשר לדרך בה מכפילים מ$\displaystyle k+1$ ל$\displaystyle j$, מקבלים מטריצה בעלת מימדים (Num-Rows(Matrices[k + 1]), Num-Cols(Matrices[j])).

מכפלת התוצאות, לכן, תעלה בדיוק $\displaystyle pqr(i,k,j)$. כדי לצמצם את סכום העלויות, לכן, יש להכפיל ביעילות רבה ככל האפשר מ$\displaystyle i$ ל$\displaystyle k$, ומ$\displaystyle k+1$ ל$\displaystyle j$ - אבל עפ"י ההגדרה אלה בדיוק $\displaystyle m(i,k)$ וm$\displaystyle (k+1,j)$.

הבעיה היחידה היא שאיננו יודעים את $\displaystyle k$, אבל קל לבדוק מהו ה$\displaystyle k$ המשתלם ביותר בעזרת לולאה:

Min-Time(i, j)
1	if i == j
2		return 0

3	min-time = ∞

4	for k in [i, ..., j - 1]
5		guess = Min-Time(i, k) + Min-Time(k + 1, j) + PQR(i, k, j)

6		if guess < min-time
7			min-time = guess
			
8	return min-time

כאשר PQR מוגדרת כך:

PQR(i, k, j)
1	p = Num-Rows(Matrices[i])
2	q = Num-Rows(Matrices[k + 1])
3	r = Num-Cols(Matrices[j])

4	return pqr

כדאי לדעת: בבעיה זו, הפתרון האופטימאלי לבעיה בגודל $\displaystyle j-i+1$ כולל פתרון אופטימאלי לאותה בעיה, אך בגודל קטן יותר. ‏ על בעיות כאלה אומרים שיש להן optimal substructure.

אז מה רע?

הפתרון איטי.

משפט: קל לראות שזמן הריצה של Min-Time(n) הוא $\displaystyle \Omega (2^{n})$. ‏

הוכחה: זמן הריצה של Min-Time(n) נתון ע"י נוסחת הנסיגה $\displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)+T(n-i)]+\Theta (n)$. אפשר להמשיך מכאן באינדוקציה. ‏

קצת מפתיע שהפתרון כ"כ איטי, מפני שאם מתבוננים בקוד של Min-Time, אפשר לראות שהוא מבצע מספר לינארי של פעולות (חוץ מקריאות רקורסיביות). יותר מכך, Min-Time יכול להקרא רק עם $\displaystyle n$ ארגומנטים שונים. נראה שמספר הפעמים שהוא נקרא - הוא זה שגבוה כ"כ. במחשבה נוספת, נתן לראות שMin-Time נקרא שוב ושוב עם אותם הארגומנטים.

דוגמה: אם $\displaystyle n=100$, אז: Min-Time(1, 3) נקרא מתוך Min-Time(1, 4), ... , Min-Time(1, 100). Min-Time(1, 40) נקרא מתוך Min-Time(1, 41), ... , Min-Time(1, 100). Min-Time(1, 3) נקרא פעמים רבות לכל אחת מקריאות אלה!

כדאי לדעת: אפשר לראות שMin-Time(1, 3) נקרא הן מתוך Min-Time(1, 4) והן מתוך Min-Time(1, 98). אומרים על כך שיש overlapping subproblems.

תזכור (Memoization)

בנקודה זו אנו יודעים שMin-Time נקרא שוב ושוב עם אותם הארגומנטים. מדוע שלא נשמור פשוט את התוצאה של כל קריאה בפעם הראשונה שחישבנו אותה עבור ארגומנט כלשהו? נעשה זאת כך. ראשית, נגדיר מטריצה גלובאלית M, ונאתחל אותה ל$\displaystyle n^{2}$ ערכי Nil:

# Initializes the M matrix to Nils.
Init(n)
1	M = Make-Matrix(n, n)

2	for i in [1, ..., n]
3		for j in [1, ..., n]
4			M[i][j] = Nil

כעת נשנה את Min-Time כך שקודם יבדוק האם כבר חישבנו את התוצאה עבור הארגומנט הנתון:

Min-Time(i, j)
1	if M[i][j] != Nil
2		return M[i][j]

3	if i == j
4		M[i][j] = 0
5		return 0
	
6	min-time = ∞
	
7	for k in [i, ..., j - 1]
8		guess = Min-Time(i, k) + Min-Time(k + 1, j) + PQR(i, k, j)
	
9		if guess M[i][j] < min-time
10			M[i][j] = min-time = guess
				
11	return min-time

נראה כעת האם שיפרנו בכך את הסיבוכיות. בדומה לצורה שעפי"ה ניתחנו את דג הסלמון, נגדיר את $\displaystyle T'(i,j)$ כזמן שאורכת Min-Time(i, j) בהנחה שכ"א מהקריאות לMin-Time(i, k) וMin-Time(k + 1, j) היא $\displaystyle O(1)$. ונחשוב מדוע המשפט הבא נכון.

משפט: זמן הריצה של Min-Time(1, n) הוא $\displaystyle \sum _{i=1}^{n}\sum _{j=i}^{n}[T'(i,j)]$.

משפט זה עוזר לנו מאד, שכן קל מאד לחשב את $\displaystyle T'(i,j)$:

משפט: $\displaystyle T'(i,j)=\Theta (j-i+1)$

על ידי חיבור שני המשפטים הקודמים, נקבל את זמן הריצה הכולל:

משפט: זמן הריצה של Min-Time(1, n) הוא $\displaystyle \Theta (n^{3})$.

הדפסת הסדר

כעת צריך להדפיס את סדר המכפלות.

Min-Time(i, j)
1	if M[i][j] != Nil
2		return M[i][j]

3	if i == j
4		M[i][j] = 0
5		O[i][j] = i
6		return 0

7	min-time = ∞

8	for k in [i, ..., j - 1]
9		guess = Min-Time(i, k) + Min-Time(k + 1, j) + PQR(i, k, j)

10		if guess < min-time
11			M[i][j] = min-time = guess
12			O[i][j] = k
			
13	return min-time

והנה הפונקציה Print-Order שתדפיס את העצירות:

Print-Orders(i, j)
1	Print( 'To Multiply from ' + i + ' to ' + j)

2	if i == j
3		Print('do nothing')
4		return

5	k = O[i][j]

6	Print('multiply from ' + i + ' to ' + k)
7	Print('multiply from ' + (k + 1) + ' to ' + j)

8	Print-Orders(i, k)
9	Print-Orders(k + 1, j)

לסיכום, כך נדפיס הכל:

1	m = Min-Time( 1, Length(Matrices) )

2	Print(m)

3	Print-Orders( 1, Length(Matrices) )

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

תכנון דינאמי - הכפלת שרשרת מטריצות

הפרק הבא: מבני נתונים