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

נגדיר כ$\displaystyle m(k)$ את הזמן המינימלי הנדרש לנוח בברכה $\displaystyle 1$, לשחות מברכה $\displaystyle 1$ לברכה $\displaystyle k$, ולנוח בברכה $\displaystyle k$.

עכשיו תורכם: עפ"י הגדרה זו, $\displaystyle m(n)$ הנו הזמן שאנו מחפשים. וודא שהנך מבין מדוע.

משפט: $\displaystyle m(k)$ מקיים את הנוסחה הבאה: אם $\displaystyle k=1$, אז $\displaystyle m(k)$ = Resting-Times[1]‏. אם $\displaystyle k>1$, אז $\displaystyle m(k)=min_{1\leq i<k}(m(i)+2\cdot (1.5^{k-i}-1))$ + Resting-Times[k]. ‏

הוכחה: המקרה $\displaystyle k=1$ ברור.

אם $\displaystyle k>1$, אז בהכרח הדג נח בברכה כלשהי עד ל$\displaystyle k$ - ככלות הכל הוא נח בברכה הראשונה. נגדיר כ$\displaystyle i$ את הברכה האחרונה בה הדג נח לפני $\displaystyle k$. המסלול מתחלק לשני חלקים: עד לברכה $\displaystyle i$ (כולל המנוחה בה), ומברכה $\displaystyle i$ ועד לברכה $\displaystyle k$ (כולל המנוחה בה).

מברכה $\displaystyle i$ ועד לברכה $\displaystyle k$, הזמן שיארך הוא $\displaystyle 2\cdot (1.5^{k-i}-1)$ + Resting-Times[k] (כולל זמן המנוחה בברכה האחרונה), וזה בלי קשר למסלול שיבחר דג הסלמון מברכה $\displaystyle 1$ ועד למנוחתו בברכה $\displaystyle i$. כדי לצמצם את סכום הזמנים, לכן, הדג צריך לצמצם את זמן המסלול הראשון; עפ"י ההגדרה, זמן המסלול הטוב ביותר מברכה $\displaystyle 1$ לברכה $\displaystyle i$ (כולל המנוחה בה) הוא $\displaystyle m(i)$.

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

# 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

כדאי לדעת: בבעיה זו, הפתרון האופטימאלי לבעיה בגודל $\displaystyle k$ כולל פתרון אופטימאלי לאותה בעיה, אך בגודל $\displaystyle i<k$. ‏ על בעיות כאלה אומרים שיש להן optimal substructure.