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

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

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

1. כפי שצוין בשאלה, נגדיר את אורך $\displaystyle P$ כ$\displaystyle n$.
2. נסמן את הנקודות שבמערך כ$\displaystyle p_{1}=(x_{1},y_{1}),p_{2}=(x_{2},y_{2}),...,p_{n}=(x_{n},y_{n})$. כאמור, אנו מניחים שהנקודות כבר ממוינות כך ש$\displaystyle x_{1}\leq x_{2}\leq ...\leq x_{n}$.
3. נסמן את המרחק בין שתי נקודות $\displaystyle p=(x,y)$ ו$\displaystyle p'=(x',y')$ כ$\displaystyle d(x,y)={\sqrt {(x-x')^{2}+(y-y')^{2}}}$.
4. נאמר ששני מסלולים שקולים אם אחד מתקבל מהשני ע"י החלפת כווני החיצים.

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

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

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

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

נגדיר את $\displaystyle m(i,j)$ ‏($\displaystyle 1\leq j<i\leq n$)‏ כעלות המסלול הזול ביותר שמקיים את התנאים הבאים:

1. המסלול מתחיל ב$\displaystyle p_{i}$ וממשיך כלפי שמאל עד ל$\displaystyle p_{1}$.
2. כשהמסלול מגיע (מכוון ימין) ל$\displaystyle p_{1}$, הוא מסתובב ימינה, וממשיך עד ל$\displaystyle p_{j}$‏‏ שם הוא מסתיים.
3. המסלול עובר דרך כל אחד מהנקודות $\displaystyle p_{1},p_{2},...,p_{i}$ בדיוק פעם אחת.

שימו לב: המסלול שעליו דיברנו זה עתה אינו מעגלי. הוא מתחיל ב$\displaystyle p_{i}$, ומסתיים ב$\displaystyle p_{j}\neq p_{i}$.

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

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

משפט: מחיר המסלול הביטוני הזול ביותר הוא $\displaystyle min_{1\leq j<n}[m(n,j)+d(p_{j},p_{n})]$.

הוכחה: במסלול המעגלי הקצר ביותר, נסמן כ$\displaystyle p_{j}$ את הנקודה הימנית ביותר לפני $\displaystyle p_{n}$ שנמצאת בחלק המסלול לכוון ימין (ראה התרשים הבא). המסלול, לכן, מורכב משלושה חלקים:

1. מ$\displaystyle p_{1}$ ימינה ל$\displaystyle p_{j}$
2. מ$\displaystyle p_{j}$ ימינה ישירות ל$\displaystyle p_{n}$
3. מ$\displaystyle p_{n}$ שמאלה חזרה ל$\displaystyle p_{1}$

עלות הקטע 2 היא בדיוק $\displaystyle d(p_{j},p_{n})$. סכום עלויות הקטע 1 ו3 הוא בדיוק $\displaystyle m(n,j)$.

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

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

משפט: $\displaystyle m(i,j)$ נתון על ידי נוסחת הנסיגה הבאה: $\displaystyle m(i,1)=\sum _{k=1}^{i-1}[d(k,k+1)]$, לכל $\displaystyle i\geq 1$. $\displaystyle m(i,i-1)=min_{1\leq k<i-1}[m(i-1,k)+d(k,i)]$, לכל $\displaystyle i>1$. $\displaystyle m(i,j)=m(i-1,j)+d(i-1,i)$, לכל $\displaystyle i>1,j<i-1$.

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

1. $\displaystyle m(i,1)$ הוא אורך המסלול הזול ביותר שעובר שמאלה מ$\displaystyle p_{i}$ ל$\displaystyle p_{1}$, מ$\displaystyle p_{1}$ פונה ימינה, אינו מגיע לאף נקודה אחרת מכוון ימין, ומכסה את כל הנקודות משמאלה ל$\displaystyle p_{i}$. לכן, בהכרח, מדובר במסלול שעובר נקודה אחרי נקודה מ$\displaystyle p_{i}$ ל$\displaystyle p_{1}$.
2. $\displaystyle m(i,i-1)$ הוא אורך המסלול הזול ביותר שעובר שמאלה מ$\displaystyle p_{i}$ ל$\displaystyle p_{1}$, מ$\displaystyle p_{1}$ ימינה ל$\displaystyle p_{i-1}$, ומכסה את כל הנקודות משמאלה ל$\displaystyle p_{i}$. נסמן כ$\displaystyle p_{k}$ את הנקודה שאליה עובר המסלול ישירות מ$\displaystyle p_{i}$; A בתרשים הבא מציג זאת.

   

   מקרה 2 בהוכחת נוסחת הנסיגה.

   היות שהוכחנו למעלה שלמסלולים שקולים יש מחיר זהה, נוכל לטעון שB בתרשים הקודם בעל אותו מחיר כA.
3. $\displaystyle m(i,j)$ הוא אורך המסלול הזול ביותר שעובר שמאלה מ$\displaystyle p_{i}$ ל$\displaystyle p_{1}$, מ$\displaystyle p_{1}$ ימינה ל$\displaystyle p_{j}$, ומכסה את כל הנקודות משמאלה ל$\displaystyle p_{i}$. היות ש$\displaystyle j<i-1$, המסלול חייב להתחיל במעבר ישיר (שמאלה) מ$\displaystyle p_{i}$ ל$\displaystyle p_{i-1}$.

   

   מקרה 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() מוצא את הנקודה $\displaystyle j$ הימנית ביותר כפי שראינו מקודם בקשר בין הבעיה המעגלית והבעיה הלא-מעגלית.
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]

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

הסיבוכיות היא $\displaystyle \Theta (n^{2})$:

1. איתחול המטריצה הוא $\displaystyle \Theta (n^{2})$.
2. נסמן כ $\displaystyle T'(i,j)$ את זמן הריצה של IJ-Length(i, j),‏ ‏ בהנחה שכל אחת מהקריאות הרקורסיביות היא $\displaystyle O(1)$. אפשר לראות ש$\displaystyle T'(i,j)=O(1)$,‏ כל עוד $\displaystyle j\neq 1,i-1$, ואחרת $\displaystyle T'(i,j)=\Theta (i)$. קל לראות שסך כל ריצת הפונקציה הוא

$\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{i-1}[T'(i,j)]=\sum _{i=1}^{n}\sum _{j=1}^{i-2}[T'(i,j)]+\sum _{i=1}^{n}[T'(i,i-1)]=\sum _{i=1}^{n}\sum _{j=1}^{i-2}[O(1)]+\sum _{i=1}^{n}[\Theta (i)]=\Theta (n^{2})$.