9.4 כפל שרשרת מטריצות
מבנה
נתונים ואלגוריתמים
נתון רצף של
מטריצות אותן יש להכפיל:
A1
A2 A3 ... An
הכפלת מטריצות הינה אסוציאטיבית ולכן:
A1 ( A2 A3 ) = ( A1 A2 ) A3
ניתן לעשות זאת בשתי דרכים.
העלות של הכפלת nxm ב- mxp היא O(nmp) (או O(n3) עבור שתי מטריצות nxn).
בחירה אומללה
של סדר הסוגריים עלולה להיות יקרה.
לדוגמא, אם
נתון:
|
Matrix |
Rows |
Columns |
|
A1 |
10 |
100 |
|
A2 |
100 |
5 |
|
A3 |
5 |
50 |
העלות עבור ( A1 A2)
A3 היא:
|
A1A2 |
10x100x5 |
= 5000 |
=> A1 A2 (10x5) |
|
(A1A2) A3 |
10x5x50 |
= 2500 |
=> A1A2A3 (10x50) |
|
|
|
7500 |
סך הכל |
|
|
|
|
|
אך עבור A1 ( A2 A3 ):
|
A2A3 |
100x5x50 |
= 25000 |
=> A2A3 (100x5) |
|
A1(A2A3) |
10x100x50 |
= 50000 |
=> A1A2A3 (10x50) |
|
|
|
75000 |
סך הכל |
זוהי הדגמה ברורה של הרווח המתקבל ממציאת הסדר האופטימלי לפני התחלת החישוב!
כמו עם עץ החיפוש הבינארי האופטימלי, גם כאן ניתן להבחין כי אם נחלק את שרשרת המטריצות
לשתי
תתי-שרשראות בעלות סדר הכפלה אופטימלי:
(A1 A2 A3 ... Aj) (Aj+1
... An )
אזי סדר
הסוגריים של תתי-השרשראות הוא האופטימלי, שכן אם זה לא כך, הרי שניתן להחליפו בסדר
סוגריים בעל עלות זולה יותר.
תכונה זו,
ידועה כ-תת-מבנה אופטימלי, והיא מאפיין של אלגוריתם דינאמי. היא מאפשרת
לפתור בעיות קטנות (תת-מבנה) ולהשתמש בפתרונות אלו על מנת להגיע לפתרונות של בעיות
גדולות יותר.
במקרה של הכפלת
שרשרת מטריצות, ההליך כמעט זהה להליך שמשמש לבניית עץ חיפוש
בינארי
אופטימלי. נבחן שתי מטריצות:
·
מטריצה אחת
המכילה את העלויות של הכפלת כל תתי-השרשראות. האלכסון שמתחת לאלכסון הראשי מכיל את
העלויות של הכפלות כל צירופי הזוגות: cost[1,2] המכיל את העלות של ההגעה לתוצר A1A2 וכד'. האלכסון שמתחת לאלכסון הראשי מכיל את
העלויות של תוצרים משולשים: כגון: cost[1,3] המכיל את העלות של תוצר ההכפלה של A1A2A3, שהתקבל על ידי השוואת cost[1,2] ו- cost[2,3], וכד'.
·
מטריצה שניה המכילה את
האינדקס של המערך האחרון בסוגריים השמאליים (בדומה לשורש של תת-העץ האופטימלי בעץ
חיפוש בינארי אופטימלי, אך כאן אין שורש אלא השרשרת מחולקת לתתי-תוצרים שמאליים
וימניים), כך ש-best[1,3] עשוי להכיל 2 כדי לסמן
שתת-השרשרת השמאלית מכילה A1A2
ושהימנית מכילהA3 בסדר
הסוגריים האופטימלי של A1A2A3.
כמו קודם, אם צריך להכפיל n מטריצות, הדבר ידרוש זמן של O(n) כדי ליצור כל אחת מ- O(n2) מהעלויות והכניסות במטריצת ה- best,
כך
שתתקבל סיבוכיות כוללת של O(n3) בעלות שטח זיכרון O(n2).
תת-מבנה
אופטימלי
תכונה של בעיות אופטימיזציה שלפיה תתי-בעיות המרכיבות
פתרון לבעיה הכוללת, הן בעצמן פתרונות אופטימליים לתתי-הבעיות. תכונה זו מאפשרת
יצירת אלגוריתמים דינאמיים לפתרון הבעיה הכוללת.