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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

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

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

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

שקול לדלג על נושא זה

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

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

כדאי לדעת:

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

תוכן עניינים

1 הבעיה
- 1.1 הכפלת מטריצות
- 1.2 הכפלת שרשרת מטריצות
2 הרקורסיה הפשוטה
3 אז מה רע?
4 תזכור (Memoization)
5 הדפסת הסדר

[עריכה] הבעיה

[עריכה] הכפלת מטריצות

בתכנות, מטריצה היא מערך של מערכים. להלן דוגמה לקטע קוד שמייצר מטריצה בעלת 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 matrixes (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$ . מעודד מהצלחתו, מחליט חברנו לפתוח חברת סטארט-אפ כדי להכפיל שרשרת מטריצות. נניח שיש מערך Matrixes שבו כל איבר הוא מטריצה. אז הסטארט-אפ של חברנו יחזיר את Matrixes[1] * Matrixes[2] * ... * Matrixes[n]. (נניח ש $\displaystyle n$ הוא אורך Matrixes.)

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

דוגמה:

נניח שיש לנו שרשרת המטריצות $\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$ .

כפי שמראה הדוגמה, הסדר בו מכפילים את המטריצות יכול להשפיע על הזמן הכולל בצורה מכריעה. לחברנו אין מושג קלוש באיזה סדר להכפיל, ועל כן הוא מבקש מאיתנו לפתור את הבעיה. נניח שברשותינו מערך גלובאלי Matrixes של $\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 \le k < j} ( m(i, k) + m(k + 1, j) + pqr(i, k, j) )$ , כאשר

$\displaystyle pqr(i, k, j)$ = Num-Rows(Matrixes[i]) * Num-Rows(Matrixes[k + 1]) * Num-Cols(Matrixes[j]).

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

אם $\displaystyle i < j$ , אז בהכרח מכפילים מ $\displaystyle i$ ל $\displaystyle k$ כלשהו, מ $\displaystyle k + 1$ ל $\displaystyle j$ , ולבסוף את שתי התוצאות. בלי קשר לדרך בה מכפילים מ $\displaystyle i$ ל $\displaystyle k$ , מקבלים מטריצה בעלת מימדים (Num-Rows(Matrixes[i]), Num-Cols(Matrixes[k])). באותו אופן, בלי קשר לדרך בה מכפילים מ $\displaystyle k + 1$ ל $\displaystyle j$ , מקבלים מטריצה בעלת מימדים (Num-Rows(Matrixes[k + 1]), Num-Cols(Matrixes[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(Matrixes[i])
2	q = Num-Rows(Matrixes[k + 1])
3	r = Num-Cols(Matrixes[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(Matrixes) )
 
2	Print(m)
 
3	Print-Orders( 1, Length(Matrixes) )

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

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

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

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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

[עריכה] הבעיה

[עריכה] הכפלת מטריצות

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

[עריכה] הרקורסיה הפשוטה

[עריכה] אז מה רע?

[עריכה] תזכור (Memoization)

[עריכה] הדפסת הסדר

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא