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

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

נגדיר כ את העלות הזולה ביותר לטיפול בקטע באורך .



משפט:

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

  1. אם

,‏ אז .

  1. אם

,‏ אז .



הוכחה: #אם ,‏ אז אין מה לחתוך; ההובלה תעלה .

  1. אם

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

מש"ל.PNG

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

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

נוסיף 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-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 > 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אם החלטנו לא לחלק את הקטע, והוא אם החלטנו לשבור בנקודה 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מתחילת כל הגשר), את החלק השמאלי, ואת החלק הימני. הסיבוכיות הנה , וזאת מניתוח דומה מאד לזה שב [[מבני נתונים ואלגוריתמים - מחברת קורס/#|]].