לדלג לתוכן

מבני נתונים ואלגוריתמים - מחברת קורס/תרגול השלמה - הנוסע המתמיד הביטוני אויקלידי

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

שאלה

[עריכה]

הגדרה:

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


כדאי לדעת:

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

שאלה זו דנה בגרסה קלה יותר של הבעיה.


הגדרה:

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




דוגמה:

בתרשים הבא, A מראה מישור בעל נקודות; B מראה את המסלול הקצר ביותר, אך המסלול אינו ביטוני.

מישור ומסלולים.
מישור ומסלולים.

בתרשים הבא, A וB מראים כל אחד מסלול ביטוני אפשרי.

מסלולים ביטוניים.
מסלולים ביטוניים.


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


שימו לב:

#הנח שP הוא מערך גלובלי בעל אורך המתאר את הנקודות.
  1. כדי לגשת לקואורדינטות הX והY של הנקודה ה, השתמש בP[i].x ובP[i].y, בהתאמה.
  2. הנח שP ממוין בסדר עולה על פי קואורדינטות הX של נקודותיו (ולכן P[1] היא בהכרח נקודת המוצא של הנוסע, לדוגמה).
  3. אנא נתח סיבוכיות תשובתך במונחי .

תשובה

[עריכה]

מספר סימונים ואבחנה פשוטה

[עריכה]

ראשית מספר סימונים:

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



דוגמה:

בתרשים הבא, A וB מראים מסלולים שקולים.

שני מסלולים שקולים.
שני מסלולים שקולים.


המשפט הבא נובע בקלות מהגדרת המרחק האוקלידי.



משפט:

אם שני מסלולים שקולים, אז מחירם זהה.


בעיה דומה לא-מעגלית

[עריכה]

נגדיר את ‏()‏ כעלות המסלול הזול ביותר שמקיים את התנאים הבאים:

  1. המסלול מתחיל ב וממשיך כלפי שמאל עד ל.
  2. כשהמסלול מגיע (מכוון ימין) ל, הוא מסתובב ימינה, וממשיך עד ל‏‏ שם הוא מסתיים.
  3. המסלול עובר דרך כל אחד מהנקודות בדיוק פעם אחת.

שימו לב:

המסלול שעליו דיברנו זה עתה אינו מעגלי. הוא מתחיל ב,

ומסתיים ב.

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

הקשר לבעיה המקורית (המעגלית)

[עריכה]

משפט:

מחיר המסלול הביטוני הזול ביותר הוא .


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

  1. מ ימינה ל
  2. מ ימינה ישירות ל
  3. מ שמאלה חזרה ל

עלות הקטע 2 היא בדיוק . סכום עלויות הקטע 1 ו3 הוא בדיוק .

הקשר בין m(i,j) למסלול המעגלי הזול ביותר.
הקשר בין m(i,j) למסלול המעגלי הזול ביותר.


נוסחת נסיגה לבעיה הלא-מעגלית

[עריכה]

משפט:

נתון על ידי נוסחת הנסיגה הבאה:

  1. , לכל .
  2. , לכל .
  3. , לכל .



הוכחה: נשקול את כל המקרים האפשריים:

  1. הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל, מ פונה ימינה, אינו מגיע לאף נקודה אחרת מכוון ימין, ומכסה את כל הנקודות משמאלה ל. לכן, בהכרח, מדובר במסלול שעובר נקודה אחרי נקודה מ ל.
  2. הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל, מ ימינה ל, ומכסה את כל הנקודות משמאלה ל. נסמן כ את הנקודה שאליה עובר המסלול ישירות מ; A בתרשים הבא מציג זאת.
    מקרה 2 בהוכחת נוסחת הנסיגה.
    מקרה 2 בהוכחת נוסחת הנסיגה.
    היות שהוכחנו למעלה שלמסלולים שקולים יש מחיר זהה, נוכל לטעון שB בתרשים הקודם בעל אותו מחיר כA.
  3. הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל, מ ימינה ל, ומכסה את כל הנקודות משמאלה ל. היות ש, המסלול חייב להתחיל במעבר ישיר (שמאלה) מ ל.
    מקרה 3 בהוכחת נוסחת הנסיגה.
    מקרה 3 בהוכחת נוסחת הנסיגה.


פסוודו-קוד

[עריכה]

להלן פסוודו-קוד המשתמש ברעיון זה:

IJ-Length(i, j)
1	if j == 1
2		ij-length = 0
		
3		for k in [1, ..., i - 1]
4			ij-length = ij-length + D(k, k + 1)
5	else if j == i - 1
6		ij-length = 

7		for k in [1, ..., i - 2]
8			guess = IJ-Length(i - 1, k) + D(k, i)
9			if ij-length > guess
10				ij-length = guess
11	else
12		ij-length = IJ-Length(i - 1, j) + D(i - 1, i)

13	return ij-length


Min-Bitonic-Euclidean()
1	if n == 1
2		return 0

3	min = 

4	for j in [1, ..., n - 1]
5		guess = IJ-Length(n, j) + D(j, n)
6		if min < guess
7			min = guess

8	return min


D(P, P')
1	return ((P'.x - P.x)^2 + (P'.y - P.y)^2)


להלן הסבר לפסוודו-קוד.

  1. IJ-Length(i, j) מממש את נוסחת הנסיגה שראינו מקודם לבעיה הלא-מעגלית.
  2. Min-Bitonic-Euclidean() מוצא את הנקודה הימנית ביותר כפי שראינו מקודם בקשר בין הבעיה המעגלית והבעיה הלא-מעגלית.
  3. D(P, P') היא פונקציית עזר המוצאת את המרחק בין שתי נקודות.

תזכור (Memoization)

[עריכה]

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

1	M = Make-Matrix(n, n)

2	for i in [1, ..., n]
3		for j in [1, ..., n]
4			M[i][j] = Nil


IJ-Length(i, j)
1	if M[i][j] == Nil
2		if j == 1
3			M[i][j] = 0
		
4			for k in [1, ..., i - 1]
5				M[i][j] = M[i][j] + D(k, k + 1)
6		else if j == i - 1
7			M[i][j] = 

8			for k in [1, ..., i - 2]
9				guess = IJ-Length(i - 1, k) + D(k, i)
10				if M[i][j] > guess
11					M[i][j] = guess
12		else
13			M[i][j] = IJ-Length(i - 1, j) + D(i - 1, i)

14	return M[i][j]

ניתוח סיבוכיות

[עריכה]

הסיבוכיות היא :

  1. איתחול המטריצה הוא .
  2. נסמן כ את זמן הריצה של IJ-Length(i, j),‏ ‏ בהנחה שכל אחת מהקריאות הרקורסיביות היא . אפשר לראות ש,‏ כל עוד , ואחרת . קל לראות שסך כל ריצת הפונקציה הוא

.