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

המבנה הרקורסיבי

נגדיר כ$m(i)$ את העלות הזולה ביותר לטיפול בקטע באורך $i$.

תבנית:הוכחה

מימוש נאיבי

להלן פסוודו-קוד המממש את נוסחת הנסיגה.

Min-Cost(i)
1	if i == 1
2		return F(1)
	
3	guess-without = F(i)

4	guess-with = ∞
5	for j in [1, …, i - 1]
6		if guess-with> Min-Cost(j) + k + Min-Cost(i - j)
7			guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
		
8	if guess-with < guess-without
9		return guess-with
10	else
11		return guess-without

שימוש בmemoization

נוסיף memoization.

Min-Cost(i)
1	if M[i] != Nil
2		return M[i]

1	if i == 1
2		M[1] = F(1)
3		return F(1)
	
4	guess-without = F(i)

5	guess-with = ∞
6	for j in [1, … i - 1]]
7		if guess-with> Min-Cost(j) + k + Min-Cost(i - j)
8			guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
		
9	if guess-with M[i] < guess-without
10		M[i] = guess-with
11		return guess-with
12	else
13		M[i] = guess-without
14		return guess-without

(נניח שהמערך הגלובלי תבנית:קוד בשורהבאורך תבנית:קוד בשורהמאותחל תחילה כולו לתבנית:קוד בשורה.)

הדפסת נקודות השבירה

נוסיף גם מספיק מידע לצורך הדפסת פרטי הפתרון.

Min-Cost(i)
1	if M[i] != Nil
2		return M[i]

1	if i == 1
2		M[1] = F(1)
3		Break[1] = Nil
4		return F(1)
	
5	guess-without = F(i)

6	guess-with = ∞
7	for j in [1, … i - 1]]
8		if guess-with> Min-Cost(j) + k + Min-Cost(i - j)
9			guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
10			if guess-with 
11				Break[i] = j
				
12	if guess-with 
13		M[i] = guess-with
14		return guess-with
15	else
16		M[i] = guess-without	
17		return guess-without

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

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

Print-Breaks(i, start)
1	if Break[i] == Nil
2		return
	
3	j = Break[i]
	
4	Print(j + start)

5	Print-Nums(j, start)
6	Print-Nums(i - j, start + j)

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

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

נגדיר את זמן הריצה של תבנית:קוד בשורה בהנחה שכל קריאה רקורסיבית היא $O(1)$ כ$T^{\prime }(i)$. קל לראות ש$T^{\prime }(i)=\mathrm{\Theta }(i)$. זמן הריצה חסום מלמעלה על ידי $\sum _{i=1}^n[T^{\prime }(i)]=\sum _{i=1}^n[\mathrm{\Theta }(i)]=\mathrm{\Theta }(n^2)$.

גם כאשר לוקחים בחשבון את האתחול והדפסת הפרטים, הפתרון עדיין $O(n^2)$.