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

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

משפט:

$\displaystyle m(i)$ נתונה על ידי נוסחת הנסיגה הבאה:

אם

$\displaystyle i=1$ ,‏ אז $\displaystyle f(1)$ .

אם

$\displaystyle i>1$ ,‏ אז $\displaystyle \min \left\{f(i),\min _{j|1\leq j<i}m(i)+k+m(j-i)\right\}$ .

הוכחה: #אם $\displaystyle i=1$ ,‏ אז אין מה לחתוך; ההובלה תעלה $\displaystyle f(1)$ .

אם

$\displaystyle i>1$ ,‏ אז או שלא חותכים את הקטע, או שכן. אם לא חותכים, עלות השבירה 0, ועלות ההובלה $\displaystyle f(i)$ . אם חותכים בנקודה $\displaystyle j$ , אז עלות הטיפול בחלק השמאלי תהיה , עפ"י ההגדרה, $\displaystyle m(j)$ ,‏ עלות השבירה היא כמובן $\displaystyle k$ ,‏ ועלות הטיפול בחלק הימני תהיה, עפ"י ההגדרה, $\displaystyle m(i-j)$ . נותר לקחת מינימום על פני $\displaystyle j$ , ולהחליט האם לחתוך או לא.

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

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 &gt; Min-Cost(j) + k + Min-Cost(i - j)
7				guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
		
8		if guess-with

נוסיף 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 &gt; 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-with
10			return guess-with
11		else
12			'''M[i] = guess-without'''	
13			return guess-without

המערך הגלובלי Mבאורך nמאותחל תחילה כולו ל Nil. נוסיף גם מספיק מידע לצורך הדפסת פרטי הפתרון (השינויים מודגשים כך).

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 &gt; 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			return guess-with
14		else
15			M[i] = guess-without'''	
16			return guess-without

המערך הגלובלי Breakמכיל את ההחלטה שעשינו לגבי כל קטע. Break[i]הוא Nilאם החלטנו לא לחלק את הקטע, והוא $\displaystyle j$ אם החלטנו לשבור בנקודה j. כעת נדפיס את העצירות, ע"י קריאה ל Print-Breaks(n, 0). הפונקציה מוגדרת להלן.

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)

הפונקציה מקבלת שני ארגומנטים: אורך הקטע, i,‏ ותחילת הקטע, start.‏ נניח שהפונקציה נקראה עבור שני ערכים ספיציפיים כאלה. אם {{{1}}}, אז לא חתכנו את הקטע, ואין מה להדפיס. אם לא, ו {{{1}}}, אז יש להדפיס את הנקודה j(תוך זכירה שאנו נמצאים startמתחילת כל הגשר), את החלק השמאלי, ואת החלק הימני. הסיבוכיות הנה $\displaystyle \Theta \left(n^{2}\right)$ , וזאת מניתוח דומה מאד לזה שב [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]].