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

דף זה עוסק בחשיבה רקורסיבית, ובפרט בפתרון בעיות בעזרת הגדרת פתרונן כמורכב מפתרון בעיות קטנות יותר.

כדאי לדעת: רעיון זה נקרא לפעמים divide and conquer, או הפרד ומשול.

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

מה היא רקורסיה?

נניח שברצוננו לכתוב פונקציה המחשבת עצרת. נוכל לכתוב זאת בלולאה, כך:

# Calculates the factorial (atzeret).
# Takes a non-negative integer number (n).
Factorial(n)
1	ret = 1
	
2	for i in [1 … n]:
3		ret = ret * i
	
4	return ret

מהתבוננות בפונקציה, קל לראות שהיא מחזירה $\displaystyle 1\cdot 1\cdot 2\cdots n=n!$.

לחלופין, נוכל לכתוב את הפונקציה בצורה רקורסיבית, כך:

# Calculates the factorial (atzeret).
# Takes a non-negative integer number (n).
Factorial(n)
1	if n == 0
2		return 1
	
3	return n * Factorial(n - 1)

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

כיצד המהדר מתייחס לרקורסיה

מדוע עובדת הגרסה הרקורסיבית? להלן ההסבר הנפוץ בקורס תכנות. נניח שאנו קוראים לFactorial(3):

1. בקריאה הראשונה n == 3.‏ 1 תכשל, ו2 לא תתבצע. 3 תחזיר כתשובה את 3 כפול הערך המוחזר מFactorial(2).
2. בקריאה זו n == 2.‏ 1 תכשל, ו2 לא תתבצע. 3 תחזיר כתשובה את 2 כפול הערך המוחזר מFactorial(1).
3. בקריאה זו n==1.‏ 1 תכשל, ו2 לא תתבצע. 3 תחזיר כתשובה את 1 כפול הערך המוחזר מFactorial(0).
4. בקריאה זו n == 0.‏ 1 תצליח, ו2 תחזיר כתשובה את 1. ערך זה יוכפל ב1, התוצאה תוכפל ב2, והתוצאה תוכפל ב3.

הנקודה האחרונה מראה שמבחינת התוצאה המוחזרת, נקבל אותו הדבר כגרסת הלולאה. בשני המקרים נקבל $\displaystyle 1\cdot 1\cdot 2\cdot 3\cdot =3!$.

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

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

כעת נראה דרך אחרת, אינדוקטיבית יותר.

גישה אינדוקטיבית

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

הוכחה: (בסיס האינדוקציה) אם $\displaystyle n=0$ אז הפונקציה מחזירה $\displaystyle 1=0!$. זה ברור מ1-2.

(מעבר האינדוקציה) נניח שהפונקציה עובדת עד (כולל) $\displaystyle n-1\geq 0$, ונראה שהיא עובדת גם ל$\displaystyle n\geq 1$. אם $\displaystyle n\geq 1$, אז ברור ש1 תיכשל, ו2 לא תתבצע. עפ"י הנחת האינדוקציה, Factorial(n - 1) תחזיר $\displaystyle (n-1)!=1\cdot 1\cdot 2\cdots (n-1)$. לכן, 3 תחזיר $\displaystyle 1\cdot 1\cdot 2\cdots (n-1)\cdot n=n!$.

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

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

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

כעת נראה מספר דוגמאות לכך.

חישוב עצרת

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

# Calculates the factorial (atzeret).
# Takes a non-negative integer number (n).
Factorial(n)
1	if n == 0
2		return 1

נמשיך בכך שנניח שהפונקציה עובדת עבור בעיות קטנות יותר. כאן, בפרט, נניח שFactorial(n - 1) אכן מחזירה את $\displaystyle 1\cdot 1\cdot 2\cdots (n-1)=(n-1)!$. נותר רק להכפיל תוצאה זו ב$\displaystyle n$:

# Calculates the factorial (atzeret).
# Takes a non-negative integer number (n).
Factorial(n)
1	if n == 0
2		return 1
	
3	return n * Factorial(n - 1)

חיפוש לינארי

נמשיך בעוד דוגמה פשוטה. ניקח חיפוש לינארי, ונכתוב אותו בצורה רקורסיבית. נכתוב את הפונקציה כך שהיא תחפש את האיבר בתת-מערך המכיל את $\displaystyle i$ האיברים הראשונים:

# Linear search.   
# Takes an array (Values) and a value (v).
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search(Values, v)
1	return Linear-Search'(Values, v, Length(Values))


# Recursive linear search.
# Takes an array (Values), a value (v), and the length of the initial subsequence.
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search'(Values, v, i)

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

# Linear search.   
# Takes an array (Values) and a value (v).
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search(Values, v)
1	return Linear-Search'(Values, v, Length(Values))


# Recursive linear search.
# Takes an array (Values), a value (v), and the length of the initial subsequence.
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search'(Values, v, i)	
1	if i == 0
2		return False

נמשיך בכך שנניח שהפונקציה עובדת עבור בעיות קטנות יותר. כאן, בפרט, נניח ש Linear-Search'(Values, v, i) אכן בודקת נכונה האם $\displaystyle v$ מופיע ב$\displaystyle i-1$ המקומות הראשונים. נותר רק לבדוק האם האיבר ה$\displaystyle i$ הוא האיבר המבוקש:

# Linear search.   
# Takes an array (Values) and a value (v).
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search(Values, v)
1	return Linear-Search'(Values, v, Length(Values))


# Recursive linear search.
# Takes an array (Values), a value (v), and the length of the initial subsequence.
# Returns an element if it matches the value (v), Nil otherwise.
Linear-Search'(Values, v, i)	
1	if i == 0
2		return False
	
3	if Values[i] == v
4		return True
	
5	return Linear-Search'(Values, v, i - 1)

נותר פשוט להוכיח פורמאלית את מה שעשינו עד כה.

הוכחה: ההוכחה היא באינדוקציה על אורך המערך, $\displaystyle i$.

(בסיס האינדוקציה) אם המערך בעל אורך 0, אז אף איבר אינו חבר בו, ועל התשובה להיות Nil. אכן, 1-2 יחזירו Nil.

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

מיון מיזוג

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

# Merge. 
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R.
Merge(L, R)
1	Merged = Make-Array( Length(L) + Length(R) )
	
2	l = r = m = 1
	
3	while l <= Length(L) or r <= Length(R)
4		if r > Length(R)
5			Merged[m++] = L[l++]
6		else if l > Length(L)
7			Merged[m++] = R[r++]
8		else if L[l] < R[r]
9			Merged[m++] = L[l++]
10		else
11			Merged[m++] = R[r++]

12	return Merged

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

כרגיל, נתחיל בכך שנטפל בבעיות הקטנות שאין יכולת או צורך לחלק אותן הלאה. כאן, במקרה הזה, אם המערך קטן מספיק, כלומר ארכו 0 או 1 - הוא ממוין.

# 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

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

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

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

הוכחה: נקבע כ$\displaystyle n$ את Length(Values). ההוכחה היא באינדוקציה על $\displaystyle n$.

(בסיס האינדוקציה) עבור $\displaystyle n=0$ או$\displaystyle n=1$,‏ 1-2 מחזירות פשוט את Values, שבמקרה זה ממוין עפ"י הגדרה.

(מעבר האינדוקציה) נניח שMerge-Sort עובדת לכל $\displaystyle n'<n$. אז 4-5 ממיינות את החצי השמאלי והימני לפי בסיס האינדוקציה (כי הפונקציה פועלת על מערכים קטנים יותר). 6 פועלת לכן על שני מערכים ממוינים, ולכן מחזירה את המערך ממוין.

סכום תת-סידרה

נניח ש$\displaystyle A$ הוא מערך של מספרים שלמים חיוביים, ו$\displaystyle t$ מספר יעד שלם לא-שלילי כלשהו. רוצים לבדוק האם קיימת תת-קבוצה של הערכים ב$\displaystyle A$ שסכום איבריה הוא בדיוק $\displaystyle t$.

דוגמה: נניח שהמערך מייצג את הערכים $\displaystyle A=[2,1,10,40,20]$ אם $\displaystyle t=52$, אז התשובה היא True, מפני ש$\displaystyle 2+10+40=52$. אם $\displaystyle t=4$ אז התשובה היא False, מפני שכפי שבדיקה פשוטה תראה, אין ערכים שסכומם 4.

מה חדש כאן יחסית למה שכבר ראינו?

1. מדובר כאן בבעיית הכרעה (כלומר, משהו שמחליט True או False), ולא בחישוב, כמקודם. (זו נקודה שולית למדי.)
2. כאן יש שתי דרגות חופש לגבי הקביעה מה בעיה "קטנה" יותר: מספר יעד קטן יותר, או סדרה קצרה יותר.

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

# Calculates whether it is possible to sum up to a number (t) from a subset
#	of the first few (i)  elements of an array (A).
# Takes an array (A), a whole number (t), and the number of first
#	elements (i).
# Returns True or False depending on whether there is a subset of the first i of T
#	summing to t.
Subset-Sum(A, t, i)
1	if t == 0
2		return True

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

# Calculates whether it is possible to sum up to a number (t) from a subset
#	of the first few (i)  elements of an array (A).
# Takes an array (A), a whole number (t), and the number of first
#	elements (i).
# Returns True or False depending on whether there is a subset of the first i of T
#	summing to t.
Subset-Sum(A, t, i)
1	if t == 0
2		return True
	
3	if i == 0
4		return False

כעת נניח שהפונקציה פותרת את הבעיות הקטנות יותר, ונפתור את הבעיה עבור $\displaystyle t$ ו$\displaystyle i$. נגדיר את האיבר ה$\displaystyle i$ כ$\displaystyle a_{i}$; יש לגביו שתי אפשרויות: או שלא משתמשים בו, או שכן. אם לא משתמשים בו, אז האפשרות היחידה להגיע ל$\displaystyle t$ היא אם אפשר להגיע ל$\displaystyle t$ בעזרת $\displaystyle i-1$ האיברים הראשונים (בעיה קטנה יותר במספר האיברים); אם כן משתמשים בו, אז האפשרות היחידה להגיע ל$\displaystyle t$ היא אם אפשר להגיע ל$\displaystyle t-a_{i}$ בעזרת $\displaystyle i-1$ האיברים הראשונים (בעיה קטנה יותר הן במספר האיברים והן במספר היעד). נקודד זאת:

# Calculates whether it is possible to sum up to a number (t) from a subset
#	of the first few (i)  elements of an array (A).
# Takes an array (A), a whole number (t), and the number of first
#	elements (i).
# Returns True or False depending on whether there is a subset of the first i of T
#	summing to t.
Subset-Sum(A, t, i)
1	if t == 0
2		return True
	
3	if i == 0
4		return False
	
5	if Subset-Sum(A, t, i - 1)
6		return True
	
7	if t >= A[i] and Subset-Sum(A, t - A[i], i - 1)
8		return True
	
9	return False

כדי לפתור את הבעיה המקורית, יש צורך לקרוא ל Subset-Sum(A, t, n).

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

משפט: נגדיר כ $\displaystyle s(t,i)$ את הערך המוחזר ע"י Subset-Sum(A, t, i). אז $\displaystyle s(t,i)$ נתון על ידי הנוסחה: $\displaystyle s(t,i)=$ True, אם $\displaystyle t=0$. False, אם $\displaystyle t\neq 0,i=0$. True, אם $\displaystyle i>0$ וכן או ש$\displaystyle s(t,i-1)$ הוא True או ש$\displaystyle s(t-a_{i},i-1)$ הוא True בנוסף, ל$\displaystyle s(t,i)$ יש ערך אמת אמ"ם אפשר להגיע ל$\displaystyle t$ בעזרת סכום תת-סדרה של $\displaystyle i$ המספרים הראשונים מA.

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

ההוכחה היא באינדוקציה כפולה על $\displaystyle i$ ו$\displaystyle t$.

(בסיס האינדוקציה) כאשר $\displaystyle t=0$ ברור שאפשר להגיע לסכום המתאים, מפני שאפשר לא לבחור אף איבר. כאשר $\displaystyle t\neq 0$ אך $\displaystyle i=0$, ברור שאי אפשר להגיע לסכום המתאים, כי אין אף איבר שאפשר לבחור.

(מעבר האינדוקציה) נניח שהטענה נכונה עד (לא כולל) זוג $\displaystyle (t,i)$ כלשהו. יש בדיוק שתי אפשרויות עבור האיבר ה$\displaystyle i$: או שלא משתמשים בו, או שכן. אם לא משתמשים בו, אז חייבים להגיע ל$\displaystyle t$ בעזרת $\displaystyle i-1$ המספרים הראשונים; מהנחת האינדוקציה, זהו בדיוק $\displaystyle s(t,i-1)$. אם כן משתמשים בו, אז חייבים להגיע ל$\displaystyle t-a_{i}$ בעזרת $\displaystyle i-1$ המספרים הראשונים; מהנחת האינדוקציה, זהו בדיוק $\displaystyle s(t-a_{i},i-1)$.

דג הסלמון

דג נולד בברכה הראשונה מתוך $\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.

הדפסת פרטי הפתרון - "שביל פירורים"

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

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

זו שיטה כללית בה נוכל להשתמש בכל בעיה. עם זאת, פרטי השיטה משתנים מעט מבעיה לבעיה. בפרט, נצטרך להחליט:

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

נראה כעת שתי דוגמות לשיטה זו.

הדפסת פרטי סכום תת-סדרה

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

נשים לב שכאן סוג ההחלטה שאנו מבצעים בכל קריאה רקורסיבית היא השאלה האם אנו משתמשים באיבר או לא. לכן, פשוט נוסיף עוד מטריצה $\displaystyle S$, המתארת עבור כל $\displaystyle t$ ו$\displaystyle i$ האם אנו משתמשים באיבר ה$\displaystyle i$ כדי לקבל סכום $\displaystyle t$.

# Calculates whether it is possible to sum up to a number (t) from a subset
#	of the first few (i)  elements of an array (A).
# Takes an array (A), a whole number (t), and the number of first
#	elements (i).
# Returns True or False depending on whether there is a subset of the first i of T
#	summing to t.
Subset-Sum(A, t, i)
1	if t == 0
2		return True
	
3	if i == 0
4		return False
	
5	if Subset-Sum(A, t, i - 1)
6		S[t][i] = False
7		return True
	
8	if t >= A[i] and Subset-Sum(A, t - A[i], i - 1)
9		S[t][i] = True
10		return True

11	S[t][i] = False
	
12	return False

נשים לב לשורות 6, ,9. אם הגענו לשורה 6, משמע שמצאנו פתרון שאינו משתמש באיבר ה$\displaystyle i$; שורה 6 רושמת זאת במטריצה. שני המקרים האחרים דומים.

והנה הפונקציה Print-Elements שתדפיס את האיברים:

# Prints the elements summing up to a given target.
Print-Elements(A, t, i)
1	if t == 0 or i == 0
2		return
		
3	if S[t][i] == False
4		Print-Elements(A, t, i - 1)
5		return

6	Print-Elements(A, t - A[i], i - 1)
7	Print( A[i] )

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

	# Run the algorithm, get whether it's possible to sum up.
1	can = Subset-Sum(A, t, Length(A))

	# If can sum up, print also the elements.
2	if can 
3		Print-Elements(A, t, Length(A))

כדאי לדעת: אפשר לשים לב ששורה 11 בSubset-Sum מיותרת. עם זאת, היא אינה מקלקלת דבר.

הדפסת פרטי דג הסלמון

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

נשים לב שכאן סוג ההחלטה שאנו מבצעים בכל קריאה רקורסיבית היא השאלה מהי הבריכה האחרונה ביותר שעצרנו לפני הבריכה הנוכחית. לכן, פשוט נוסיף עוד מערך 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 k == 1
2		S[k] = k
3		return Resting-Times[k]
		
4	min-time = ∞
	
5	for i in [1, ..., k - 1]
6		guess = Min-Time(i) + 2 * (1.5^(k - i) - 1) + Resting-Times[k]
					
7		if guess < min-time
8			S[k] = i
			
9	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) )

הפרק הקודם: מתמטיקה

חשיבה רקורסיבית

-

ֵ