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

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

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

כדאי לדעת: #תכנון דינאמי מסביר בקצרה את הרעיון הכללי של תכנון דינאמי. הכפלת שרשרת מטריצות מראה יישום נוסף של רעיון התכנון הדינאמי.

הבעיה

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

דוגמה: נשתמש כדוגמה בברכות הבאות לאורך הדף: הבריכות והתעלות במסלולו של דג הסלמון המסכן.

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

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

דוגמה: אם הדג נח רק בברכה הראשונה והאחרונה, אז הזמן הכולל הוא $\displaystyle 1.5+2\cdot (1.5^{6}-1)+1$, אבל אם דג הסלמון נח גם בברכה השלישית, אז הזמן הכולל יורד ל$\displaystyle 1.5+2\cdot (1.5^{3}-1)+0.2+2\cdot (1.5^{3}-1)+1$. שני פתרונות אפשריים.

נניח שיש מערך גלובלי Resting-Times בגודל $\displaystyle n$, ואנו צריכים להשתמש בו כדי לחשב את זמן שחיית המינימום ואת ברכות העצירה.

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

נגדיר כ$\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.

אז מה רע?

הפתרון איטי.

משפט: זמן הריצה של Min-Time(n) הוא $\displaystyle \Omega (1.5^{n})$.‏

הוכחה: זמן הריצה של Min-Time(n) נתון ע"י נוסחת הנסיגה $\displaystyle T(n)=\sum _{i=1}^{n-1}[T(i)]+\Theta (n)$. אפשר להוכיח את החסם התחתון באינדוקציה. ‏

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

דוגמה: אם $\displaystyle n=100$, אז: Min-Time(1) נקרא מתוך Min-Time(2), ... , Min-Time(100). Min-Time(40) נקרא מתוך Min-Time(41), ... , Min-Time(100). Min-Time(1) נקרא פעמים רבות לכל אחת מקריאות אלה!

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

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

כדאי לדעת: אפשר לראות שMin-Time(1) נקרא הן מתוך Min-Time(2) והן מתוך Min-Time(98). אומרים על כך שיש overlapping subproblems.

תזכור (Memoization)

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

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

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

# 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" - בפעם הראשונה שקוראים להן, זמן הריצה עשוי להיות שונה מזה שפעם השניה ואילך.

איך לא לנתח

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

דוגמה: להלן הפסוודו-קוד של מיון מיזוג: # Merge sort. # Takes an array (Values). # Returns an array of the same elements, sorted in increasing order. Merge-Sort(Values) 1 if Length(Values) <= 1 2 return Values 3 mid = ⌊(1 + Length(Values)) / 2⌋ 4 L = Merge-Sort( Values[1, ... , mid] ) 5 R = Merge-Sort( Values[mid + 1, ... , Length(Values)] ) 6 return Merge(L, R) הפונקציה Merge פועלת בזמן לינארי. נקבל, לכן, את נוסחת הנסיגה $\displaystyle T(n)=2\cdot T(n/2)+\Theta (n)$, שאותה נוכל לפתור (בין היתר) על ידי הפרישה הבאה: עץ הפרישה של מיון מיזוג. נשים לב שבעץ זה, כל צומת מתאר קריאה אחת של האלגוריתם. צומת הראש, לדוגמה, פועל בזמן $\displaystyle \Theta (n)$, אך מבצע שתי קריאות נוספות. ‏

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

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

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

איך לנתח

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

נגדיר את $\displaystyle T'(k)$ כזמן שאורכת Min-Time(k) בהנחה שכ"א מהקריאות לMin-Time(1), ..., Min-Time(k - 1) היא $\displaystyle O(1)$.

משפט: זמן הריצה של Min-Time(n) הוא $\displaystyle \sum _{k=1}^{n}[T'(k)]$.

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

משפט: זמן הריצה של Min-Time(n) הוא $\displaystyle \Theta (n^{2})$.

הוכחה: מהתבוננות בקוד, אם כל קריאה רקורסיבית היא $\displaystyle O(1)$, אז נקבל $\displaystyle T'(k)=\Theta (k)$. לכן, במקרה זה $\displaystyle \sum _{k=1}^{n}[\Theta (k)]=\Theta \left(\sum _{k=1}^{n}[k]\right)=\Theta (n^{2})$.

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

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

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

חלק מהצמתים מודגשים, וחלק אינם:

1. צומת מודגש אם הוא מתאר קריאה "רצינית", כלומר אחת שבה החלק העיקרי בפונקציה מתבצע (שורות 3-11 בMin-Time).
2. צומת אינו מודגש אם הוא מתאר קריאה "פושטית", בה לכל היותר רק חלק הmemoization מתבצע (שורות 1-2 בMin-Time).

נשים לב לנקודות הבאות:

1. אם צומת לא מודגש, אז אין לו ילדים, ובנוסף, הוא $\displaystyle O(1)$ (מדוע?)
2. כל צומת מופיע מודגש פעם אחת (מדוע?)

ננתח כעת בשלבים, לפי הרעיון הבא. בכל שלב:

1. ניקח צומת $\displaystyle k$ מודגש שאין לו ילדים מודגשים.
2. ננתח את זמן הריצה שלו, ונרשום את התוצאה בצד. נשים לב שאם לצומת אין ילדים מודגשים, אז כל קריאה רקורסיבית שלו היא אכן $\displaystyle O(1)$ (מפני שזו איננה ממש קריאה רקורסיבית). זמן הריצה שלו, לכן, הוא אכן $\displaystyle T'(k)$.
3. נמיר אותו בצומת לא מודגש, מפני שניתחנו כבר את חלק הקוד המסובך בו (ורשמנו אותו בצד). כל שנותר הוא הקריאה לפונקציה, והיא לוקחת $\displaystyle O(1)$.

לבסוף נישאר עם צומת יחיד לא מודגש (כלומר בעל זמן ריצה $\displaystyle O(1)$, ולכן נקבל שסכום זמני הריצה ששמרנו בצד, הוא בדיוק זמן הריצה של האלגוריתם.

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

דוגמה: נתחיל בצומת 1 המודגש. לצומת זה אין כלל ילדים, ולכן זמן הקריאה הוא בבירור $\displaystyle T'(1)$. נרשום בצד שעד כה הקריאות שעברנו עליהן עלו $\displaystyle T'(1)$, ונחליף את הצומת 1 בצומת לא מודגש. זה מסמן את העובדה שניתחנו כבר את החלק "עם הבשר" בצומת 1, וכל שנותר הוא $\displaystyle O(1)$. עץ הקריאות הרקורסיביות - שלב 1. נעבור לצומת 2 המודגש. לצומת זה יש ילד לא מודגש יחיד, ולכן במקרה זה זמן הקריאה הוא $\displaystyle T(2)$ (מפני שהקריאה הרקורסיבית איננה ממש רקורסיבית, אלא קריאה ל"חלק הפושטי" שעולה $\displaystyle O(1)$). נוסיף בצד לקריאות שעברנו עליהן את $\displaystyle T'(2)$, ונחליף את הצומת 2 בצומת לא מודגש. זה מסמן את העובדה שניתחנו כבר את החלק "עם הבשר" בצומת 2, וכל שנותר הוא $\displaystyle O(1)$. עץ הקריאות הרקורסיביות - שלב 2. כנ"ל לגבי צומת 3. עץ הקריאות הרקורסיביות - שלב 3. נמשיך כך כל הדרך עד $\displaystyle n-1$. עץ הקריאות הרקורסיביות - שלב n - 1. כשנגיע לצומת $\displaystyle n$, כל ילדיו אינם מודגשים, לכן נוכל לעשות עבורו אותו הדבר. עץ הקריאות הרקורסיביות - שלב n.

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

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

# 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

והנה הפונקציה Print-Stops שתדפיס את העצירות:

# 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) )

הפרק הקודם: תכנון דינאמי

תכנון דינאמי - דג הסלמון

הפרק הבא: תכנון דינאמי - הכפלת שרשרת מטריצות