Matrix Chain Multiplication
שרשרת של מטריצות מתוארת באמצעות dims: למטריצה i יש dims[i] שורות ו-dims[i+1] עמודות, כך שכל מטריצה מתאימה לזו שאחריה. הכפלת מטריצת p × q במטריצת q × r דורשת p × q × r כפלות סקלריות ומפיקה מטריצת p × r. כל דרך להציב את הסוגריים נותנת את אותה מכפלה סופית, אך לא באותה עלות. החזר את המספר הקטן ביותר של כפלות סקלריות הדרושות להכפלת השרשרת כולה.
פונקציה
- dimsinteger-array
- הגדלים לאורך השרשרת: מטריצה i היא dims[i] × dims[i+1]
- מחזירהinteger
- מספר הכפלות הסקלריות הקטן ביותר הדרוש להכפלת כל השרשרת
אילוצים
2 ≤ dims.length ≤ 100, כך שהשרשרת מכילה בין 1 ל־99 מטריצות.1 ≤ dims[i] ≤ 100- התשובה היא לכל היותר 98 × 106, הרבה מתחת לגבול של מספר שלם signed בן 32 סיביות.
דוגמאות
- קלט
- dims = [4, 10, 3, 12]
- פלט
- 264
- הסבר
- הכפלת שני הגורמים הראשונים עולה 4 × 10 × 3 = 120 ומשאירה מטריצה בגודל 4 × 3, שכאשר מכפילים אותה במטריצה בגודל 3 × 12, מתווספת עלות של 144: בסך הכול 264. הסדר האחר עולה 360 + 480 = 840.
- קלט
- dims = [6, 2, 7, 3, 5]
- פלט
- 132
- הסבר
- נכפיל 2 × 7 ב־7 × 3 (42), את התוצאה של 2 × 3 ב־3 × 5 (30), ואז 6 × 2 בתוצאה של 2 × 5 (60): בסך הכול 132.
- קלט
- dims = [3, 7]
- פלט
- 0
- הסבר
- יש רק מטריצה אחת, 3 × 7, לכן לא מכפילים שום דבר והעלות היא 0.
שאלת המשך
האם תוכל גם לספור כמה סוגריים שונים משיגים את העלות המינימלית?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
עזוב את הכפל הראשון וחשוב על הכפל האחרון. לא משנה באיזה סדר תבחר, הצעד האחרון מכפיל את המכפלה של חלק שמאלי כלשהו בשרשרת במכפלת שאר החלקים.
מכפלת המטריצות שבין שני הגבולות
leftו-rightהיא תמיד מטריצה בגודלdims[left] × dims[right]. לכן, אם בשלב האחרון מחלקים את הקטע הזה בגבולsplit, העלות היאdims[left] × dims[split] × dims[right], ושני החלקים הם עותקים קטנים יותר של אותה בעיה.שמרו ב־
best[left][right]את הדרך הזולה ביותר להכפיל את המטריצות שבין הגבולותleftו־right(0 עבור מטריצה יחידה). זהו המינימום, מבין כל ערכיsplitשנמצאים строго ביניהם, שלbest[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]. חשבו מקטעים צרים לפני מקטעים רחבים.
פתרון
הסדר משנה את העלות: 264 לעומת 840 בדוגמה הראשונה. התבוננו בכפל האחרון. הוא מחבר את המכפלות של חלק שמאלי ושל חלק ימני בשרשרת, וכל חלק הוא אותה בעיה בשרשרת קצרה יותר. טבלה על פני המקטעים של השרשרת פותרת כל אחת מהן פעם אחת, בזמן O(n³).
נסו כל חלוקה באמצעות רקורסיה פשוטה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
מספרים את הגבולות של השרשרת מ־0 עד m-1, כאשר m = dims.length: לגבול k יש גודל dims[k]. הכפלת המטריצות שבין הגבולות left ו־right נותנת מטריצה בגודל dims[left] × dims[right], בכל סדר שבו מכפילים אותן. לכן, אם השלב האחרון מפצל את הקטע הזה בנקודה split, העלות שלו היא dims[left] × dims[split] × dims[right], בלי קשר למה שקרה בתוך שני הבלוקים. יש לבנות כל בלוק בעלות הנמוכה ביותר האפשרית, ולכן cheapest(left, right) היא הסכום הקטן ביותר של עלויות שני הבלוקים בתוספת השלב האחרון, מבין כל האפשרויות של split. הניסיון של כל האפשרויות לשלב האחרון מבטיח שהפתרון נכון.
האלגוריתם פותר שוב ושוב את אותם קטעים: עבור n מטריצות הוא מבצע 3^(n-1) קריאות, כלומר בערך 1.2 × 10^9 עבור 20 מטריצות, בעוד שיש רק כ־m²/2 קטעים שונים.
אלגוריתם
- כתבו את
cheapest(left, right)עבור המטריצות שבין הגבולותleftו־right. - אם
right - left < 2, יש מטריצה אחת: החזירו 0. - עבור כל
splitשנמצא ביניהם, בלי לכלול אותם, חברו אתcheapest(left, split), אתcheapest(split, right)ואתdims[left] × dims[split] × dims[right]. - החזירו את הסכום הקטן ביותר.
- התשובה היא
cheapest(0, m-1).
def matrixChainOrder(dims):
def cheapest(left, right):
# The fewest multiplications for the matrices between boundaries left and right
if right - left < 2:
return 0 # a single matrix costs nothing
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
return best
return cheapest(0, len(dims) - 1)רקורסיה עם זיכרון מטמון
האינטואיציה
קריאה תלויה רק ב־left וב־right. שמור את התוצאה שלה ב־memo[left][right], כשכל תא מתחיל ב־-1, ערך ששום עלות ממשית לא יכולה לקבל, ובקריאות מאוחרות יותר קרא את התא במקום לבצע רקורסיה. כל אחד מכ־m²/2 הזוגות נפתר פעם אחת עם פחות מ־m פיצולים: O(n³), או 161,700 בדיקות פיצול עבור 99 מטריצות. עומק הרקורסיה לעולם אינו גדול מאורך השרשרת, לכן 100 גבולות נכנסים לכל מחסנית קריאות.
אלגוריתם
- אתחל את
memoעםmשורות ו-mעמודות, ואתחל כל תא ל-1. - ב-
cheapest(left, right), טווח של מטריצה אחת מחזיר 0, ותא שאינו 1 מחזיר את העלות השמורה שלו. - אחרת, חשב את המחיר של כל
splitבדיוק כמו ברקורסיה הרגילה וקח את המינימום. - כתוב את המינימום הזה לתוך
memo[left][right]לפני החזרתו. - התשובה היא
cheapest(0, m-1).
def matrixChainOrder(dims):
m = len(dims)
# memo[left][right]: the answer for boundaries left and right, -1 while unknown
memo = [[-1] * m for _ in range(m)]
def cheapest(left, right):
if right - left < 2:
return 0 # a single matrix costs nothing
if memo[left][right] != -1:
return memo[left][right]
best = None
for split in range(left + 1, right):
cost = (cheapest(left, split) + cheapest(split, right)
+ dims[left] * dims[split] * dims[right])
if best is None or cost < best:
best = cost
memo[left][right] = best
return best
return cheapest(0, m - 1)מלאו את הטבלה על ידי מתיחת הרוחב
האינטואיציה
כל תא תלוי רק במקטעים צרים יותר, ולכן לולאות יכולות למלא את best[left][right] מצר לרחב. רוחב 1 הוא מטריצה יחידה ונשאר 0; כשמגיעים למקטע רחב יותר, שני החלקים של כל פיצול כבר חושבו. עם dims = [6, 2, 7, 3, 5]:
- רוחב 2:
best[0][2] = 84,best[1][3] = 42,best[2][4] = 105. - רוחב 3: הערך של
best[0][3]הוא 78 (פיצול 1: 0 + 42 + 36), והערך שלbest[1][4]הוא 72 (פיצול 3: 42 + 0 + 30). - רוחב 4: הפיצולים 1, 2 ו־3 נותנים 0 + 72 + 60 = 132, 84 + 105 + 210 = 399 ו־78 + 0 + 90 = 168, ולכן
best[0][4] = 132.
הפיצול העליון בגבול 1 פירושו שמכפילים את המטריצה 6 × 2 אחרונה, כמו בדוגמה השנייה. זמן הריצה והזיכרון תואמים לגרסת הממואיזציה, ללא רקורסיה.
אלגוריתם
- נסמן
m = dims.lengthונקצה טבלה בגודלm × mבשםbest, שמכילה אפסים. - נעבור על
widthמ־2 עדm-1. בתוך הלולאה, נעלה אתleftהחל מ־0 כל עודright = left + widthעדיין נמצא בגבולות. - עבור המקטע הזה, נחשב את
best[left][split] + best[split][right] + dims[left] × dims[split] × dims[right]עבור כלsplitמ־left+1עדright-1, ונשמור את הערך המינימלי ב־best[left][right]. - התשובה נמצאת ב־
best[0][m-1].
def matrixChainOrder(dims):
m = len(dims)
# best[left][right]: the fewest multiplications for the matrices
# between boundary left and boundary right (0 for a single matrix)
best = [[0] * m for _ in range(m)]
for width in range(2, m):
for left in range(m - width):
right = left + width
low = None
for split in range(left + 1, right):
# the last product joins a dims[left] x dims[split] block
# with a dims[split] x dims[right] block
cost = best[left][split] + best[split][right] + dims[left] * dims[split] * dims[right]
if low is None or cost < low:
low = cost
best[left][right] = low
return best[0][m - 1]
מלכודות ומקרי קצה
- כפל הזוג הזול ביותר תחילה. עבור
[10, 10, 1, 9]הזוג האחרון הוא הזול ביותר (90), אבל השלב שאחריו עולה 900, ובסך הכול 990. כפל הזוג הראשון תחילה עולה 190. - קריאת התשובה מהתא הלא נכון. ב-
dimsיש ערך אחד יותר ממספר המטריצות, לכן התשובה היאbest[0][m-1], ולאbest[0][m]. - הגדלת
leftבלולאה החיצונית. אז שורהleftקוראת אתbest[split][right]משורה מאוחרת יותר שערכה עדיין 0. הציבו את הרוחב בלולאה החיצונית, או ספרו אתleftלאחור. - אי-טיפול במטריצה יחידה.
[3, 7]חייב להחזיר 0, וב-R הלולאה2:(m-1)הופכת ל-2:1ורצה לאחור, לכן הוסיפו תנאי הגנה.
שאלות נפוצות3
מהי סיבוכיות הזמן של כפל שרשראות מטריצות?
בטבלה יש בערך n²/2 רצפים, וכל אחד מנסה עד n חלוקות, ולכן תכנות דינמי פועל בזמן O(n³) ובזיכרון של O(n²). רקורסיה רגילה ללא זיכרון מטמון מבצעת 3^(n-1) קריאות עבור n מטריצות.
למה הסדר של כפל מטריצות חשוב?
כפל מטריצות הוא אסוציאטיבי, ולכן (AB)C ו־A(BC) נותנים את אותה מטריצה, אבל המטריצות הביניים שונות בגודלן. בדוגמה הראשונה, (AB)C בונה מטריצה בגודל 4 × 3 ועולה 264, ואילו A(BC) בונה מטריצה בגודל 10 × 12 ועולה 840.
איך מוצאים את סוגרור האופטימלי עצמו?
שמור את הפיצול המנצח ב־choice[left][right] לצד best[left][right]. כדי להדפיס, מטריצה יחידה מדפיסה את שמה; קטע ארוך יותר מדפיס סוגריים פותחים, את החלק עד choice[left][right], את החלק שאחריו וסוגריים סוגרים. הדבר מוסיף זיכרון של O(n²).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def matrixChainOrder(dims):
# כתבו כאן קודבדיקה #1
בדיקה #2
בדיקה #3
ארגומנט
dims = [4, 10, 3, 12]
הפלט הצפוי
264