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

דף זה הוא השני משני דפים שעוסק ביישום רעיון התכנון הדינמי. אנו נתמקד ברעיון ה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]

תבנית:משפט

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

נניח שמספר השורות של תבנית:קוד בשורה הוא $p$, מספר השורות של תבנית:קוד בשורה הוא תבנית:קוד בשורה, ומספר העמודות של תבנית:קוד בשורה הוא תבנית:קוד בשורה. ראינו כבר שנתן לממש את תבנית:קוד בשורה בזמן $\mathrm{\Theta }(p\cdot q\cdot r)$. חברנו, מהנדס אלקטרוניקה במקצועו, מימש את תבנית:קוד בשורה בחומרה, כך שזמן ההכפלה הוא בדיוק $p\cdot q\cdot r$. מעודד מהצלחתו, מחליט חברנו לפתוח חברת סטארט-אפ כדי להכפיל שרשרת מטריצות. נניח שיש מערך תבנית:קוד בשורה שבו כל איבר הוא מטריצה. אז הסטארט-אפ של חברנו יחזיר את תבנית:קוד בשורה. (נניח ש$n$ הוא אורך תבנית:קוד בשורה.)

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

תבנית:מבנה תבנית

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

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

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

תבנית:משפט

תבנית:הוכחה

הבעיה היחידה היא שאיננו יודעים את $k$, אבל קל לבדוק מהו ה$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(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

תבנית:הארה

אז מה רע?

הפתרון איטי.

תבנית:הוכחה

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

תבנית:מבנה תבנית

תזכור (Memoization)

בנקודה זו אנו יודעים שתבנית:קוד בשורה נקרא שוב ושוב עם אותם הארגומנטים. מדוע שלא נשמור פשוט את התוצאה של כל קריאה בפעם הראשונה שחישבנו אותה עבור ארגומנט כלשהו? נעשה זאת כך. ראשית, נגדיר מטריצה גלובאלית תבנית:קוד בשורה, ונאתחל אותה ל$n^2$ ערכי תבנית:קוד בשורה:

# 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

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

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

נראה כעת האם שיפרנו בכך את הסיבוכיות. בדומה לצורה שעפי"ה ניתחנו את דג הסלמון, נגדיר את $T^{\prime }(i,j)$ כזמן שאורכת תבנית:קוד בשורה בהנחה שכ"א מהקריאות לתבנית:קוד בשורה ותבנית:קוד בשורה היא $O(1)$. ונחשוב מדוע המשפט הבא נכון. תבנית:משפט

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

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

הדפסת הסדר

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

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-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) )

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס