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

גרסה עם הדפסת המסלולים הזולים ביותר עצמם

שאלה

בהרצאה ראינו שני אלגוריתמים למציאת מחירי המסלולים הזולים לכלל הזוגות: אלגוריתם "הכפלת מטריצות" ואלגוריתם Floyd-Warshall. כעת רוצים להיות מסוגלים גם לענות על השאלה מה צמתי המסלול הזול ביותר מכל $\displaystyle u$ לכל $\displaystyle v$. אנא שנה את האלגוריתם כך שיחזיר זוג (Min-Costs, Min-Cost-Paths) (עליך להחליט בעצמך מאיזה סוג טיפוס הוא Min-Cost-Paths). אנא עשה זאת בצורה שלא תפגע בסיבוכיות האלגוריתם. אנא כתוב גם פונקציה Cheapest-Path(Min-Costs-Path, u, v) המקבלת את הערך המוחזר ושני צמתים, ומדפיסה בסיבוכיות \Theta( במקרה הגרוע את צמתי המסלול הקצר ביותר בין שני הצמתים.

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

תשובה

רעיון משותף

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

1. נשנה את הפסוודו-קוד כך שיחזיר גם מטריצה $\displaystyle P$ אשר מכילה בכניסה ה[u][v] את צומת $\displaystyle w$ זה.
2. נשתמש בפונקציה הבאה, אשר מקבלת מטריצה $\displaystyle P$ זו ושני צמתים, ומשתמשת בצמתי הביניים כדי

להדפיס את צמתי הביניים של המסלול ביניהם. (בכל אחד משני הסעיפים יהיה ברור ש$\displaystyle P$ למעשה מתארת את המסלול הזול ביותר, ולכן היא נקראת כאן Min-Costs-Path.)

Cheapest-Path(Min-Costs-Path, u, v)
1	w = Min-Costs-Path[u][v]

2	if w == u or w == v
3		return

4	Cheapest-Path(Min-Costs-Path, u, w)

5	print w

6	Cheapest-Path(Min-Costs-Path, w, v)

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

Matrix-Multiplication(G, Edge-Costs, m)
1	P = Make-Matrix(n, n)

2	if m == 1
3		for u in V(G)
4			for v in V(G)
5				P[u][v] = v		

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

17	return (D, P)

אלגוריתם Floyd-Warshall

Floyd-Warshall(G, Edge-Costs, m)
1	P = Make-Matrix(n, n)

2	if m == 0
3		for u in V(G)
4			for v in V(G)
5				P[u][v] = v		

6		return (Edge-Costs, P)

7	D' = Floyd-Warshall(G, Edge-Costs, m - 1)

8	n = Length( V(G) )

9	D = Make-Matrix(n, n)

10	for u in V(G)
11		for v in V(G)
12			D[u][v] = D'[u][v]

13			if D[u][v] > D'[u][m] + D'[m][v]
14				D[u][v] = D'[u][m] + D'[m][v]
15				P[u][v] = m

16	return (D, P)

ווריאציה עם מחירים שליליים

שאלה

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

שימו לב: הטענות עבור שני האלגוריתמים דומות מאד זו לזו. אנא בחר אלגוריתם אחד מהשניים, ענה על השאלה לגביו, ורק וודא שהנך יודע לפתור את השני.

1. אנא הוכח שכאשר יש בגרף מעגלים בעלי משקל שלילי (כלומר מעגל שסכום קשתותיו שלילי), אז בהכרח קיימים שני צמתים, $\displaystyle u$ ו$\displaystyle v$, כך שאין מסלול סופי זול ביותר מ$\displaystyle u$ ל$\displaystyle v$.
2. האלגוריתמים שראינו אכן מוצאים תמיד מסלול סופי. אנא הסבר היכן הוכחת הנכונות מניחה במובלע שאין מעגלים בעלי משקל שלילי.
3. אנא הוכח שכאשר אין מעגלים בעלי משקל שלילי, אז בלי קשר לסימן משקל הקשתות, האלגוריתמים אכן עובדים.

תשובה

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$, ומסלול אחר ללא מעגל זה בהכרח אינו יקר יותר.

זיהוי ארביטראג'

שאלה

יחסי המרה

	שקל	דולר	דינאר	דונג
שקל	1	0.2		100
דולר	4.5	1	3	10000
דינאר		0.2	1	1000
דונג	0.001	0.00009	0.0009	1

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

דוגמה: בטבלה שמשמאל: ניתן להמיר $\displaystyle 1$ שקל ל$\displaystyle 0.2$ דולר. ניתן להמיר $\displaystyle 1$ דולר ל$\displaystyle 4.5$ שקל. אי אפשר להמיר ישירות שקל לדינאר.

הגדרה: נאמר שקיים ארביטראז' אם קיימת סדרת המרות שמסתיימת ברווח חד-משמעי.

דוגמה: בטבלה שמשמאל, נניח שאנו מתחילים עם $\displaystyle 1$ שקל. נמיר את השקל ל $\displaystyle 0.2$ דולר. נמיר את $\displaystyle 0.2$הדולר ל$\displaystyle 0.2\cdot 10000=2000$ דונג. נמיר את $\displaystyle 2000$ הדונג ל$\displaystyle 2$ שקלים. הכפלנו את כספנו!

אנא מצא אלגוריתם יעיל המוצא האם בטבלת המרות כלשהי קיים ארביטראז'.

רמז: השתמש בזהות הידועה $\displaystyle \log(p_{1}\cdot p_{2}\cdots p_{k})=\log(p_{1})+\log(p_{2})+\cdots +\log(p_{k})$.

תשובה

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

זיהוי מעגלים שליליים

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

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

מציאת ארביטראז'

נבנה גרף חדש שבו הצמתים מתאימים למטבעות השונים, והקשתות מתארות המרות בין המטבעות. אם אפשר להמיר מטבע אחד למטבע שני ביחס $\displaystyle p$, אז נייחס מחיר $\displaystyle \log(1/p)$ לקשת. נשים לב שאם יש ארביטראז', אז קיימת סדרת המרות המקיימת $\displaystyle p_{1}\cdot p_{2}\cdots p_{k}>1$. תנאי זה שקול לתנאי $\displaystyle \log \left(1/p_{1}\right)+\log \left(1/p_{2}\right)+\cdots +\log \left(1/p_{k}\right)=\log \left(1/(p_{1}\cdot p_{2}\cdots p_{k})\right)<\log(1)=0$. התנאי לארביטראז' בטבלה, לכן, שקול לתנאי למעגל שלילי בגרף החדש.