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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 37:
==הרקורסיה הפשוטה==
 
{{:מבני נתונים ואלגוריתמים - מחברת קורס/נספחים/חשיבה רקורסיבית/דג הסלמון/הרקורסיה הפשוטה}}
נגדיר כ<math dir = "ltr">\displaystyle m(k)</math> את הזמן המינימלי הנדרש לנוח בברכה <math dir = "ltr">\displaystyle 1</math>, לשחות מברכה <math dir = "ltr">\displaystyle 1</math> לברכה <math dir = "ltr">\displaystyle k</math>, ולנוח בברכה <math dir = "ltr">\displaystyle k</math>.
{{משימה|1 =
עפ"י הגדרה זו, <math dir = "ltr">\displaystyle m(n)</math> הנו הזמן שאנו מחפשים. וודא שהנך מבין מדוע.}}
 
{{משפט|תוכן =
<math dir = "ltr">\displaystyle m(k)</math> מקיים את הנוסחה הבאה:
#אם <math dir = "ltr">\displaystyle k = 1</math>, אז <math dir = "ltr">\displaystyle m(k)</math> = {{קוד בשורה|Resting-Times[1]}}.‏
#אם <math dir = "ltr">\displaystyle k > 1</math>, אז <math dir = "ltr">\displaystyle m(k) = min_{1 \le i < k} ( m(i) + 2 \cdot
(1.5^{k - i} - 1))</math> + {{קוד בשורה|Resting-Times[k]}}.‏ ‏}}
 
{{הוכחה|1 =
המקרה <math dir = "ltr">\displaystyle k =1</math> ברור.
 
אם <math dir = "ltr">\displaystyle k > 1</math>, אז בהכרח הדג נח בברכה כלשהי עד ל<math dir = "ltr">\displaystyle k</math> - ככלות הכל הוא נח בברכה הראשונה. '''נגדיר''' כ<math dir = "ltr">\displaystyle i</math> את הברכה האחרונה בה הדג נח לפני <math dir = "ltr">\displaystyle k</math>. המסלול מתחלק לשני חלקים: עד לברכה <math dir = "ltr">\displaystyle i</math> (כולל המנוחה בה), ומברכה <math dir = "ltr">\displaystyle i</math> ועד
לברכה <math dir = "ltr">\displaystyle k</math> (כולל המנוחה בה).
 
מברכה <math dir = "ltr">\displaystyle i</math> ועד לברכה <math dir = "ltr">\displaystyle k</math>, הזמן שיארך הוא <math dir = "ltr">\displaystyle 2 \cdot (1.5^{k - i} - 1)</math> + {{קוד בשורה|Resting-Times[k]}} (כולל זמן המנוחה בברכה האחרונה), וזה בלי קשר למסלול שיבחר דג הסלמון מברכה <math dir = "ltr">\displaystyle 1</math> ועד למנוחתו בברכה <math dir = "ltr">\displaystyle i</math>. כדי לצמצם את סכום הזמנים, לכן, הדג צריך לצמצם את זמן המסלול הראשון; עפ"י ההגדרה, זמן המסלול הטוב ביותר מברכה <math dir = "ltr">\displaystyle 1</math> לברכה <math dir = "ltr">\displaystyle i</math> (כולל המנוחה בה) הוא <math dir = "ltr">\displaystyle m(i)</math>.}}
 
הבעיה היחידה היא שאיננו יודעים את <math dir = "ltr">\displaystyle i</math>, אבל קל לבדוק מהו ה<math dir = "ltr">\displaystyle i</math> המשתלם ביותר בעזרת לולאה:
<source lang = "python">
# 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</source>
 
{{הארה|1 =
בבעיה זו, הפתרון האופטימאלי לבעיה בגודל <math dir = "ltr">\displaystyle k</math> כולל פתרון אופטימאלי לאותה בעיה, אך בגודל <math dir = "ltr">\displaystyle i < k</math>. ‏ על בעיות כאלה אומרים שיש להן ''optimal substructure''.}}
 
==אז מה רע?==