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

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

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

קפיצה אל: ניווט, חיפוש

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

אלגוריתמים
מבני נתונים
גרפים
- גרפים וייצוגיהם
- עצים
- אלגוריתם Union-Find
- אלגוריתמים למציאת עפ"מ
- אלגוריתם Kruskal
- אלגוריתם Prim
- חיפוש רוחבי
- אלגוריתם Dijkstra
- מסלולים זולים לכלל הזוגות
- אלגוריתם "הכפלת מטריצות"
- אלגוריתם Floyd-Warshall
- זרימה - הגדרות
- זרימה שיורית וחתכים
- אלגוריתמי זרימה
נספחים
- מתמטיקה
- חשיבה רקורסיבית

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

כדאי לדעת:

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

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

[עריכה] הרעיון הכללי

שימו לב:

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

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

הגדרה:

נגדיר כ $\displaystyle d^{(m)}(u, v)$ את מחיר המסלול הזול ביותר מ $\displaystyle u$ ל $\displaystyle v$ שארכו בדיוק $\displaystyle m$ .

מעניין לראות שבגרף ה"מוסף", אפשר להרחיב את משמעות ההגדרה. המשפט הבא מפרט זאת.

משפט:

בגרף ה"מוסף", $\displaystyle d^{(m)}(u, v)$ שווה בדיוק למחיר המסלול הזול ביותר מ $\displaystyle u$ ל $\displaystyle v$ שארכו לכל היותר $\displaystyle m$ .

לפני שנוכיח את המשפט, להלן דוגמה.

דוגמה:

להלן הגרף המקורי לבעיה:

(נזכר שהגרף ה"מוסף" נוצר על ידי הוספת קשתות במחירים 0 ואינסוף.)

בגרף המקורי:
- המסלול הזול ביותר מ $\displaystyle 1$ ל $\displaystyle 2$ הוא $\displaystyle 1 \rightarrow 4 \rightarrow 2$ , ועלותו 2.
- אין מסלול מ $\displaystyle 1$ ל $\displaystyle 2$ באורך 4.
בגרף ה"מוסף":
- המסלול הזול ביותר מ $\displaystyle 1$ ל $\displaystyle 2$ גם הוא $\displaystyle 1 \rightarrow 4 \rightarrow 2$ , ועלותו 2.
- המסלול הזול ביותר (אך לא היחידי) מ $\displaystyle 1$ ל $\displaystyle 2$ באורך 4 הוא $\displaystyle 1 \rightarrow 4 \rightarrow 2 \rightarrow 2 \rightarrow 2$ , ועלותו 2.

כעת נוכיח את המשפט.

הוכחה: נניח בשלילה ש $\displaystyle P$ , המסלול הזול ביותר מ $\displaystyle u$ ל $\displaystyle v$ הוא בעל אורך $\displaystyle m'$ הקטן (ממש) מ $\displaystyle m$ . אם זה המצב, נוכל לבנות מסלול בדיוק באותו מחיר, שארכו בדיוק $\displaystyle m$ ; המסלול מורכב משני חלקים: החלק הראשון הוא $\displaystyle P$ , שארכו $\displaystyle m'$ , והחלק השני מורכב מ $\displaystyle m - m'$ "סיבובים" מהסוג $\displaystyle v \rightarrow v$ , שעלותם 0.

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

משפט:

נקבע את $\displaystyle n$ כמספר הצמתים בגרף. אז מחיר המסלול הזול ביותר מ $\displaystyle u$ ל $\displaystyle v$ הוא $\displaystyle d^{(n - 1)}(u, v)$ .

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

משפט:

לכל $\displaystyle m$ ,‏ $\displaystyle d^{(m)}(u, v)$ הוא:

Edge-Costs[u][v], אם $\displaystyle m = 1$ .
$\displaystyle min_{w \in V}\{d^{(m - 1)}(u, w) +$ Edge-Costs[w][v] $\displaystyle \}$ , אם $\displaystyle m > 1$ .

הוכחה: אם $\displaystyle m = 1$ , אז מחיר המסלול הזול ביותר מ $\displaystyle u$ ל $\displaystyle v$ הוא בדיוק מחיר הקשת מ $\displaystyle u$ ל $\displaystyle v$ (נזכר שבגרף ה"מוסף" בהכרח יש קשת כזו).

אם $\displaystyle m > 1$ , אז המסלול הזול ביותר בהכרח מתחלק לשני חלקים:

חלק ראשון, מ $\displaystyle u$ ועד $\displaystyle w$ כלשהו, באורך $\displaystyle m - 1$ .
חלק שני, מ $\displaystyle w$ ל $\displaystyle v$ , באורך 1.

נשים לב גם שבהכרח משתמשים במסלול הזול ביותר מ $\displaystyle u$ ל $\displaystyle w$ באורך $\displaystyle m - 1$ - אם לא כן, היינו יכולים למצוא מסלול זול יותר.

היות שאיננו יודעים מיהו $\displaystyle w$ , לוקחים את המינימום על פני כל האפשרויות.

[עריכה] פסוודו-קוד

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

Matrix-Multiplication(G, Edge-Costs, m)
1      if m == 1
2              return Edge-Costs
 
3      D' = Matrix-Multiplication(G, Edge-Costs, m - 1)
 
4       n = Length( V(G) )
 
5       D = Make-Matrix(n, n)
 
6       for u in V(G)
7               for v in V(G)
8                       D[u][v] = ∞
 
9                       for w in V(G)
10                              if D[u][v] > D'[u][w] + Edge-Costs[w][v]
11                                     D[u][v] = D'[u][w] + Edge-Costs[w][v]
 
12      return D

ולהלן דוגמה לשימוש בו:

1  n = Length( V(G) )
 
2      D = Matrix-Multiplication(G, Edge-Costs, n - 1)
 
        # Prints 2.
3      Print( D[1][2] )
 
        # Prints ∞.
4      Print( D[2][1] )

בMatrix-Multiplication, שורות 1-2 מזהות את תנאי העצירה. כפי שהוכחנו מקודם, אם $\displaystyle m = 0$ אז המסלול הזול ביותר מ $\displaystyle u$ ל $\displaystyle v$ הוא בדיוק הכניסה ה $\displaystyle (u, v)$ במטריצה Edge-Costs; לכן אנו מחזירים מטריצה זו במקרה זה.

שורה 3 מחשבת את המסלולים הזולים ביותר עבור המקרה הקצר באחת (כלומר $\displaystyle m - 1$ ), ושומרת את התוצאה במטריצה זמנית D'. כעת 5-12 מייצרות את המטריצה עבור המרחק $\displaystyle m$ , וממלאות אותה. נשים לב שעבור כל $\displaystyle u$ ו $\displaystyle v$ (הלולאות ב6 ו7), עוברים על כל צומת ביניים $\displaystyle w$ אפשרי, בדיוק כפי שראינו ברעיון הכללי.

כדאי לדעת:

האלגוריתם נקרא "הכפלת מטריצות" כי 6-11 בMatrix-Multiplication נראות דומות לקוד של הכפלת מטריצות (במובן אלגברה ליניארית), ואפשר לחשוב על שני האלגוריתמים כמקרים פרטיים של רעיון אלגברי כללי יותר (לא נכנס לכך בקורס).

[עריכה] ניתוח סיבוכיות

ראשית, קל לראות כי 6-11 הן $\displaystyle \Theta(n^3)$ , וזאת עפ"י הדמיון לקוד להכפלת שתי מטריצות (במובן אלגברה לינארית). , קל גם לראות שהן למעשה קובעות את זמן הריצה של קריאה יחידה של הפונקציה. נגדיר כ $\displaystyle n$ את מספר צמתי הגרף, וכ $\displaystyle T(m)$ את זמן הריצה של Matrix-Multiplication(G, Edge-Costs, m). אז $\displaystyle T(m) = T(m - 1) + \Theta(n^3)$ , ולכן $\displaystyle T(n - 1) = \Theta(n^4)$ .

כדאי לדעת:

בספר הקורס ישנה גרסה שסיבוכיותה $\displaystyle \Theta(n^3 \cdot \log(n))$ , אלא שבאלגוריתם Floyd-Warshall נראה פתרון שעובד בזמן $\displaystyle \Theta(n^3)$ , ולכן זה אינו מעניין יותר מדי.

-

אלגוריתם "הכפלת מטריצות"

-

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

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

[עריכה] הרעיון הכללי

[עריכה] פסוודו-קוד

[עריכה] ניתוח סיבוכיות

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים