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

דף זה הוא הראשון משני דפים שעוסק ביישום רעיון התכנון הדינמי. אנו נתמקד ברעיון ה-memoization.

הבעיה

דג נולד בברכה הראשונה מתוך $n$ ברכות, המחוברות ע"י $n-1$ תעלות. הדג שוחה מהברכה הראשונה לאחרונה. לכל ברכה יש מספר המציין את משך הזמן שיש לשהות בה כדי להתאושש (חלק מהברכות נוחות יותר מהאחרות). התעלות, לעומת זאת, זהות, ושחייה בכל אחת מהן אורכת $1$ יחידות זמן.

תבנית:מבנה תבנית

דג הסלמון צריך לבחור באיזו ברכה לעצור ולנוח, כדי לצמצם את משך הזמן הכולל מהברכה הראשונה לאחרונה. מדוע שהדג יעצור לנוח בכלל בברכה כלשהי? נניח שאם הדג אינו עוצר בברכה, אז השחייה בתעלה הבאה אורכת $1.5$ יחידות זמן, השחייה בתעלה שלאחריה אורכת $1.5^2$ יחידות זמן, השחייה בתעלה שלאחריה אורכת $1.5^3$ יחידות זמן, וכן הלאה (עד שהדג עוצר לנוח בברכה). לשם הפשטות, נניח שהדג נח בברכה הראשונה והאחרונה.

מהו זמן המינימום למסלול הדג, ובאלו ברכות ינוח?

תבנית:מבנה תבנית

נניח שיש מערך גלובלי תבנית:קוד בשורה בגודל $n$, ואנו צריכים להשתמש בו כדי לחשב את זמן שחיית המינימום ואת ברכות העצירה.

הרקורסיה הפשוטה

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

תבנית:משפט

תבנית:הוכחה

הבעיה היחידה היא שאיננו יודעים את $i$, אבל קל לבדוק מהו ה$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			min-time = guess
			
8	return min-time

תבנית:הארה

אז מה רע?

הפתרון איטי.

תבנית:הוכחה

קצת מפתיע שהפתרון כ"כ איטי, מפני שאם מתבוננים בקוד של תבנית:קוד בשורה, אפשר לראות שהוא מבצע מספר ליניארי של פעולות (חוץ מקריאות רקורסיביות). יותר מכך, תבנית:קוד בשורה יכול להקרא רק עם $n$ ארגומנטים שונים. נראה שמספר הפעמים שהוא נקרא - הוא זה שגבוה כ"כ. במחשבה נוספת, נתן לראות שתבנית:קוד בשורה נקרא שוב ושוב עם אותם הארגומנטים.

תבנית:מבנה תבנית

להלן הרמות הראשונות בעץ הקריאות הרקורסיביות:

עץ הקריאות הרקורסיביות.

תזכור (Memoization)

בנקודה זו אנו יודעים שתבנית:קוד בשורה נקרא שוב ושוב עם אותם הארגומנטים. מדוע שלא נשמור פשוט את התוצאה של כל קריאה בפעם הראשונה שחישבנו אותה עבור ארגומנט כלשהו? נעשה זאת כך. ראשית, נגדיר מערך גלובלי תבנית:קוד בשורה, ונאתחל אותו ל$n$ ערכי תבנית:קוד בשורה:

# Initializes the M array to Nils.
Init(n)
1	M = Make-Array(n)
	
2	for i in [1, ..., n]
3		M[i] = Nil

כעת נשנה את תבנית:קוד בשורה כך שקודם יבדוק האם כבר חישבנו את התוצאה עבור הארגומנט הנתון. השינויים מסומנים כך:

# 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 M[k] != Nil
2		return M[k]
	
3	if k == 1
4		M[k] = Resting-Times[k]
5		return Resting-Times[k]
		
6	min-time = ∞
	
7	for i in [1, ..., k - 1]
8		guess = Min-Time(i) + 2 * (1.5^(k - i) - 1) + Resting-Times[k]
					
9		if guess < min-time
10			M[k] = min-time = guess
			
11	return min-time

מיד נראה האם שיפרנו בכך את סדר הגדילה של זמן הריצה.

ניתוח זמן הריצה בMemoization

ניתוח זמן הריצה של פונקציות המשתמשות בmemoization שונה מזה של הפונקציות האחרות בהן נתקלנו, מפני שהסיבוכיות שלהן היא "time dependent" - בפעם הראשונה שקוראים להן, זמן הריצה עשוי להיות שונה מזה שפעם השניה ואילך.

איך לא לנתח

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

תבנית:מבנה תבנית

נראה מדוע אין לעשות כן בפונקציות בעלות memoization. שוב, להלן הרמות הראשונות בעץ הקריאות הרקורסיביות:

עץ הקריאות הרקורסיביות.

ברור למדי שעץ זה אינו מתאר את הנעשה בפונקציה. לדוגמה, כבר לא נכון שכל קריאה ל2 תניב קריאה ל1 - זה נכון רק לפעם הראשונה שקוראים ל2. הפועל היוצא הוא שרבים מהצמתים המצויירים בעץ לא אמורים להיות קיימים - הם אינם משקפים קריאות שיתבצעו.

איך לנתח

להלן שיטה כללית לפתרון פונקציות בעלות memoization.

נגדיר את $T^{\prime }(k)$ כזמן שאורכת תבנית:קוד בשורה בהנחה שכ"א מהקריאות לתבנית:קוד בשורה, ..., תבנית:קוד בשורה היא $O(1)$.

תבנית:משפט

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

כעת נוכיח את המשפט הכללי לפתרון פונקציות בעלות memoization.

נראה כיצד לעשות זאת בעץ הקודם.

תבנית:מבנה תבנית

הדפסת העצירות

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

# 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 M[k] != Nil
2		return M[k]
	
3	if k == 1
4		M[k] = Resting-Times[k]
5		S[k] = k
6		return Resting-Times[k]
		
7	min-time = ∞
	
8	for i in [1, ..., k - 1]
9		guess = Min-Time(i) + 2 * (1.5^(k - i) - 1) + Resting-Times[k]
					
10		if guess < min-time
11			M[k] = min-time = guess
12			S[k] = i
			
13	return min-time

והנה הפונקציה תבנית:קוד בשורה שתדפיס את העצירות:

# Prints the stops on the fastest route up to
#	(and including) some pool number (i).
Print-Stops(i)
1	if i > 1
2		Print-Stops(S[i])
	
3	Print(i)

לסיכום, כך נדפיס הכל:

	# Run the algorithm, get the shortest time. 
1	m = Min-Time( Length(Resting-Times) )

	# Print the shortest time.
2	Print(m)
	
	# Print the stops.
3	Print-Stops( Length(Resting-Times) )

תבנית:מבני נתונים ואלגוריתמים - מחברת קורס