מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 10/תשובות
1
[עריכה]1
[עריכה]ראשית נשנה מעט את אלגוריתם Prim:
MST-Prim(G, Edge-Costs)
1 pq = Make-Priority-Queue()
2 Min-Costs = Make-Array(Length(V(G)))
3 Used = Make-Array(Length(V(G)))
4 s = V[1]
5 for u in V(G)
6 Min-Costs[u] = u == s? 0 : ∞
7 Used[u] = False
8 Insert(pq, u)
9 V' = Make-List()
10 while Size(pq) > 0
11 u = Delete(pq)
12 Used[u] = True
13 Insert(V', u)
14 total-cost = total-cost + Min-Costs[u]
15 for v in A(G, u)
16 if Min-Costs[v] > Edge-Costs[ (u, v) ] and Used[v] == False
17 Min-Costs[v] = Edge-Costs[ (u, v) ]
18 Decrease-Key(pq, v)
השינויים היחידים הם ב9 וב13: אנו מחזיקים רשימה מקושרת V'
המכילה את קבוצת הצמתים שצירפנו לעץ הפורש שאליו שייך s
. בכל שלב נצרף את הצומת מחוץ לV'
שהוא הזול ביותר להוספה (כלומר שהוא מחובר בקשת הזולה ביותר המחברת בין צומת בV'
לצומת מחוץ לV'
).
כשמתבוננים בקוד ומבינים אותו כך, קל לראות שהאלגוריתם למעשה מממש את "אלגוריתם" Grow MST. קל להראות זאת פורמלית באינדוקציה - ההוכחה דומה מאד לאלגוריתם Kruskal.
2
[עריכה]שוב נשנה מעט את אלגוריתם Prim:
# Takes a connected undirected graph (G) and a cost table (W)
# Returns a set of edges E' such that (V(G), E') is
# a MST (minimum spanning tree).
MST-Prim(G, Edge-Costs)
1 pq = Make-Priority-Queue()
2 Min-Costs = Make-Array(Length(V(G)))
3 Neighbor = Make-Array(Length(V(G)))
4 Used = Make-Array(Length(V(G)))
5 s = V[1]
6 for u in V(G)
7 Min-Costs[u] = u == s? 0 : ∞
8 Neighbor[u] = u == s? 0 : ∞
9 Used[u] = False
10 Insert(pq, u)
11 E' = Make-List()
12 while Size(pq) > 0
13 u = Delete(pq)
14 Used[u] = True
15 if Neighbor[u] != ∞
16 Insert(E', (Neighbor[u], u) )
17 total-cost = total-cost + Min-Costs[u]
18 for v in A(G, u)
19 if Min-Costs[v] > Edge-Costs[ (u, v) ] and Used[v] == False
20 Min-Costs[v] = Edge-Costs[ (u, v) ]
21 Neighbor[v] = u
22 Decrease-Key(pq, v)
23 return E'
ההסבר וההוכחה כמעט זהים לאלה שבסעיף הקודם.
2
[עריכה]נבנה גרף חדש ברשימת שכנויות.
נגדיר את הגרף החדש מתוך כלהלן. ראשית, אם , אז נקבע . כעת נעבור על כל . אם מחיר קשת הוא 1, נוסיף קשת זו ל.
לחלופין, נניח שמחיר הקשת הוא . במקרה זה נוסיף עוד צמתים חדשים ל ועוד קשתות ל, כך שיש מסלול באורך מ ל של קשתות במחיר 1 ב. נקבל ב גרף בעל מסלולים במחיר 1 בלבד.
דוגמה: בתרשים הבא, הגרף העליון הוא , הגרף המקורי. הגרף התחתון הוא הגרף החדש (הצמתים המקוריים מ מסומנים בהדגשה). |
המשפט הבא טריביאלי:
משפט: לכל , מחיר המסלול הזול מ ל ב הוא מרחק המסלול הקצר מ ל ב. |
קל גם להווכח שסיבוכיות בניית היא .
כעת נריץ את אלגוריתם [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] על . הסיבוכיות הכוללת (של הבניה ושל ההרצה) במקרה הגרוע היא .
3
[עריכה]ראשית נכתוב פונקציה דומה למה שהתבקשנו לעשות, Dijkstra'
. פונקציה זו תחזיר זוג
מערכים:
- המערך הראשון הוא
Min-Costs
, שממפה כל צומתu
לעלות המסלול הזול ביותר מs
לu
. - המערך הראשון הוא
Parents
, שממפה כל צומתu
לצומת הקודם במסלול הזול ביותר מs
לu
.להלן הפסוודו-קוד המתאים (השינויים מודגשים כך):
Dijkstra'(G, s)
1 pq = Make-Priority-Queue()
2 '''Parents = Make-Array( Length(V(G)) )'''
3 Min-Costs = Make-Array( Length(V(G)) )
4 for u in V(G)
5 Min-Costs[u] = u == s? 0 : ∞
6 '''Parents[u] = Nil'''
7 Insert(pq, u)
8 while Size(pq) > 0
9 u = Delete(pq)
10 for v in A(g, u)
11 if Min-Costs[v] > Min-Costs[u] + Edge-Costs[ (u, v) ]
12 Min-Costs[v] = Min-Costs[u] + Edge-Costs[ (u, v) ]
13 '''Parents[v] = u'''
14 Decrease-Key(pq, v)
15 return '''(Min-Dists, Parents)'''
התוספות פשוטות למדי. מייצרים מערך Parents
, בו כל צומת שומר את "אביו" במסלול מs
אליו. בכל פעם שצומת מעדכן את שכניו, מעדכנים שהוא אביהם של הצמתים המעודכנים.
נכתוב גם פונקציה Parents-To-Paths
ההופכת את מערך האבות Parents
למערך מסלולים.
Parents-To-Path(s, v, Parents)
1 stk = Make-Stack()
2 while Parents[v] != Nil
3 u = Parents[v]
4 Push(stk, (u, v))
5 v = u
6 Path = Make-Array( Size(stk) )
7 i = 1
8 while Size(stk) > 0
9 Path[i++] = Pop(stk)
10 return Path
הפונקציה מקבלת את צומת המוצא s
, צומת כלשהו v
, והמערך Parents
; היא מחזירה מערך המתאר הת המסלול מs
לv
. 1-6 "מטיילות" אחורה על מסלול האבות, ומכניסות קשתות למחסנית. 7-11 ממירות את המחסנית למערך, ומחזירות את המערך.
כעת, בעזרת Dijkstra'
וParents-To-Paths
, נוכל לכתוב את הפונקציה המבוקשת:
Dijkstra(G, s)
1 (Min-Costs, Parents) = Dijkstra'(G, s)
2 Min-Paths = Make-Array( Length(V(G)) )
3 for v in V(G)
4 Min-Paths[u] = Parents-To-Paths(s, v, Parents)
5 return (Min-Costs, Min-Paths)
כעת ננתח את הסיבוכיות:
- מהתבוננות ב
Dijkstra'
, קל לראות שהסיבוכיות שלה הנה זו של אלגוריתם Dijkstra. Parents-To-Paths
היא .הסיבוכיות הכוללת, לכן, היא .
4
[עריכה]נבנה גרף חדש כך.
ראשית, נקח את צמתי הגרף , ונשכפל אותם 3 פעמים, בקבוצות , , ו. לכל צומת בקבוצה , יש צומת ב, וצומת ב. התרשים הבא מראה זאת.
כעת נוסיף גם קשתות:
- כל קשת אדומה בין ל (בגרף המקורי) - נמתח אותה בגרף החדש בין ב לבין הצומת המתאים ל ב.
- כל קשת שחורה בין ל (בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל ב לבין הצומת המתאים ל ב.
התרשים הבא מראה זאת.
בנוסף נמתח עוד שני סוגי קשתות:
- לכל צומת ב, נמתח קשת במחיר 1 בין ב לבין ב.
- לכל צומת ב, נמתח קשת במחיר 1 בין ב לבין ב.(לא נצייר קשתות אלו מטעמי נוחות.)
נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא .
המשפט הבא מסביר את חשיבות הגרף החדש.
משפט: מחיר המסלול הקביל הזול ביותר מ ל בגרף המקורי, קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ ל ב בגרף החדש. |
הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ ל ב בגרף החדש, מורכב משני חלקים:
- מסלול זהה לחלוטין למסלול קביל מ ל בגרף המקורי
- מסלול בעלות 1 ל ב
לכן, כל שנותר הוא להריץ את אלגוריתם Dijkstra.
קל לראות שהסיבוכיות הכוללת היא זו של אלגוריתם Dijkstra.
5
[עריכה]1
[עריכה]נניח שיש מעגל סופי מ כלשהו חזרה אליו, ועלות מעגל זה היא . אז אין שום מסלול סופי מ ל שהוא הזול ביותר, כי הספת מעגל זה תוזיל אותו ב.
2
[עריכה]אלגוריתם "הכפלת מטריצות"
[עריכה]באלגוריתם "הכפלת מטריצות", טענו את המשפט הבא:
משפט: נקבע את כמספר הצמתים בגרף. אז מחיר המסלול הזול ביותר מ ל הוא . |
הרעיון מאחורי המשפט היה שהמסלול הזול ביותר מ ל בהכרח קצר מ: אם לא, אז יש צומת אחד (לפחות) שרואים אותו פעמיים. אמנם נכון שאם מחירי הקשתות לא-שליליים (כפי שהיה שם), קל לראות שאפשר להתעלם מאפשרות זו כמסלול הזול ביותר; כאן, לעומת זאת, דווקא נוכחנו שייתכן שנרצה לפגוש אותו צומת פעמיים (ֹויותר).
אלגוריתם Floyd-Warshall
[עריכה]באלגוריתם Floyd-Warshall, טענו את המשפט הבא:
משפט: הוא:
|
קל לראות שחלקו השני של המשפט לא נכון. בזמנו טענו שאם מ ל עוברים דרך , אז מ
ל ומ ל אין צורך
לעבור דרך . כעת דווקא ראינו שמעגל כזה מ
ל דווקא עלול להוזיל את המסלול.
3
[עריכה]אלגוריתם "הכפלת מטריצות"
[עריכה]פשוט יש לחזור על הרעיון הכללי, ולראות שלא השתנה כלום.
נתחיל במשפט שראינו שהשתבש בסעיף הקודם:
משפט: נקבע את כמספר הצמתים בגרף. אז מחיר המסלול הזול ביותר מ ל הוא . |
משפט זה שוב נכון. כל מסלול באורך (או יותר) פוגש לפחות צומת אחד פעמיים. אם אין מעגל שלילי, מסלול כזה בהכרח אינו זול יותר ממסלול אחר ללא המעגל.
כעת נתבונן במשפט הבא:
משפט: לכל , הוא:
|
בהוכחת משפט זה לא הנחנו כלום לגבי סימן מחיר הקשתות. מחיר המסלול הזול ביותר באורך 1 הוא, עפ"י ההגדרה, מחיר הקשת בין שני צמתים. המסלול הזול ביותר באורך מורכב, עפ"ׁ ההגדרה, ממסלול באורך ועוד קשת.
אלגוריתם Floyd-Warshall
[עריכה]פשוט יש לחזור על [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]], ולראות שלא השתנה כלום. נתחיל במשפט הבא:
משפט: נקבע את כמספר הצמתים בגרף. אז מחיר המסלול הזול ביותר מ ל הוא בדיוק . |
משפט זה בוודאי נכון - המסלול הזול ביותר מ ל הוא
הזול ביותר מבין המסלולים שמותר להם לעבור דרך כל צומת בגרף.
נמשיך במשפט שהשתבש מקודם:
משפט: הוא:
|
חלקו הראשון של המשפט נכון לפי ההגדרה.
אם אין מעגלים שליליים, גם חלקו השני נכון. אם מ ל עוברים דרך , אז אין טעמם לבדוק מסלולים שבהם מ ל או מ ל עוברים דרך . מסלולים אלה כוללים מעגל כזה מ ל, ומסלול אחר ללא מעגל זה בהכרח אינו יקר יותר.
6
[עריכה]נניח שזהו הגרף המקורי:
נבנה גרף חדש כך.
ראשית, נקח את צמתי הגרף , ונשכפל אותם 3 פעמים, בקבוצות , , ו. לכל צומת בקבוצה , יש צומת ב, וצומת ב. התרשים הבא מראה זאת.
כעת נוסיף גם קשתות:
- כל קשת בין ל (בגרף המקורי) - נמתח אותה בגרף החדש בין ב לבין הצומת המתאים ל ב.
- כל קשת בין ל (בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל ב לבין הצומת המתאים ל ב.
התרשים הבא מראה זאת (רק חלק מהקשתות מצויירות).
בנוסף נמתח עוד שני סוגי קשתות:
- לכל צומת ב, נמתח קשת במחיר בין ב לבין ב.
- לכל צומת ב, נמתח קשת במחיר בין ב לבין ב.(לא נצייר קשתות אלו מטעמי נוחות.)
נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא .
המשפט הבא מסביר את חשיבות הגרף החדש.
משפט: מחיר המסלול הזול ביותר מ ל בגרף המקורי (כולל הקנס, אם יש), קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ ל ב בגרף החדש. |
הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ ל ב בגרף החדש, מורכב משני חלקים:
- מסלול זהה לחלוטין למסלול מ ל בגרף המקורי
- מסלול בעלות 1 ל ב, אם החלק הראשון זוגי, ומסלול בעלות , אם החלק הראשון אי-זוגי.
לכן, כל שנותר הוא להריץ את אלגוריתם Dijkstra.
קל לראות שהסיבוכיות הכוללת היא זו של אלגוריתם Dijkstra.
7
[עריכה]שימו לב: אלגוריתם Dijkstra אינו פועל בצורה נכונה על גרפים בעלי קשתות שליליות (אפילו אם אין מעגל שלילי). לא למדנו אחרת, וקל לבנות דוגמה המראה זאת. |
נניח שזהו הגרף המקורי:
נבנה גרף חדש כך.
ראשית, נקח את צמתי הגרף , ונשכפל אותם 3 פעמים, בקבוצות , , ו. לכל צומת בקבוצה , יש צומת ב, וצומת ב. התרשים הבא מראה זאת.
כעת נוסיף גם קשתות:
- במקום כל קשת בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל ב לצומת המתאים ל ב.
- במקום כל קשת בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל ב לצומת המתאים ל ב.
- במקום הקשת השלילית (בגרף המקורי), נמתח קשת מהצומת המתאים ל ב לצומת המתאים ל ב במחיר 0. התרשים הבא מראה זאת.
נניח שלקשת השלילית היה מחיר . בנוסף נמתח עוד שני סוגי קשתות:
- לכל צומת ב, נמתח קשת במחיר בין ב לבין ב.
- לכל צומת ב, נמתח קשת במחיר 0 בין ב לבין ב.(לא נצייר קשתות אלו מטעמי נוחות.)
נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא .
המשפט הבא מסביר את חשיבות הגרף החדש.
משפט: מחיר המסלול הזול ביותר מ ל בגרף המקורי, קטן בדיוק ב ממחיר המסלול הזול ביותר מ ל ב בגרף החדש. |
הוכחה: בגרף המקורי, ייתכן שהמסלול הזול ביותר מ ל לא השתמש בקשת השלילילת, וייתכן שהשתשמש בו. במקרה הראשון, תהיה קפיצה מ ישירות ל, ובמקרה השני, תהיה קפיצה מ ל ומ ל. הקפיצה מ ישירות ל עולה יותר מאשר המסלול המקורי. הקפיצות מ ל ומ ל גם כן עולות יותר מאשר המסלול המקורי, שכן עלות כל אחת משתי הקשתות היא 0, והנוסע לא קיבל את התשלום מהחברה.
כעת כל הקשתות אינן שליליות, ומותר להריץ את Dijkstra.
קל לראות שהסיבוכיות הכוללת היא זו של Dijkstra.