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

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

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


עכשיו תורכם:

עפ"י הגדרה זו, הנו הזמן שאנו מחפשים. וודא שהנך מבין מדוע.



משפט:

מקיים את הנוסחה הבאה:

  1. אם , אז = Resting-Times[1]‏.
  2. אם , אז + Resting-Times[k].



הוכחה: המקרה ברור.

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

מברכה ועד לברכה , הזמן שיארך הוא + Resting-Times[k] (כולל זמן המנוחה בברכה האחרונה), וזה בלי קשר למסלול שיבחר דג הסלמון מברכה ועד למנוחתו בברכה . כדי לצמצם את סכום הזמנים, לכן, הדג צריך לצמצם את זמן המסלול הראשון; עפ"י ההגדרה, זמן המסלול הטוב ביותר מברכה לברכה (כולל המנוחה בה) הוא .

מש"ל.PNG

הבעיה היחידה היא שאיננו יודעים את , אבל קל לבדוק מהו ה המשתלם ביותר בעזרת לולאה:

# Calculates the minimum time for the fish to swim up to (including) some pool (k).
# Takes the up-to pool number (k).
Min-Time(k)
1	if k == 1
2		return Resting-Times[k]
		
3	min-time = 
	
4	for i in [1, ..., k - 1]
5		guess = Min-Time(i) + 2 * (1.5^(k - i) - 1) + Resting-Times[k]
					
6		if guess < min-time
7			M[k] = min-time = guess
			
8	return min-time


כדאי לדעת:

בבעיה זו, הפתרון האופטימאלי לבעיה בגודל כולל פתרון אופטימאלי לאותה בעיה, אך בגודל . ‏ על בעיות כאלה אומרים שיש להן optimal substructure.