מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי - הכפלת שרשרת מטריצות
שקלו לדלג על נושא זה נושא זה מניח שאתה חש בנוח עם חשיבה רקורסיבית ותכנות רקורסיבי. אם זה אינו המצב, שקול לדלג לחשיבה רקורסיבית ולחזור לכאן מאוחר יותר. |
דף זה הוא השני משני דפים שעוסק ביישום רעיון התכנון הדינמי. אנו נתמקד ברעיון ה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
הוא , מספר השורות של R
הוא q
, ומספר העמודות של R
הוא r
. ראינו כבר שנתן לממש את Multiply
בזמן . חברנו, מהנדס אלקטרוניקה במקצועו, מימש את Multiply
בחומרה, כך שזמן ההכפלה הוא בדיוק . מעודד מהצלחתו, מחליט חברנו לפתוח חברת סטארט-אפ כדי להכפיל שרשרת מטריצות. נניח שיש מערך Matrices
שבו כל איבר הוא מטריצה. אז הסטארט-אפ של חברנו יחזיר את Matrices[1] * Matrices[2] * ... * Matrices[n]
. (נניח ש הוא אורך Matrices
.)
הבעיה היא שהכפלת שרשרת מטריצות מוגדרת היטב מבחינת האלגברה הלינארית, אולם לא מבחינה אלגוריתמית.
דוגמה: נניח שיש לנו שרשרת המטריצות .
אז:
|
כפי שמראה הדוגמה, הסדר בו מכפילים את המטריצות יכול להשפיע על הזמן הכולל בצורה מכריעה. לחברנו אין מושג קלוש באיזה סדר להכפיל, ועל כן הוא מבקש מאיתנו לפתור את הבעיה. נניח שברשותינו מערך גלובאלי Matrices
של מטריצות במימדים מתאימים להכפלה. עלינו להדפיס מה זמן ההכפלה הכולל הקצר ביותר, ואת סדר המכפלות שיביא לזמן זה.
שימו לב: מטרתנו אינה להכפיל את המטריצות (זו הבעיה של חבר שלנו - לא שלנו). המטרה שלנו היא רק למצא דברים לגבי סדר המכפלות האופטימאלי. |
הרקורסיה הפשוטה
עריכהנגדיר כ את הזמן המינימאלי הנדרש להכפלת תת-השרשרת מ (כולל) ל (כולל).
עכשיו תורכם: עפ"י הגדרה זו, הנו הזמן שאנו מחפשים. וודא שהנך מבין מדוע. |
משפט: מקיים את הנוסחה הבאה:
= |
הוכחה: המקרה ברור.
אם , אז בהכרח מכפילים מ ל כלשהו, מ ל , ולבסוף את שתי התוצאות. בלי קשר לדרך בה מכפילים מ ל , מקבלים מטריצה בעלת מימדים (Num-Rows(Matrices[i])
, Num-Cols(Matrices[k])
). באותו אופן, בלי קשר לדרך בה מכפילים מ ל , מקבלים מטריצה בעלת מימדים (Num-Rows(Matrices[k + 1])
, Num-Cols(Matrices[j])
).
מכפלת התוצאות, לכן, תעלה בדיוק . כדי לצמצם את סכום העלויות, לכן, יש להכפיל ביעילות רבה ככל האפשר מ ל , ומ ל - אבל עפ"י ההגדרה אלה בדיוק וm .
הבעיה היחידה היא שאיננו יודעים את , אבל קל לבדוק מהו ה המשתלם ביותר בעזרת לולאה:
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
כדאי לדעת: בבעיה זו, הפתרון האופטימאלי לבעיה בגודל כולל פתרון אופטימאלי לאותה בעיה, אך בגודל קטן יותר. על בעיות כאלה אומרים שיש להן optimal substructure. |
אז מה רע?
עריכההפתרון איטי.
משפט: קל לראות שזמן הריצה של |
הוכחה: זמן הריצה של Min-Time(n)
נתון ע"י נוסחת הנסיגה . אפשר להמשיך מכאן באינדוקציה.
קצת מפתיע שהפתרון כ"כ איטי, מפני שאם מתבוננים בקוד של Min-Time
, אפשר לראות
שהוא מבצע מספר לינארי של פעולות (חוץ מקריאות רקורסיביות). יותר מכך, Min-Time
יכול להקרא רק עם ארגומנטים שונים. נראה שמספר הפעמים שהוא נקרא - הוא זה
שגבוה כ"כ.
במחשבה נוספת, נתן לראות שMin-Time
נקרא שוב ושוב עם אותם הארגומנטים.
דוגמה: אם , אז:
|
כדאי לדעת: אפשר לראות שMin-Time(1, 3) נקרא הן מתוך Min-Time(1, 4) והן מתוך Min-Time(1, 98) . אומרים על כך שיש overlapping subproblems.
|
תזכור (Memoization)
עריכהבנקודה זו אנו יודעים שMin-Time
נקרא שוב ושוב עם אותם הארגומנטים. מדוע שלא נשמור פשוט את התוצאה של כל קריאה בפעם הראשונה שחישבנו אותה עבור ארגומנט כלשהו? נעשה זאת כך. ראשית, נגדיר מטריצה גלובאלית M
, ונאתחל אותה ל ערכי 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
נראה כעת האם שיפרנו בכך את הסיבוכיות. בדומה לצורה שעפי"ה ניתחנו את דג הסלמון, נגדיר את כזמן שאורכת Min-Time(i, j)
בהנחה שכ"א מהקריאות לMin-Time(i, k)
וMin-Time(k + 1, 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-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) )
הפרק הקודם: תכנון דינאמי - דג הסלמון |
תכנון דינאמי - הכפלת שרשרת מטריצות | הפרק הבא: מבני נתונים |