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

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

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

שאלה[עריכה]

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


שימו לב:

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

תשובה[עריכה]

רעיון משותף[עריכה]

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

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

להדפיס את צמתי הביניים של המסלול ביניהם. (בכל אחד משני הסעיפים יהיה ברור ש למעשה מתארת את המסלול הזול ביותר, ולכן היא נקראת כאן 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. אנא הוכח שכאשר יש בגרף מעגלים בעלי משקל שלילי (כלומר מעגל שסכום קשתותיו שלילי), אז בהכרח קיימים שני צמתים, ו, כך שאין מסלול סופי זול ביותר מ ל.
  2. האלגוריתמים שראינו אכן מוצאים תמיד מסלול סופי. אנא הסבר היכן הוכחת הנכונות מניחה במובלע שאין מעגלים בעלי משקל שלילי.
  3. אנא הוכח שכאשר אין מעגלים בעלי משקל שלילי, אז בלי קשר לסימן משקל הקשתות, האלגוריתמים אכן עובדים.

תשובה[עריכה]

1[עריכה]

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


2[עריכה]

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

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



משפט:

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


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

אלגוריתם Floyd-Warshall[עריכה]

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



משפט:

הוא:

  1. Edge-Costs[u][v], אם .
  2. , אם .


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

3[עריכה]

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

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

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



משפט:

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


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

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



משפט:

לכל ,‏ הוא:

  1. Edge-Costs[u][v], אם .
  2. Edge-Costs[w][v], אם .

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

אלגוריתם Floyd-Warshall[עריכה]

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



משפט:

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


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



משפט:

הוא:

  1. Edge-Costs[u][v], אם .
  2. , אם .


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


זיהוי ארביטראג'[עריכה]

שאלה[עריכה]

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

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




דוגמה:

בטבלה שמשמאל:

  1. ניתן להמיר שקל ל דולר.
  2. ניתן להמיר דולר ל שקל.
  3. אי אפשר להמיר ישירות שקל לדינאר.



הגדרה:

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




דוגמה:

בטבלה שמשמאל, נניח שאנו מתחילים עם שקל.

  1. נמיר את השקל ל דולר.
  2. נמיר את הדולר ל דונג.
  3. נמיר את הדונג ל שקלים.

הכפלנו את כספנו!


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


רמז:

השתמש בזהות הידועה .

תשובה[עריכה]

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

זיהוי מעגלים שליליים[עריכה]

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

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

מציאת ארביטראז'[עריכה]

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