מבני נתונים ואלגוריתמים - מחברת קורס/שיעורי בית 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

נבנה גרף חדש $\displaystyle G'=(V',E')$ ברשימת שכנויות.

נגדיר את הגרף החדש מתוך $\displaystyle G=(V,E)$ כלהלן. ראשית, אם $\displaystyle V=\{1,...,n\}$, אז נקבע $\displaystyle V'=\{1,...,n\}$. כעת נעבור על כל $\displaystyle e\in E$. אם מחיר קשת $\displaystyle e$ הוא 1, נוסיף קשת זו ל$\displaystyle E'$.

לחלופין, נניח שמחיר הקשת $\displaystyle e=(u,v)$ הוא $\displaystyle k>1$. במקרה זה נוסיף עוד $\displaystyle k-1$ צמתים חדשים ל$\displaystyle V'$ ועוד $\displaystyle k$ קשתות ל$\displaystyle E'$, כך שיש מסלול באורך $\displaystyle k$ מ$\displaystyle u$ ל$\displaystyle v$ של קשתות במחיר 1 ב$\displaystyle G'$. נקבל ב$\displaystyle G'$ גרף בעל מסלולים במחיר 1 בלבד.

דוגמה: בתרשים הבא, הגרף העליון הוא $\displaystyle G$, הגרף המקורי. הגרף התחתון הוא $\displaystyle G'$ הגרף החדש (הצמתים המקוריים מ$\displaystyle G$ מסומנים בהדגשה). הפיכת Dijkstra לBFS.

המשפט הבא טריביאלי:

משפט: לכל $\displaystyle u\in V$, מחיר המסלול הזול מ$\displaystyle s$ ל$\displaystyle u$ ב$\displaystyle G$ הוא מרחק המסלול הקצר מ$\displaystyle s$ ל$\displaystyle u$ ב$\displaystyle G'$.

קל גם להווכח שסיבוכיות בניית $\displaystyle G'$ היא $\displaystyle O(k\cdot (|V|+|E|))=O(|V|+|E|)$. כעת נריץ את אלגוריתם [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] על $\displaystyle G'$. הסיבוכיות הכוללת (של הבניה ושל ההרצה) במקרה הגרוע היא $\displaystyle \Theta (k\cdot (|V|+|E|))=\Theta (|V|+|E|)$.

3

ראשית נכתוב פונקציה דומה למה שהתבקשנו לעשות, Dijkstra'. פונקציה זו תחזיר זוג מערכים:

1. המערך הראשון הוא Min-Costs, שממפה כל צומת u לעלות המסלול הזול ביותר מs לu.
2. המערך הראשון הוא 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)

כעת ננתח את הסיבוכיות:

1. מהתבוננות בDijkstra', קל לראות שהסיבוכיות שלה הנה זו של אלגוריתם Dijkstra.
2. Parents-To-Paths היא $\displaystyle O(|E|)$.הסיבוכיות הכוללת, לכן, היא $\displaystyle O((|V|+|E|)\cdot \log(|V|)+|V|\cdot |E|))$.

4

נבנה גרף חדש כך.

ראשית, נקח את צמתי הגרף $\displaystyle V$, ונשכפל אותם 3 פעמים, בקבוצות $\displaystyle A$,‏ $\displaystyle B$, ו$\displaystyle C$. לכל צומת $\displaystyle u$ בקבוצה $\displaystyle A$, יש צומת $\displaystyle |V|+u$‏ ב$\displaystyle B$,‏ וצומת ‏ $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.‏ התרשים הבא מראה זאת.

שכפול הצמתים.

כעת נוסיף גם קשתות:

1. כל קשת אדומה בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין $\displaystyle u$ ב$\displaystyle A$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
2. כל קשת שחורה בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.

התרשים הבא מראה זאת.

הוספת הקשתות.

בנוסף נמתח עוד שני סוגי קשתות:

1. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר 1 בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר 1 בין $\displaystyle |V|+u$ ב$\displaystyle B$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא $\displaystyle \Theta (|V|+|E|)$.

המשפט הבא מסביר את חשיבות הגרף החדש.

משפט: מחיר המסלול הקביל הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי, קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש.

הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש, מורכב משני חלקים:

1. מסלול זהה לחלוטין למסלול קביל מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי
2. מסלול בעלות 1 ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$

לכן, כל שנותר הוא להריץ את אלגוריתם Dijkstra.

קל לראות שהסיבוכיות הכוללת היא זו של אלגוריתם Dijkstra.

5

1

נניח שיש מעגל סופי מ$\displaystyle u$ כלשהו חזרה אליו, ועלות מעגל זה היא $\displaystyle -p$. אז אין שום מסלול סופי מ$\displaystyle u$ ל$\displaystyle u$ שהוא הזול ביותר, כי הספת מעגל זה תוזיל אותו ב$\displaystyle p$.

2

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

באלגוריתם "הכפלת מטריצות", טענו את המשפט הבא:

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

הרעיון מאחורי המשפט היה שהמסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ בהכרח קצר מ$\displaystyle n$: אם לא, אז יש צומת אחד (לפחות) שרואים אותו פעמיים. אמנם נכון שאם מחירי הקשתות לא-שליליים (כפי שהיה שם), קל לראות שאפשר להתעלם מאפשרות זו כמסלול הזול ביותר; כאן, לעומת זאת, דווקא נוכחנו שייתכן שנרצה לפגוש אותו צומת פעמיים (ֹויותר).

אלגוריתם Floyd-Warshall

באלגוריתם Floyd-Warshall, טענו את המשפט הבא:

משפט: $\displaystyle d^{(m)}(u,v)$ הוא: Edge-Costs[u][v], אם $\displaystyle m=0$. $\displaystyle min\{d^{(m-1)}(u,v),d^{(m-1)}(u,m)+d^{(m-1)}(m,v)\}$, אם $\displaystyle m>1$.

קל לראות שחלקו השני של המשפט לא נכון. בזמנו טענו שאם מ $\displaystyle u$ ל$\displaystyle v$ עוברים דרך $\displaystyle m$, אז מ$\displaystyle u$ ל$\displaystyle m$ ומ$\displaystyle m$ ל$\displaystyle v$ אין צורך לעבור דרך $\displaystyle m$. כעת דווקא ראינו שמעגל כזה מ$\displaystyle m$ ל$\displaystyle m$ דווקא עלול להוזיל את המסלול.

3

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

פשוט יש לחזור על הרעיון הכללי, ולראות שלא השתנה כלום.

נתחיל במשפט שראינו שהשתבש בסעיף הקודם:

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

משפט זה שוב נכון. כל מסלול באורך $\displaystyle n$ (או יותר) פוגש לפחות צומת אחד פעמיים. אם אין מעגל שלילי, מסלול כזה בהכרח אינו זול יותר ממסלול אחר ללא המעגל.

כעת נתבונן במשפט הבא:

משפט: לכל $\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$.

בהוכחת משפט זה לא הנחנו כלום לגבי סימן מחיר הקשתות. מחיר המסלול הזול ביותר באורך 1 הוא, עפ"י ההגדרה, מחיר הקשת בין שני צמתים. המסלול הזול ביותר באורך $\displaystyle m$ מורכב, עפ"ׁ ההגדרה, ממסלול באורך $\displaystyle m-1$ ועוד קשת.

אלגוריתם Floyd-Warshall

פשוט יש לחזור על [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]], ולראות שלא השתנה כלום. נתחיל במשפט הבא:

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

משפט זה בוודאי נכון - המסלול הזול ביותר מ$\displaystyle u$ ל$\displaystyle v$ הוא הזול ביותר מבין המסלולים שמותר להם לעבור דרך כל צומת בגרף. נמשיך במשפט שהשתבש מקודם:

משפט: $\displaystyle d^{(m)}(u,v)$ הוא: Edge-Costs[u][v], אם $\displaystyle m=0$. $\displaystyle min\{d^{(m-1)}(u,v),d^{(m-1)}(u,m)+d^{(m-1)}(m,v)\}$, אם $\displaystyle m>1$.

חלקו הראשון של המשפט נכון לפי ההגדרה. אם אין מעגלים שליליים, גם חלקו השני נכון. אם מ$\displaystyle u$ ל$\displaystyle v$ עוברים דרך $\displaystyle m$, אז אין טעמם לבדוק מסלולים שבהם מ$\displaystyle u$ ל$\displaystyle m$ או מ$\displaystyle m$ ל$\displaystyle v$ עוברים דרך $\displaystyle m$. מסלולים אלה כוללים מעגל כזה מ$\displaystyle m$ ל$\displaystyle m$, ומסלול אחר ללא מעגל זה בהכרח אינו יקר יותר.

6

נניח שזהו הגרף המקורי:

בעיית המסלול הזול ביותר.

נבנה גרף חדש כך.

ראשית, נקח את צמתי הגרף $\displaystyle V$, ונשכפל אותם 3 פעמים, בקבוצות $\displaystyle A$,‏ $\displaystyle B$, ו$\displaystyle C$. לכל צומת $\displaystyle u$ בקבוצה $\displaystyle A$, יש צומת $\displaystyle |V|+u$‏ ב$\displaystyle B$,‏ וצומת ‏ $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.‏ התרשים הבא מראה זאת.

שכפול הצמתים.

כעת נוסיף גם קשתות:

1. כל קשת בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין $\displaystyle u$ ב$\displaystyle A$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
2. כל קשת בין $\displaystyle u$ ל$\displaystyle v$ (בגרף המקורי) - נמתח אותה בגרף החדש בין הצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לבין הצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.

התרשים הבא מראה זאת (רק חלק מהקשתות מצויירות).

הוספת הקשתות.

בנוסף נמתח עוד שני סוגי קשתות:

1. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle 1$ בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle x+1$ בין $\displaystyle |V|+u$ ב$\displaystyle B$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא $\displaystyle \Theta (|V|+|E|)$.

המשפט הבא מסביר את חשיבות הגרף החדש.

משפט: מחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי (כולל הקנס, אם יש), קטן בדיוק ב1 ממחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש.

הוכחה: מבניית הגרף החדש, ברור שכל מסלול מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש, מורכב משני חלקים:

1. מסלול זהה לחלוטין למסלול מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי
2. מסלול בעלות 1 ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$, אם החלק הראשון זוגי, ומסלול בעלות $\displaystyle x+1$, אם החלק הראשון אי-זוגי.

לכן, כל שנותר הוא להריץ את אלגוריתם Dijkstra.

קל לראות שהסיבוכיות הכוללת היא זו של אלגוריתם Dijkstra.

7

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

נניח שזהו הגרף המקורי:

הבעיה המקורית.

נבנה גרף חדש כך.

ראשית, נקח את צמתי הגרף $\displaystyle V$, ונשכפל אותם 3 פעמים, בקבוצות $\displaystyle A$,‏ $\displaystyle B$, ו$\displaystyle C$. לכל צומת $\displaystyle u$ בקבוצה $\displaystyle A$, יש צומת $\displaystyle |V|+u$‏ ב$\displaystyle B$,‏ וצומת ‏ $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.‏ התרשים הבא מראה זאת.

שכפול הצמתים.

כעת נוסיף גם קשתות:

1. במקום כל קשת $\displaystyle (u,v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל$\displaystyle u$ ב$\displaystyle A$ לצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.
2. במקום כל קשת $\displaystyle (u,v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
3. במקום הקשת השלילית $\displaystyle (x,y)$ (בגרף המקורי), נמתח קשת מהצומת המתאים ל$\displaystyle x$ ב$\displaystyle A$ לצומת המתאים ל$\displaystyle y$ ב$\displaystyle B$ במחיר 0. התרשים הבא מראה זאת.

הוספת הקשתות.

נניח שלקשת השלילית היה מחיר $\displaystyle -z$. בנוסף נמתח עוד שני סוגי קשתות:

1. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle z$ בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle B$, נמתח קשת במחיר 0 בין $\displaystyle u+|V|$ ב$\displaystyle B$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא $\displaystyle \Theta (|V|+|E|)$.

המשפט הבא מסביר את חשיבות הגרף החדש.

משפט: מחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי, קטן בדיוק ב$\displaystyle z$ ממחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש.

הוכחה: בגרף המקורי, ייתכן שהמסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ לא השתמש בקשת השלילילת, וייתכן שהשתשמש בו. במקרה הראשון, תהיה קפיצה מ$\displaystyle A$ ישירות ל$\displaystyle C$, ובמקרה השני, תהיה קפיצה מ$\displaystyle A$ ל$\displaystyle B$ ומ$\displaystyle B$ ל$\displaystyle C$. הקפיצה מ$\displaystyle A$ ישירות ל$\displaystyle C$ עולה $\displaystyle z$ יותר מאשר המסלול המקורי. הקפיצות מ$\displaystyle A$ ל$\displaystyle B$ ומ$\displaystyle B$ ל$\displaystyle C$ גם כן עולות $\displaystyle z$ יותר מאשר המסלול המקורי, שכן עלות כל אחת משתי הקשתות היא 0, והנוסע לא קיבל את התשלום $\displaystyle z$ מהחברה.

כעת כל הקשתות אינן שליליות, ומותר להריץ את Dijkstra.

קל לראות שהסיבוכיות הכוללת היא זו של Dijkstra.