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

תת-סידרה עולה ארוכה ביותר

שאלה

הגדרה: נתונה סידרה $\displaystyle X=[x_{1}...x_{n}]$ של מספרים שונים זה מזה. $\displaystyle Y=[y_{1}...y_{m}]$ היא תת-סידרה עולה של $\displaystyle X$ אם: קיימת סדרה עולה ממש של אינדקסים $\displaystyle [i_{1},...,i_{m}]$ כך ש$\displaystyle x_{i_{j}}=y_{j}$ לכל $\displaystyle j$. $\displaystyle Y$ היא סידרה עולה.

דוגמה: נניח ש$\displaystyle X=[1,5,2,3]$. אם נקבע $\displaystyle Z=[1,2,3]$, אז $\displaystyle Z$ היא תת-סידרה עולה של $\displaystyle X$. גם אם נקבע $\displaystyle Z=[2,3]$ תהיה $\displaystyle Z$ תת-סידרה עולה של $\displaystyle X$.

הגדרה: אם $\displaystyle X$ היא סידרה, אז $\displaystyle Y$ היא הLIS (או longest increasing subsequence), אם היא הארוכה ביותר מבין תתי-הסדרות העולות של $\displaystyle X$.

הנח שX הוא מערך גלובלי המתאר את הסדרה $\displaystyle X$, בעלת האורך $\displaystyle n$. בשאלה זו עליך למצוא אלגוריתם יעיל למציאת אורך הLIS.

תשובה

נשתמש במספר סימונים ומשפטים פשוטים:

1. נגדיר את הרישה ה$\displaystyle i$ של מחרוזת $\displaystyle X$ כ$\displaystyle X_{i}=x_{1},...,x_{i}$.‏
2. נגדיר כ$\displaystyle l(i)$ את אורך הLIS של $\displaystyle X_{i}$ שאיברה האחרון הוא $\displaystyle x_{i}$.
3. נשים לב ש:
   1. $\displaystyle \max _{1\leq i\leq n}[l(i)]$ הוא אורך הLIS של $\displaystyle X$.
   2. $\displaystyle l(i)$ מקיים את הנוסחה $\displaystyle l(i)=1+\max _{1\leq j<i,\;x_{j}\leq x_{i}}[l(j)]$.

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

אלה שלבי פעולות הפתרון:

1. נאתחל את כל אחד מאיברי L ל$\displaystyle \infty$.
2. נעבור בלולאה, משמאל לימין, על איברי X. כשנגיע לאיבר ה$\displaystyle i$:
   1. נחפש את האיבר הגדול ביותר ב בL[1], ..., L[i - 1] שאינו גדול מX[i].
   2. אם מצאנו איבר כזה בכניסה ה$\displaystyle j$ של L, נקבע L[j + 1] = X[i].
   3. אם לא, נקבע L[1] = X[i].
3. נמצא את האיבר הגדול ביותר בL שאינו $\displaystyle \infty$, ונחזיר את האינדקס שלו כתשובה המבוקשת.

דוגמה: נניח שX == [1, 5, 2, 3]. תחילה נאתחל את המערך L, כך שL == [∞, ∞, ∞, ∞]. כעת נעבור בלולאה על איברי X: כשi == 1,‏ אז X[i] == 1. בL אין שום איבר קטן מ1 בתחום $\displaystyle [1:0]$. נקבע, לכן, L[1] = 1. בשלב זה L = [1, ∞, ∞, ∞]. כשi == 2,‏ אז X[i] == 5. האיבר הגדול ביותר בL שאינו גדול מ5, הוא 1 באינדקס 1. נקבע, לכן, L[2] = 5. בשלב זה L = [1, 5, ∞, ∞]. כשi == 3,‏ אז X[i] == 2. האיבר הגדול ביותר בL שאינו גדול מ2, הוא 1 באינדקס 1. נקבע, לכן, L[2] = 2. בשלב זה L = [1, 2, ∞, ∞,]. כשi == 4,‏ אז X[i] == 3. האיבר הגדול ביותר בL שאינו גדול מ4, הוא 2 באינדקס 2. נקבע, לכן, L[3] = 3. בשלב זה L = [1, 2, 3, ∞].האיבר הגדול ביותר בL שאינו $\displaystyle \infty$, הוא 3. נחזיר, לכן, את האינדקס שלו - 3.

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

משפט: בסוף האיטרציה ה$\displaystyle i$ של הלולאה: L ממוין. אם האיבר ה$\displaystyle j$ בL אינו $\displaystyle \infty$, אז יש תת-סידרה עולה בX[1], ..., X[i] המסתיימת באיבר שערכו L[j].

להלן הפסוודו-קוד המתאים:

1	L = Make-Array(n)
	
2	for i in [1, ..., n]
3		L[i] = ∞

4	for i in [1, ..., n]
5		j = Smaller-Index(L, X[i])
6			L[j + 1] = X[i]

7	max = 0
8	for i in [1, ..., n]
9		if L[i] > max and L[i] < ∞
10			max = L[i]

הנה הסבר לפסוודו-קוד:

1. ב1-3 מאתחלים את L. קל לראות שהסיבוכיות לינארית.
2. ב4-6 מעדכנים את L על פי ההסבר שראינו למעלה. הפונקציה Smaller-Index, שמימושה אינו מופיע כאן, ניתנת למימוש בקלות באופן דומה למה שראינו ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] (שים לב שL ממוין). הסיבוכיות היא $\displaystyle \sum _{i=1}^{n}[O(\log(i))]=O(n\cdot \log(n))$.
3. ב7-10 מחפשים את המקסימום בL. קל לראות שהסיבוכיות לינארית.

תת-סידרה בדלנית מקסימאלית כפלית

שאלה

נתונה סידרה $\displaystyle X=[x_{1},...,x_{n}]$ של מספרים גדולים או שווים ל1. תת-סידרה $\displaystyle X'$ של X נקראת חברותית אם היא מכילה לפחות שני איברים עוקבים של X, ובדלנית אם היא איננה חברותית.

דוגמה: נניח ש$\displaystyle X=[1,5,2,7]$. אז: $\displaystyle X'=[1,5]$ היא תת-סידרה חברותית. $\displaystyle X'=[1,7]$ היא תת-סידרה בדלנית. $\displaystyle X'=[1,5,7]$ היא תת-סידרה חברותית. $\displaystyle X'=[1]$ היא תת-סידרה בדלנית. $\displaystyle X'=[]$ היא תת-סידרה בדלנית.

אנא כתוב אלגוריתם אשר מקבל סידרה $\displaystyle X$ ומדפיס תת-סידרה בדלנית שמכפלת איבריה גדולה ככל האפשר. (הנח שמכפלת איברי תת-סידרה ריקה היא 1.) קבע את Length(X) כ$\displaystyle n$, ונתח את סיבוכיות האלגוריתם במונחי $\displaystyle n$.

דוגמה: נניח שהאלגוריתם מקבל כקלט את $\displaystyle X=[1,5,2,7]$. במקרה זה, עליו להדפיס $\displaystyle [5,7]$: זו תת-סידרה בדלנית של $\displaystyle X$,‏ $\displaystyle 5\cdot 7=35$,‏ ואין תת-סידרה בדלנית אחרת שמכפלת איבריה גדולה מ35.

תשובה

המבנה הרקורסיבי

נגדיר כ$\displaystyle m(i)$ את המכפלה הגדולה ביותר האפשרית של תת-סידרה בדלנית של $\displaystyle [x_{1},...,x_{i}]$ (שים לב שתת-הסדרה אינה בהרכח משתמשת ב$\displaystyle x_{i}$).

משפט: $\displaystyle m(i)$ מקיימת את נוסחת הנסיגה הבאה: אם $\displaystyle i=1$, אז $\displaystyle m(i)=x_{1}$. אם $\displaystyle i=2$, אז $\displaystyle m(i)=\max\{x_{1},x_{2}\}$. אם $\displaystyle i>2$, אז $\displaystyle m(i)=\max\{m(i-1),m(i-2)\cdot x_{i}\}$.

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

1. אם $\displaystyle i=1$, אז בוודאי שנבחר באיבר הראשון (כל איבר הוא לפחות 1); נקבל בהכרח $\displaystyle x_{1}$.
2. אם $\displaystyle i=2$, אז בוודאי שנבחר באיבר הראשון או באיבר השני (כל איבר הוא לפחות 1); נקבל בהכרח $\displaystyle \max\{x_{1},x_{2}\}$.
3. אם $\displaystyle i>2$, אז או שנבחר ב$\displaystyle x_{i}$ או שלא (אלו שתי האפשרויות היחידות).
   • אם נבחר ב$\displaystyle x_{i}$, אז לא נוכל לבחור ב$\displaystyle x_{i-1}$; במקרה זה נרצה להכפיל את $\displaystyle x_{i}$ בתוצאה הטובה ביותר האפשרית עד $\displaystyle i-2$, שהיא $\displaystyle m(i-2)$.
   • אם לא נבחר את $\displaystyle x_{i}$, אז נרצה את תת-הסדרה הטובה ביותר עד $\displaystyle i-1$, שהיא, עפ"י ההגדרה, $\displaystyle m(i-1)$.

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

מימוש רקורסיבי נאיבי

להלן פסוודו-קוד המממש רעיון זה:

Max-Product(i)
1	if i == 1
2		return X[1]

3	if i == 2
4		return max(X[1], X[2])

6	guess-with = Max-Product(i - 2) * X[i]
7	guess-without = Max-Product(i - 1)
		
8	if guess-with > guess-without
9		return guess-with
10	else
11		return guess-without

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

שימוש בmemoization

להלן פסוודו-קוד יעיל יותר:

1	L = Make-Array(n)

2	for i in [1, ..., n]
3		L[i] = Nil


Max-Product(i)
1	if L[i] != Nil
2		return L[i]

3	if i == 1
4		L[1] = X[1]
5		return L[1]

6	if i == 2
7		L[2] = max(X[1], X[2])
8		return L[2]

9	guess-with = Max-Product(i - 2) * X[i]
10	guess-without = Max-Product(i - 1)
		
11	if guess-with > guess-without
12		L[i] = guess-with
12		return L[i]
13	else
14		L[i] = guess-without
15		return L[i]

הדפסת האיברים

להלן פסוודו-קוד המאפשר גם הדפסת תת-הסדרה:

1	L = Make-Array(n)
2	U = Make-Array(n)

3	for i in [1, ..., n]
4		L[i] = Nil


Max-Product(i)
1	if L[i] != Nil
2		return L[i]

3	if i == 1
4		L[1] = X[1]
5		U[1] = True
6		return L[1]

7	if i == 2
8		L[2] = max(X[1], X[2])
9		U[2] = X[2] == L[2]? True : False
10		return L[2]

11	guess-with = Max-Product(i - 2) * X[i]
12	guess-without = Max-Product(i - 1)
		
13	if guess-with > guess-without
14		L[i] = guess-with
15		U[i] = True
16		return L[i]
17	else
18		L[i] = guess-without
19		U[i] = False
20		return L[i]

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

Print-Seq(i)
1	if U[i] == True
2		Print-Seq(i - 2)
3		Print(i)
4		return
	
5	Print-Seq(i - 1)

כיצד נשתמש בקוד, אם כן?

1. נאתחל המשתנים הגלובליים, ונקרא לMax-Product(n).
2. נקרא לPrint-Seq(n).

ניתוח סיבוכיות

הסיבוכיות הכוללת הנה לינארית:

• מהתבוננות, ברור שהאתחול לינארי.
• הסיבוכיות של Max-Product(n) נתון על ידי $\displaystyle \sum _{i=1}^{n}[T'(i)]$, כאשר $\displaystyle T'(i)=O(1)$ הוא זמן הריצה של Max-Product(i) בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$ (ראו הניתוח בדג הסלמון).
• מהתבוננות, קל לראות שהדפסת האיברים היא $\displaystyle O(n)$.

חיתוך בד

שאלה

נתונה פיסת בד שמידותיה $\displaystyle (n,m)$ (כלומר ארכה $\displaystyle n$ מטר, ורחבה $\displaystyle m$ מטר). הנח ש$\displaystyle n$ ו$\displaystyle m$ מספרים שלמים.

נתונות $\displaystyle k$ מידות, $\displaystyle (n_{1},m_{1}),...,(n_{k},m_{k})$, שלהן מותאמים מחירים $\displaystyle p_{1},...,p_{k}$. כלומר:

1. חתיכת בד במידה $\displaystyle (n_{1},m_{1})$ שווה $\displaystyle p_{1}$ שקלים.
2. חתיכת בד במידה $\displaystyle (n_{2},m_{2})$ שווה $\displaystyle p_{2}$ שקלים.
3. ...
4. חתיכת בד במידה $\displaystyle (n_{k},m_{k})$ שווה $\displaystyle p_{k}$ שקלים.חוץ מ$\displaystyle k$ מידות אלה, כל המידות האחרות חסרות ביקוש, ולכן כל חתיכת בד במידה שונה

ממידות אלה שווה 0 שקלים. הנח שכל $\displaystyle n_{i}$ ו$\displaystyle m_{i}$ הוא מספר שלם חיובי ממש.

דוגמה: בתרשים הבא, A מראה פיסת בד במידות $\displaystyle (2,3)$, וB מראה שתי מידות בעלת ערך: העליונה בעלת המידות $\displaystyle (3,2)$, והתחתונה בעלת המידות $\displaystyle (1,2)$. נניח שהמידה העליונה שווה 35 שקל, והתחתונה שווה 2 שקלים. .

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

דוגמה: כיצד נוכל להשתמש בפיסת הבד מA שבדוגמה הקודמת? לו היינו יכולים לסובב אותה, היינו יכולים להפיק ממנה צורה ששווייה 35 שקל ללא גזירה אחת. עם זאת, עדיין יש סדרת גזירות שתפיק צורות בשווי 4 שקלים. בתרשים הבא: A מראה את החתך הראשון: נחתוך את הצורה אנכית בשורה 1, ונקבל את שתי הצורות בB. את הצורה העליונה בB נחתוך אנכית בטור הראשון, ונקבל את שלוש הצורות בC. את הצורה התחתונה בC נחתוך אנכית בטור 2, ונקבל את ארבע הצורות בD. כל אחת מהשורות בD מכילה כעת צורה אחת ששווייה 2 שקלים, ועוד צורה חסרת ערך. . יש עוד סדרות חיתוך שיניבו צורות בשווי 4 שקלים, אך אין סדרה שתניב יותר מכך.

בשאלה זו עליך למצוא אלגוריתם יעיל למציאת סדרת החיתוך הרווחית ביותר. אנא הוכח שהאלגוריתם שמצאת עובד בסיבוכיות $\displaystyle O(n\cdot m\cdot (n+m))$.

הנח שקיימת פונקציה Value(i, j) המחזירה בזמן $\displaystyle O(1)$:

1. 0 אם $\displaystyle (i,j)$ אינה אחת מ$\displaystyle k$ המידות בעלות התועלת.
2. $\displaystyle p_{k}$ אם $\displaystyle (i,j)=(n_{k},m_{k})$.

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

תשובה

המבנה הרקורסיבי

נגדיר כ$\displaystyle m(i,j)$ את מקסימום הרווח מפיסת בד במידות $\displaystyle (i,j)$.‏

משפט: $\displaystyle m(i,j)$ נתונה על ידי נוסחת הנסיגה הבאה: $\displaystyle m(i,j)=\max\{$ $\displaystyle \max _{1\leq i'<i}m(i',j)+m(i-i',j),$ $\displaystyle \max _{1\leq j'<j}m(i,j')+m(i,j'-j),$ $\displaystyle value(i,j)\}$ (כאשר $\displaystyle value(i,j)$ הוא הערך המוחזר מהפונקציה Value(i, j)).

כדאי לדעת: שים לב שהנוסחה הנ"ל כוללת בתוכה תנאי עצירה, מפני שעבור $\displaystyle i=j=1$, מה שכתוב כאן הינו פשוט $\displaystyle value(i,j)\}$. אפשר גם לכתוב את נוסחת הנסיגה בדרכים אחרות, ובחלקן גם יופיעו תנאי עצירה בצורה מפורשת יותר.

הוכחה: יש שלוש אפשרויות:

1. כדאי לחתוך את פיסת הבד אפקית באיזשהו $\displaystyle i'$ (כמתואר בתרשים הבא). נשים לב שאפשרות זו רלוונטית רק עבור עבור $\displaystyle i>1$.
2. כדאי לחתוך את פיסת הבד אנכית באיזשהו $\displaystyle j'$ (כמתואר בתרשים הבא אחריו). נשים לב שאפשרות זו רלוונטית רק עבור עבור $\displaystyle j>1$.
3. כלל לא משתלם לחתוך את פיסת הבד.

בתרשים הבא, לדוגמה, חיתוך אופקי של הצורה בA בשורה $\displaystyle i'$ ייצור שתי צורות מלבניות בB; לראשונה שבהן יהיו $\displaystyle i'$ שורות:

חיתוך אופקי.

בתרשים הבא, לדוגמה, חיתוך אנכי של הצורה בA בעמודה $\displaystyle j'$ ייצור שתי צורות מלבניות בB; לראשונה שבהן יהיו $\displaystyle j'$ עמודות:

חיתוך אנכי.

כעת נדון בכל אחת משלוש האפשרויות:

1. כדאי לחתוך את פיסת הבד אפקית באיזשהו $\displaystyle i'$. במקרה זה נקבל שתי חתיכות בד, האחת במידות $\displaystyle (i',j)$,‏ והשניה במידות $\displaystyle (i-i',j)$. עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא $\displaystyle m(i',j)$,‏ ועבור השניה $\displaystyle m(i-i',j)$.
2. כדאי לחתוך את פיסת הבד אנכית באיזשהו $\displaystyle j'$. במקרה זה נקבל שתי חתיכות בד, האחת במידות $\displaystyle (i,j')$,‏ והשניה במידות $\displaystyle (i,j-j')$. עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא $\displaystyle m(i,j')$,‏ ועבור השניה $\displaystyle m(i,j-j')$.
3. כלל לא משתלם לחתוך את פיסת הבד: הטוב ביותר האפשרי הוא Value(i, j).

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

מימוש רקורסיבי נאיבי

הפסוודו-קוד הבא מראה מימוש פשוט לנוסחה הנ"ל:

Max-Value(i, j)
1	max-value = 0

	# Check horizontal cuts.

	# This loop means the C-language loop for(i' = 1; i' < i; ++i')
2	for i' in [1, ..., i - 1]
3		guess = Max-Value(i', j) + Max-Value(i - i', j)		
4		if guess > max-value
5			max-value = guess
		
	# Check vertical cuts.

	# This loop means the C-language loop for(j' = 1; j' < j; ++j')
6	for j' in [1, ..., j - 1]
7		guess = Max-Value(i, j') + Max-Value(i, j - j')		
8		if guess > max-value
9			max-value = guess

	# Check the worth of this shape.

19	guess = Value(i, j)
	
11	if guess > max-value
12		max-value = guess

13	return max-value

שימוש בmemoization

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

1	M = Make-Matrix(m, n)

2	for i in [1, ..., m]
3		for j in [1, ..., n]
4			M[i][j] = Nil


Max-Value(i, j)
1	if M[i, j] != Nil
2		return M[i, j]

4	max-value = 0

	# Check horizontal cuts.

5	for i' in [1, ..., i - 1]
6		guess = Max-Value(i', j) + Max-Value(i - i', j)		
7		if guess > max-value
8			max-value = guess
		
	# Check vertical cuts.

9	for j' in [1, ..., j - 1]
10		guess = Max-Value(i, j') + Max-Value(i, j - j')		
11		if guess > max-value
12			max-value = guess

	# Check the worth of this shape.

13	guess = Value(i, j)
	
14	if guess > max-value
15		max-value = guess
		
16	M[i, j] = max-value

17	return max-value

הדפסת החלטות החיתוך

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

1	M = Make-Matrix(m, n)
2	C = Make-Matrix(n, n)

3	for i in [1, ..., m]
4		for j in [1, ..., n]
5			M[i][j] = Nil
6			C[i][j] = Nil


Max-Value(i, j)
1	if M[i, j] != Nil
2		return M[i, j]

3	max-value = 0

	# Check horizontal cuts.

4	for i' in [1, ..., i - 1]
5		guess = Max-Value(i', j) + Max-Value(i - i', j)		
6		if guess > max-value
7			max-value = guess
8			C[i][j] = ('Horizontal', i')
		
	# Check vertical cuts.

9	for j' in [1, ..., j - 1]
10		guess = Max-Value(i, j') + Max-Value(i, j - j')		
11		if guess > max-value
12			max-value = guess
13			C[i][j] = ('Vertical', j')

	# Check the worth of this shape.

14	guess = Value(i, j)
	
15	if guess > max-value
16		max-value = guess
17		C[i][j] = ('Shape', 0)
		
18	M[i, j] = max-value

19	return max-value

המטריצה C היא מטריצה של זוגות (בשפת C היינו ממשים זאת בעזרת מטריצה של מבנים):

1. האיבר הראשון בכל זוג הוא מחרוזת, המתארת איזו משלוש האפשרויות היא בחרנו.
2. האיבר השני בכל זוג הוא מספר המתאר היכן חתכנו.

הנה הקוד המדפיס את סדרת הפעולות:

Print-Cuts(i, j)
1	Print('For the best value of ' + i + ' and ' + j)

2	(type, index) = C[i][j]

3	if type == 'Horizontal'
4		Print 'Cut horizontally at ' + index
5		Print-Cuts(index, j)
6		Print-Cuts(i - index, j)
7	else if type == 'Vertical'
8		Print 'Cut vertically at ' + index
9		Print-Cuts(i, index)
10		Print-Cuts(i, j - index)
11	else
12		Print 'Use the shape itself'

ניתוח סיבוכיות

נגדיר כ$\displaystyle T'(i,j)$ את סיבוכיות Max-Cuts(i, j) בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$. קל מאד לראות מהקוד ש$\displaystyle T'(i,j)=\Theta (i+j)$. נשים לב גם ש$\displaystyle \Theta (i+j)=O(m+n)$, ולכן $\displaystyle T'(i,j)=O(m+n)$. סיבוכיות $\displaystyle Max-Cuts(m,n)$ חסומה מלמעלה על ידי $\displaystyle \sum _{i=1}^{m}\sum _{j=1}^{n}[T'(i,j)]=\sum _{i=1}^{m}\sum _{j=1}^{n}[O(m+n)]=O(m\cdot n\cdot (m+n))$.

גם כאשר לוקחים בחשבון את האתחול והדפסת הפרטים, הפתרון עדיין $\displaystyle O(m\cdot n\cdot (m+n))$.

תת-מחרוזת משותפת ארוכה ביותר

שאלה

הגדרה: מחרוזת היא רצף של תווים. אם $\displaystyle X=x_{1}\ldots x_{m}$,‏ $\displaystyle Y=y_{1}\ldots y_{n}$,‏ ו$\displaystyle Z=z_{1}\ldots z_{k}$ הן שלוש מחרוזות, אז: $\displaystyle Z$ היא תת-מחרוזת של $\displaystyle X$ אם קיימת סדרה עולה ממש של אינדקסים $\displaystyle i_{1},\ldots ,i_{k}$ כך ש$\displaystyle x_{i_{j}}=z_{j}$ לכל $\displaystyle j$. $\displaystyle Z$ היא תת-מחרוזת משותפת של $\displaystyle X$ ו$\displaystyle Y$ אם היא תת-מחרוזת הן של $\displaystyle X$ והן של $\displaystyle Y$

דוגמה: $\displaystyle Hello$ ו$\displaystyle ABCBDAB$ הן מחרוזות. אם $\displaystyle X=ABCBDAB$ ו$\displaystyle Y=BDCABA$, אז: אם נקבע $\displaystyle Z=BCBA$, אז $\displaystyle Z$ היא תת-מחרוזת של $\displaystyle X$. גם אם נקבע $\displaystyle Z=ABCBDAB$ (כלומר $\displaystyle X$ עצמה), אז $\displaystyle Z$ היא תת-מחרוזת של $\displaystyle X$. אם $\displaystyle X=ABCBDAB$ ו$\displaystyle Y=BDCABA$, אז $\displaystyle Z=BCBA$ היא תת-מחרוזת משותפת ל$\displaystyle X$ ול$\displaystyle Y$ (מבין כמה תתי-מחרוזות אפשריות).

הגדרה: אם $\displaystyle X$ ו$\displaystyle Y$ הן מחרוזות, אז $\displaystyle Z$ היא הLCS (או longest common subsequence), אם היא הארוכה ביותר מבין תתי-המחרוזות המשותפות ל$\displaystyle X$ ול$\displaystyle Y$.

בשאלה זו עליך למצוא אלגוריתם יעיל למציאת הLCS לכל שתי מחרוזות $\displaystyle X$ ו$\displaystyle Y$:

1. אנא תאר אלגוריתם יעיל המוצא את אורך הLCS.
2. אנא תאר אלגוריתם יעיל המדפיס את הLCS עצמו.

שימו לב: בכל אחד משני הסעיפים: הנח שX וY הם שני מערכים גלובליים המתארים את המחרוזות $\displaystyle X$ ו$\displaystyle Y$, בעלות האורכים $\displaystyle m$ ו$\displaystyle n$ בהתאמה. אנא הוכח נכונות תשובתך, ונתח את סיבוכיותה במונחי $\displaystyle m$ ו$\displaystyle n$.

תשובה

המבנה הרקורסיבי של הבעיה

ראשית מספר סימונים:

1. כפי שצוין בשאלה, נגדיר את אורך $\displaystyle X$ כ$\displaystyle m$, ואת אורך $\displaystyle Y$ כ$\displaystyle n$.
2. נסמן את הרישה ה$\displaystyle i$ של מחרוזת $\displaystyle X$ כ$\displaystyle X_{i}$. במילים אחרות, $\displaystyle X_{i}=x_{1},...,x_{i}$.‏
3. נגדיר כ$\displaystyle l(i,j)$ את אורך הLCS של $\displaystyle X_{i}$ ו$\displaystyle Y_{j}$. במילים אחרות, $\displaystyle l(i,j)$ היא אורך תת-הסדרה הארוכה ביותר המשותפת ל$\displaystyle X_{i}$ ו$\displaystyle Y_{j}$.

עכשיו תורכם: וודא שהמך מבין מדוע לפי הגדרה זו, $\displaystyle l(m,n)$ הוא אורך הLCS של $\displaystyle X$ ו$\displaystyle Y$.

משפט: $\displaystyle l(i,j)$ מקיים את הנוסחה הבאה: אם $\displaystyle i=0$ או $\displaystyle j=0$,‏ אז $\displaystyle l(i,j)=0$. אם לא,‏ אז: אם $\displaystyle x_{i}=y_{j}$, אז $\displaystyle l(i,j)=1+l(i-1,j-1)$. אם $\displaystyle x_{i}\neq y_{j}$, אז $\displaystyle l(i,j)=\max\{l(i-1,j),l(i,j-1)\}$.

הוכחה: אם $\displaystyle i=0$ או $\displaystyle j=0$, אז (לפחות) אחת המחרוזות היא המחרוזת הריקה, ורק המחרוזת הריקה יכולה להיות תת-מחרוזת של המחרוזת הריקה. למחרוזת הריקה יש אורך 0, ומכאן החלק הראשון של המשפט.

מכאן נניח ששתי המחרוזות אינן ריקות.

נניח ש$\displaystyle x_{i}=y_{j}$. ראשית, קל לראות שבהכרח תווה האחרון של $\displaystyle Z$ הוא $\displaystyle x_{i}$ - אם זה לא היה המצב, אז $\displaystyle Zx_{i}$ גם היא מחרוזת משותפת ל$\displaystyle X_{i}$ ו$\displaystyle Y_{j}$, דבר שנוגד עפ"י ההגדרה את היותה של $\displaystyle Z$ תת-המחרוזת המשותפת הארוכה ביותר. נחשוב כעת על כל תתי המחרוזות המשותפות מהצורה $\displaystyle Z'x_{i}$: עבור כל אחת מהן, קל לראות ש$\displaystyle Z'$ היא תת-מחרוזת משותפת ל$\displaystyle X_{i-1}$ ו$\displaystyle Y_{j-1}$, ולכן בהכרח הארוכה שבהן היא זו שהרישה שלה היא הLCS של $\displaystyle X_{i-1}$ ו$\displaystyle Y_{j-1}$.

לחלופין, נניח ש$\displaystyle x_{i}\neq y_{j}$; יש שלוש אפשרויות:

1. $\displaystyle Z$מסתיימת ב$\displaystyle x_{i}$ - אם כן, הLCS בהכרח מהצורה $\displaystyle Z'x_{i}$, כאשר $\displaystyle Z'$ היא הLCS של $\displaystyle X_{i}$ ו$\displaystyle Y_{j-1}$.
2. $\displaystyle Z$ מסתיימת ב$\displaystyle y_{j}$ - אם כן, הLCS בהכרח מהצורה $\displaystyle Z'y_{j}$, כאשר $\displaystyle Z'$ היא הLCS של $\displaystyle X_{i-1}$ ו$\displaystyle Y_{j}$.
3. $\displaystyle Z$אינה מסתיימת ב$\displaystyle x_{i}$, וכן אינה מסתיימת ב$\displaystyle y_{j}$ - אם זה המצב, אז הLCS של $\displaystyle X_{i-1}$ ו$\displaystyle Y_{j-1}$ הוא הLCS של $\displaystyle X_{i-1}$ ו$\displaystyle Y_{j}$ (וכן גם הLCS של $\displaystyle X_{i}$ ו$\displaystyle Y_{j-1}$), כך ששתי הבדיקות הקודמות מכסות כבר (פעמיים אפילו) מקרה זה.

מציאת אורך הLCS

להלן פסוודו-קוד למציאת אורך הLCS.

1	L = Make-Matrix(m, n)

2	for i in [1, ..., m]
3		for j in [1, ..., n]
4			L[i][j] = Nil

LCS-Length(i, j)
1	if L[i][j] == Nil
2		if i == 0 or j == 0
3			return 0
4		else if X[i] == Y[j]
5			L[i][j] = 1 + LCS-Length(i - 1, j - 1)
6		else
7			guess-x = LCS-Length(i - 1, j)
8			guess-y = LCS-Length(i, j - 1)
		
9			L[i][j] = Max(guess-x, guess-y)

10	return L[i][j]

ארבע השורות הראשונות מאתחלות מטריצה המשמשת לmemoization, והפונקציה LCS-Length מוצאת את את האורך המבוקש. 1-4 מייצרות מטריצה (גלובלית) שכל אחד מאיבריה מאותחל לNil.‏ 2-9 של LCS-Length, פועלות בדיוק לפי נוסחת הנסיגה הקודמת (שאת נכונותה כבר הראינו). המטריצה L, בפרט ב1 של LCS-Length, מטפלות במצב בו הפונקציה נקראת עם פרמטרים שאתם היא כבר נקראה בעבר.

ניתוח סיבוכיות

נגדיר את $\displaystyle T'(i,j)$ כזמן שאורכת LCS-Length בהנחה שכל אחת מקריאותיה הרקורסיביות היא $\displaystyle O(1)$. קל לראות ש$\displaystyle T'(i,j)=O(1)$.

זמן הריצה של LCS-Length(m, n) חסום מלמעלה על ידי $\displaystyle \sum _{i=0}^{m}\sum _{j=0}^{n}[T'(i,j)]=\Theta (m\cdot n)$. חוץ מכך ישנו האתחול 1-4 שאורך גם כן $\displaystyle \Theta (m\cdot n)$. הזמן הכולל, לכן, הוא $\displaystyle O(m\cdot n)$.

הדפסת איברי הLCS

ראשית נשנה מעט את הפסוודו-קוד הקודם.

1	L = Make-Matrix(m, n)
2	D = Make-Matrix(m, n)

3	for i in [1, ..., m]
4		for j in [1, ..., n]
5			L[i][j] = Nil


LCS-Length(i, j)
1	if L[i][j] == Nil
2		if i == 0 or j == 0
3			return 0
4		else if X[i] == Y[j]
5			L[i][j] = 1 + LCS-Length(i - 1, j - 1)
6			D[i][j] = 'b'
7		else
8			guess-x = LCS-Length(i - 1, j)
9			guess-y = LCS-Length(i, j - 1)
		
10			L[i][j] = Max(guess-x, guess-y)
	
11			if L[i][j] == guess-x
12				D[i][j] = 'x'
13			else
14				D[i][j] = 'y'	

15	return L[i][j]

המטריצה הגלובלית D מתארת בכניסה ה$\displaystyle (i,j)$ את ההחלטה לגבי הLCS של $\displaystyle X_{i}$ ו$\displaystyle Y_{j}$:

1. 'x' מסמלת את ההחלטה לוותר על התו האחרון ב$\displaystyle X_{i}$.
2. 'y' מסמלת את ההחלטה לוותר על התו האחרון ב$\displaystyle Y_{j}$.
3. 'b' מסמלת את ההחלטה לוותר על התו האחרון בשניהם. זה בדיוק המצב בו $\displaystyle X_{i}=Y_{j}$ נמצא כחלק מהLCS.הפונקציה הבאה מדפיסה את הLCS כאשר קוראים לPrint-LCS(m, n):

Print-LCS(i, j)
1	if i > 1 and j > 1
2		if D[i][j] == 'x':
3			Print-LCS(i - 1, j)
4		else if D[i][j] == 'y':
5			Print-LCS(i, j - 1)
6		else
7			Print-LCS(i - 1, j - 1)

1	if D[i][j] == 'b':
2		Print(X[i])

קל לראות שהסיבוכיות עדיין $\displaystyle \Theta (m\cdot n)$: השינויים בLCS-Length אינם משנים את סיבוכיותה; כל קריאה לPrint-LCS(i, j) מורידה (לפחות) את אחד הארגומנטים שלה ב1, ולכן היא יכולה להיקרא לכל היותר $\displaystyle m+n$ פעמים. הסיבוכיות, לכן, היא $\displaystyle \Theta (m\cdot n)$ + $\displaystyle O(m+n)$ = $\displaystyle \Theta (m\cdot n)$.

גשר זבלה

שאלה

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

דוגמה: נניח $\displaystyle m=3$ ו$\displaystyle k=100$ (ראה A בתרשים הבא). אפשר לשבור את הגשר ב4 אפנים: שוברים בנקודות 1 ו2. מתקבלים 3 חלקים בעלי אורך 1 כל אחד (ראה B בתרשים הבא). עלות השבירה היא $\displaystyle 2\cdot 100=200$. שוברים בנקודה 1. מתקבלים 2 חלקים: הראשון בעל אורך 1, והשני בעל אורך 2 (ראה C בתרשים הבא). עלות השבירה היא $\displaystyle 1\cdot 100=100$. שוברים בנקודה 2. מתקבלים 2 חלקים: הראשון בעל אורך 2, והשני בעל אורך 1 (ראה D בתרשים הבא). עלות השבירה היא $\displaystyle 1\cdot 100=100$. לא שוברים באף נקודה. מתקבל חלק יחיד בעל אורך 3. עלות השבירה היא $\displaystyle 0\cdot 100=0$. דוגמה לגשר הזבלה.

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

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

דוגמה: בהמשך לדוגמה הקודמת שראינו, נניח $\displaystyle f(1)=1$,‏ $\displaystyle f(2)=10$,‏ ו$\displaystyle f(3)=2$. ארבע האפשרויות שראינו מקודם יעלו כך: עלות ההובלה היא $\displaystyle f(1)+f(1)+f(1)=3$. עלות ההובלה היא $\displaystyle f(1)+f(2)=11$. עלות ההובלה היא $\displaystyle f(2)+f(1)=11$. עלות ההובלה היא $\displaystyle f(3)=2$.

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

תשובה

המבנה הרקורסיבי

נגדיר כ$\displaystyle m(i)$ את העלות הזולה ביותר לטיפול בקטע באורך $\displaystyle i$.

משפט: $\displaystyle m(i)$ נתונה על ידי נוסחת הנסיגה הבאה: אם $\displaystyle i=1$,‏ אז $\displaystyle f(1)$. אם $\displaystyle i>1$,‏ אז $\displaystyle \min \left\{f(i),\min _{1\leq j<i}\left\{m(j)+k+m(i-j)\right\}\right\}$.

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

1. אם $\displaystyle i=1$,‏ אז אין מה לחתוך; ההובלה תעלה $\displaystyle f(1)$.
2. אם $\displaystyle i>1$,‏ אז או שלא חותכים את הקטע, או שכן. אם לא חותכים, עלות השבירה 0, ועלות ההובלה $\displaystyle f(i)$. אם חותכים בנקודה $\displaystyle j$, אז עלות הטיפול בחלק השמאלי תהיה , עפ"י ההגדרה, $\displaystyle m(j)$,‏ עלות השבירה היא כמובן $\displaystyle k$,‏ ועלות הטיפול בחלק הימני תהיה, עפ"י ההגדרה, $\displaystyle m(i-j)$. נותר לקחת מינימום על פני $\displaystyle j$, ולהחליט האם לחתוך או לא.

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

מימוש נאיבי

להלן פסוודו-קוד המממש את נוסחת הנסיגה.

Min-Cost(i)
1	if i == 1
2		return F(1)
	
3	guess-without = F(i)

4	guess-with = ∞
5	for j in [1, …, i - 1]
6		if guess-with> Min-Cost(j) + k + Min-Cost(i - j)
7			guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
		
8	if guess-with < guess-without
9		return guess-with
10	else
11		return guess-without

שימוש בmemoization

נוסיף memoization.

Min-Cost(i)
1	if M[i] != Nil
2		return M[i]

1	if i == 1
2		M[1] = F(1)
3		return F(1)
	
4	guess-without = F(i)

5	guess-with = ∞
6	for j in [1, … i - 1]]
7		if guess-with> Min-Cost(j) + k + Min-Cost(i - j)
8			guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
		
9	if guess-with M[i] < guess-without
10		M[i] = guess-with
11		return guess-with
12	else
13		M[i] = guess-without
14		return guess-without

(נניח שהמערך הגלובלי Mבאורך nמאותחל תחילה כולו לNil.)

הדפסת נקודות השבירה

נוסיף גם מספיק מידע לצורך הדפסת פרטי הפתרון.

Min-Cost(i)
1	if M[i] != Nil
2		return M[i]

1	if i == 1
2		M[1] = F(1)
3		Break[1] = Nil
4		return F(1)
	
5	guess-without = F(i)

6	guess-with = ∞
7	for j in [1, … i - 1]]
8		if guess-with> Min-Cost(j) + k + Min-Cost(i - j)
9			guess-with = Min-Cost(j) + k + Min-Cost(i - j)		
10			if guess-with 
11				Break[i] = j
				
12	if guess-with 
13		M[i] = guess-with
14		return guess-with
15	else
16		M[i] = guess-without	
17		return guess-without

המערך הגלובלי Break מכיל את ההחלטה שעשינו לגבי כל קטע. Break[i]הוא Nilאם החלטנו לא לחלק את הקטע, והוא $\displaystyle j$אם החלטנו לשבור בנקודה j.

כעת נדפיס את העצירות, ע"י קריאה לPrint-Breaks(n, 0). הפונקציה מוגדרת להלן.

Print-Breaks(i, start)
1	if Break[i] == Nil
2		return
	
3	j = Break[i]
	
4	Print(j + start)

5	Print-Nums(j, start)
6	Print-Nums(i - j, start + j)

הפונקציה מקבלת שני ארגומנטים: אורך הקטע, i,‏ ותחילת הקטע, start.‏ נניח שהפונקציה נקראה עבור שני ערכים ספיציפיים כאלה. אם Break[i] == Nil, אז לא חתכנו את הקטע, ואין מה להדפיס. אם לא, וBreak[i] == j, אז יש להדפיס את הנקודה j(תוך זכירה שאנו נמצאים startמתחילת כל הגשר), את החלק השמאלי, ואת החלק הימני.

ניתוח סיבוכיות

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

גם כאשר לוקחים בחשבון את האתחול והדפסת הפרטים, הפתרון עדיין $\displaystyle O(n^{2})$.

זמן הריצה של הכפלת שרשרת מטריצות תחת Memoization

שאלה

אנא וודא את הנוסחות הבאות בזמן הריצה של הכפלת שרשרת מטריצות תחת memoization:

1. $\displaystyle T'(i,j)=\Theta (j-i+1)$ (נזכר ש$\displaystyle T'(i,j)$ מוגדרת כזמן שאורכת Min-Time(i, j) בהנחה שכ"א מהקריאות הרקורסיביות היא $\displaystyle O(1)$).
2. $\displaystyle T(1,n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[T'(i,j)]$.
3. $\displaystyle T(1,n)=\Theta (n^{3})$.

תשובה

א'

נתבונן בפסוודו-קוד עם memoization:

Min-Time(i, j)
1	if M[i][j] != Nil
2		return M[i][j]

3	if i == j
4		M[i][j] = 0
5		return 0
	
6	min-time = ∞
	
7	for k in [i, ..., j - 1]
8		guess = Min-Time(i, k) + Min-Time(k + 1, j) + PQR(i, k, j)
	
9		if guess M[i][j] < min-time
10			M[i][j] = min-time = guess
				
11	return min-time

נשים לב שאם נניח שכל קריאה רקורסיבית אורכת $\displaystyle O(1)$, אז יש לנו מספר קריאות שכ"א היא $\displaystyle O(1)$ (1-6, 11), ולולאה בת $\displaystyle j-i$ איטרציות, כאשר כל איטרציה היא $\displaystyle O(1)$. זמן הריצה, לכן הוא $\displaystyle T'(i,j)=O(1)+(j-i)\cdot O(1)=\Theta (j-i+1)$.

ב'

ההוכחה חוזרת, למעשה, על זו של דג הסלמון.

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

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

הציור אינו מראה את כל צמתי הקריאה מטעמי נוחות. הצומת $\displaystyle 1,n$ קורא לצומת $\displaystyle 1,1$, בעקיפין לצמתים $\displaystyle 2,2$ ו$\displaystyle 23,36$, ולעוד צמתים. הקווים המקווקווים מציינים שהקריאות אינן בהכרח ישירות.

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

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

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

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

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

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

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

עץ הקריאות הרקורסיביות - שלב 1.

נחזור על אותה הפעולה עבור הצומת $\displaystyle 2,2$.

עץ הקריאות הרקורסיביות - שלב 2.

כנ"ל לגבי הצומת $\displaystyle 23,23$.

עץ הקריאות הרקורסיביות - שלב 3.

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

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

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

קל להשתכנע שבשלב בו נחליף את צומת הראש בצומת לא מודגש, רשמנו בצד את כל האיברים מהצורה $\displaystyle T'(i,j)$, כאשר $\displaystyle 1\leq i\leq n$ ו$\displaystyle j\leq i\leq n$. בצורה אחרת, מה שרשום בצד הוא $\displaystyle \sum _{i=1}^{n}\sum _{j=i}^{n}[T'(i,j)]$.

ג'

נשלב את שני הסעיפים הקודמים: $\displaystyle T(1,n)=\sum _{i=1}^{n}\sum _{j=i}^{n}[T'(i,j)]=\sum _{i=1}^{n}\sum _{j=i}^{n}[\Theta (j-i+1)]$.

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

נוסע מתמיד ביטוני אויקלידי

שאלה

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

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

שאלה זו דנה בגרסה קלה יותר של הבעיה.

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

דוגמה: בתרשים הבא, A מראה מישור בעל $\displaystyle n=7$ נקודות; B מראה את המסלול הקצר ביותר, אך המסלול אינו ביטוני. מישור ומסלולים. בתרשים הבא, A וB מראים כל אחד מסלול ביטוני אפשרי. מסלולים ביטוניים.

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

שימו לב: #הנח שP הוא מערך גלובלי בעל אורך $\displaystyle n$ המתאר את הנקודות. כדי לגשת לקואורדינטות הX והY של הנקודה ה$\displaystyle i$, השתמש בP[i].x ובP[i].y, בהתאמה. הנח שP ממוין בסדר עולה על פי קואורדינטות הX של נקודותיו (ולכן P[1] היא בהכרח נקודת המוצא של הנוסע, לדוגמה). אנא נתח סיבוכיות תשובתך במונחי $\displaystyle n$.

תשובה

מספר סימונים ואבחנה פשוטה

ראשית מספר סימונים:

1. כפי שצוין בשאלה, נגדיר את אורך $\displaystyle P$ כ$\displaystyle n$.
2. נסמן את הנקודות שבמערך כ$\displaystyle p_{1}=(x_{1},y_{1}),p_{2}=(x_{2},y_{2}),...,p_{n}=(x_{n},y_{n})$. כאמור, אנו מניחים שהנקודות כבר ממוינות כך ש$\displaystyle x_{1}\leq x_{2}\leq ...\leq x_{n}$.
3. נסמן את המרחק בין שתי נקודות $\displaystyle p=(x,y)$ ו$\displaystyle p'=(x',y')$ כ$\displaystyle d(x,y)={\sqrt {(x-x')^{2}+(y-y')^{2}}}$.
4. נאמר ששני מסלולים שקולים אם אחד מתקבל מהשני ע"י החלפת כווני החיצים.

דוגמה: בתרשים הבא, A וB מראים מסלולים שקולים. שני מסלולים שקולים.

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

משפט: אם שני מסלולים שקולים, אז מחירם זהה.

בעיה דומה לא-מעגלית

נגדיר את $\displaystyle m(i,j)$ ‏($\displaystyle 1\leq j<i\leq n$)‏ כעלות המסלול הזול ביותר שמקיים את התנאים הבאים:

1. המסלול מתחיל ב$\displaystyle p_{i}$ וממשיך כלפי שמאל עד ל$\displaystyle p_{1}$.
2. כשהמסלול מגיע (מכוון ימין) ל$\displaystyle p_{1}$, הוא מסתובב ימינה, וממשיך עד ל$\displaystyle p_{j}$‏‏ שם הוא מסתיים.
3. המסלול עובר דרך כל אחד מהנקודות $\displaystyle p_{1},p_{2},...,p_{i}$ בדיוק פעם אחת.

שימו לב: המסלול שעליו דיברנו זה עתה אינו מעגלי. הוא מתחיל ב$\displaystyle p_{i}$, ומסתיים ב$\displaystyle p_{j}\neq p_{i}$.

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

הקשר לבעיה המקורית (המעגלית)

משפט: מחיר המסלול הביטוני הזול ביותר הוא $\displaystyle min_{1\leq j<n}[m(n,j)+d(p_{j},p_{n})]$.

הוכחה: במסלול המעגלי הקצר ביותר, נסמן כ$\displaystyle p_{j}$ את הנקודה הימנית ביותר לפני $\displaystyle p_{n}$ שנמצאת בחלק המסלול לכוון ימין (ראה התרשים הבא). המסלול, לכן, מורכב משלושה חלקים:

1. מ$\displaystyle p_{1}$ ימינה ל$\displaystyle p_{j}$
2. מ$\displaystyle p_{j}$ ימינה ישירות ל$\displaystyle p_{n}$
3. מ$\displaystyle p_{n}$ שמאלה חזרה ל$\displaystyle p_{1}$

עלות הקטע 2 היא בדיוק $\displaystyle d(p_{j},p_{n})$. סכום עלויות הקטע 1 ו3 הוא בדיוק $\displaystyle m(n,j)$.

הקשר בין m(i,j) למסלול המעגלי הזול ביותר.

נוסחת נסיגה לבעיה הלא-מעגלית

משפט: $\displaystyle m(i,j)$ נתון על ידי נוסחת הנסיגה הבאה: $\displaystyle m(i,1)=\sum _{k=1}^{i-1}[d(k,k+1)]$, לכל $\displaystyle i\geq 1$. $\displaystyle m(i,i-1)=min_{1\leq k<i-1}[m(i-1,k)+d(k,i)]$, לכל $\displaystyle i>1$. $\displaystyle m(i,j)=m(i-1,j)+d(i-1,i)$, לכל $\displaystyle i>1,j<i-1$.

הוכחה: נשקול את כל המקרים האפשריים:

1. $\displaystyle m(i,1)$ הוא אורך המסלול הזול ביותר שעובר שמאלה מ$\displaystyle p_{i}$ ל$\displaystyle p_{1}$, מ$\displaystyle p_{1}$ פונה ימינה, אינו מגיע לאף נקודה אחרת מכוון ימין, ומכסה את כל הנקודות משמאלה ל$\displaystyle p_{i}$. לכן, בהכרח, מדובר במסלול שעובר נקודה אחרי נקודה מ$\displaystyle p_{i}$ ל$\displaystyle p_{1}$.
2. $\displaystyle m(i,i-1)$ הוא אורך המסלול הזול ביותר שעובר שמאלה מ$\displaystyle p_{i}$ ל$\displaystyle p_{1}$, מ$\displaystyle p_{1}$ ימינה ל$\displaystyle p_{i-1}$, ומכסה את כל הנקודות משמאלה ל$\displaystyle p_{i}$. נסמן כ$\displaystyle p_{k}$ את הנקודה שאליה עובר המסלול ישירות מ$\displaystyle p_{i}$; A בתרשים הבא מציג זאת.

   

   מקרה 2 בהוכחת נוסחת הנסיגה.

   היות שהוכחנו למעלה שלמסלולים שקולים יש מחיר זהה, נוכל לטעון שB בתרשים הקודם בעל אותו מחיר כA.
3. $\displaystyle m(i,j)$ הוא אורך המסלול הזול ביותר שעובר שמאלה מ$\displaystyle p_{i}$ ל$\displaystyle p_{1}$, מ$\displaystyle p_{1}$ ימינה ל$\displaystyle p_{j}$, ומכסה את כל הנקודות משמאלה ל$\displaystyle p_{i}$. היות ש$\displaystyle j<i-1$, המסלול חייב להתחיל במעבר ישיר (שמאלה) מ$\displaystyle p_{i}$ ל$\displaystyle p_{i-1}$.

   

   מקרה 3 בהוכחת נוסחת הנסיגה.

פסוודו-קוד

להלן פסוודו-קוד המשתמש ברעיון זה:

IJ-Length(i, j)
1	if j == 1
2		ij-length = 0
		
3		for k in [1, ..., i - 1]
4			ij-length = ij-length + D(k, k + 1)
5	else if j == i - 1
6		ij-length = ∞

7		for k in [1, ..., i - 2]
8			guess = IJ-Length(i - 1, k) + D(k, i)
9			if ij-length > guess
10				ij-length = guess
11	else
12		ij-length = IJ-Length(i - 1, j) + D(i - 1, i)

13	return ij-length


Min-Bitonic-Euclidean()
1	if n == 1
2		return 0

3	min = ∞

4	for j in [1, ..., n - 1]
5		guess = IJ-Length(n, j) + D(j, n)
6		if min < guess
7			min = guess

8	return min


D(P, P')
1	return √((P'.x - P.x)^2 + (P'.y - P.y)^2)

להלן הסבר לפסוודו-קוד.

1. IJ-Length(i, j) מממש את נוסחת הנסיגה שראינו מקודם לבעיה הלא-מעגלית.
2. Min-Bitonic-Euclidean() מוצא את הנקודה $\displaystyle j$ הימנית ביותר כפי שראינו מקודם בקשר בין הבעיה המעגלית והבעיה הלא-מעגלית.
3. D(P, P') היא פונקציית עזר המוצאת את המרחק בין שתי נקודות.

תזכור (Memoization)

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

1	M = Make-Matrix(n, n)

2	for i in [1, ..., n]
3		for j in [1, ..., n]
4			M[i][j] = Nil


IJ-Length(i, j)
1	if M[i][j] == Nil
2		if j == 1
3			M[i][j] = 0
		
4			for k in [1, ..., i - 1]
5				M[i][j] = M[i][j] + D(k, k + 1)
6		else if j == i - 1
7			M[i][j] = ∞

8			for k in [1, ..., i - 2]
9				guess = IJ-Length(i - 1, k) + D(k, i)
10				if M[i][j] > guess
11					M[i][j] = guess
12		else
13			M[i][j] = IJ-Length(i - 1, j) + D(i - 1, i)

14	return M[i][j]

ניתוח סיבוכיות

הסיבוכיות היא $\displaystyle \Theta (n^{2})$:

1. איתחול המטריצה הוא $\displaystyle \Theta (n^{2})$.
2. נסמן כ $\displaystyle T'(i,j)$ את זמן הריצה של IJ-Length(i, j),‏ ‏ בהנחה שכל אחת מהקריאות הרקורסיביות היא $\displaystyle O(1)$. אפשר לראות ש$\displaystyle T'(i,j)=O(1)$,‏ כל עוד $\displaystyle j\neq 1,i-1$, ואחרת $\displaystyle T'(i,j)=\Theta (i)$. קל לראות שסך כל ריצת הפונקציה הוא

$\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{i-1}[T'(i,j)]=\sum _{i=1}^{n}\sum _{j=1}^{i-2}[T'(i,j)]+\sum _{i=1}^{n}[T'(i,i-1)]=\sum _{i=1}^{n}\sum _{j=1}^{i-2}[O(1)]+\sum _{i=1}^{n}[\Theta (i)]=\Theta (n^{2})$.

רשת חומוסיות

שאלה

רשת החומוסיות מק-לאפה מתכננת להקים סניפים רבים לאורך רחוב איבן-גבירול בתל אביב. $\displaystyle m_{1},m_{2},\ldots m_{n}$ מציינים את מספרי הבתים ברחוב בהם יש מקום פנוי להקמת סניף חדש. הרשת שוקלת היכן להקים את הסניפים החדשים:

1. מסקר שוק, הרשת מעריכה שבבית מספר $\displaystyle m_{i}$ רווחיה הצפויים יהיו $\displaystyle p_{i}$ ‏($\displaystyle p_{i}$ הוא מספר חיובי כלשהו).
2. הרשת אינה מוכנה להקים שני סניפים שמרחקם זה מזה הוא פחות מ$\displaystyle k$‏ ($\displaystyle k$ הוא מספר שלם חיובי כלשהו).

דוגמה: אם $\displaystyle k=20$ והרשת בוחרת להקים סניף בבית מספר 135, אסור לה להקים סניף בבית מספר 143, שכן $\displaystyle 143-135<20$.

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

תשובה

ראשית נניח שהמערך Mממויין, או, לחלופין, נמיין אותו בעזרת מיון מיזוג בסיבוכיות $\displaystyle \Theta (n\cdot \log(n))$.

נגדיר כ$\displaystyle mp(i)$ את מירב הרווח שאפשר להרוויח מפתיחת סניפים הלקוחים מתוך $\displaystyle i$הבתים הראשונים.

משפט: לפי הגדרת $\displaystyle mp(i)$: הפתרון הטוב ביותר הוא בעל רווח $\displaystyle mp(n)$. הפונקציה נתונה על ידי נוסחת הנסיגה: $\displaystyle mp(1)=p_{1}$ לכל $\displaystyle i>1$,‏ $\displaystyle mp(i)=\max \left\{p_{i}+\max _{j|m_{i}-m_{j}>k}mp(j),mp(i-1)\right\}$ $\displaystyle mp(i)$ מונוטונית לא-יורדת ב$\displaystyle i$.

הוכחה: (2) אם $\displaystyle i=1$, אז ברור שהפתרון הרווחי ביותר הוא זה שבו בוחרים את הבית הראשון (והיחידי האפשרי לבחירה). אם $\displaystyle i>1$, אז או שבוחרים את בית $\displaystyle i$, או שלא. במקרה הראשון, מרוויחים $\displaystyle p_{i}$ מהבחירה בבית, אך לפניו אסור לבחור באף בית בעל מיקום שהפרשו מ$\displaystyle m_{i}$קטן מ$\displaystyle k$. במקרה השני, הרווח הוא בדיוק הרווח כשמותר לבחור מבין $\displaystyle i-1$הבתים הראשונים.

להלן פסוודו-קוד המממש נוסחה זו.

Max-Profit(M, P, k, i)
1	if i == 0
2		return 0
		
3	if i == 1
4		return P[1]
		
5	guess-without = Max-Profit(i - 1)
6	guess-with = P[i]
		
7	if m[i] > k
8		j = Find-Index(M, M[i] - k)
9		guess-with = guess-with + Max-Profit(M, P, k, j)
			
10	if guess-with > guess-without
11		return guess-with
12	else
13		return guess-without

חשוב רק לשים לב לקריאה לפונקציה Find-Index ב8. פונקציה זו מוצאת את האינדקס הגדול ביותר בMשקטן מM[i] - k. היות שMממויין, נוכל לעשות זאת על ידי שינוי קטן בחיפוש בינרי. נוסיף גם Memoization:

1	MP = Make-Array(n)
	
2	for i in [1, ..., n]
3		MP[i] = Nil


Max-Profit(M, P, k, i)
1	if i == 0
2		return 0
		
3	if MP[i] != Nil
4		return MP[i]
		
5	if i == 1
6		MP[1] = P[1]
7		return P[1]
		
8		guess-without = Max-Profit(i - 1)
9		guess-with = P[i]
		
10	if m[i] > k
11		j = Find-Index(M, M[i] - k)
12		guess-with = guess-with + Max-Profit(M, P, k, j)
			
13	if guess-with > guess-without
14		MP[i] = guess-with
15		return guess-with
16	else
17		MP[i] = guess-without
18		return guess-without

כעת נוסיף גם את הדפסת האיברים:

1	MP = Make-Array(n)
2	Used = Make-Array(n)
	
3	for i in [1, ..., n]
4		MP[i] = Nil


Max-Profit(M, P, k, i)
1	if i == 0
2		return 0
		
3	if MP[i] != Nil		
4		return MP[i]
		
5	if i == 1
6		MP[1] = P[1]
7		Used[1] = True
8		return P[1]
		
9		guess-without = Max-Profit(i - 1)
10		guess-with = P[i]
		
11	if m[i] > k
12		j = Find-Index(M, M[i] - k)
13		guess-with = guess-with + Max-Profit(M, P, k, j)
			
14	if guess-with > guess-without
15		MP[i] = guess-with
16		Used[i] = True
17		return guess-with
18	else
19		MP[i] = guess-without
20		Used[i] = False
21		return guess-without

המערך Used מתאר האם השתמשנו באיבר ה$\displaystyle i$או לא. נשתמש בו ע"י קריאה לPrint-Nums(k, n), כאשר Print-Nums מוגדרת כך:

Print-Nums(k, i)
1	if i &lt 1
2		return
		
3	if Used[i]
4		j = Find-Index(M, M[i] - k)
5		Print-Nums(k, j)
6	else
7		Print-Nums(k, i - 1)
			
8	if Used[i]
9		Print(i)

נותר רק לנתח את הסיבוכיות.

השורה j ← Find-Index(M, M[i] - k)אורכת $\displaystyle O(\log(n))$. אם נגדיר כ$\displaystyle T'(i)$ את זמן הקריאה לMax-Profit(M, P, k, i)בהנחה שכל קריאה רקורסיבית היא $\displaystyle O(1)$, אז $\displaystyle T'(i)=O(\log(n))$, והסיבוכיות היא $\displaystyle O(n\cdot \log(n))$. מצד שני, מיון המערך הוא $\displaystyle \Omega (n\cdot \log(n))$, ולכן נקבל $\displaystyle \Theta (n\cdot \log(n))$.

תכנון פרוייקטים

שאלה

בבעיית "תכנון הפרוייקטים" יש $\displaystyle k$ פרוייקטים ו$\displaystyle n$ עובדות. צריך להחליט כמה עובדות יש להקצות לכל אחד מהפרוייקטים.

לכל פרוייקט $\displaystyle 1\leq i\leq k$ ומספר עובדות $\displaystyle 1\leq j\leq n$, ‏ $\displaystyle q(i,j)$ הוא מספר המייצג את איכות ביצוע הפרוייקט ה$\displaystyle$i אם ישבצו לו $\displaystyle j$ עובדות. הנח:

1. $\displaystyle q(i,j)$ פונקציה לא שלילית (אין איכות שלילית).
2. $\displaystyle q(i,j)$ מונוטונית לא-יורדת ב$\displaystyle j$ (הוספת עובדות לפרוייקט אינה מורידה מאיכותו).
3. ניתן להקצות 0 עובדות לפרוייקט.
4. כל עובדת מוקצת לפרוייקט אחד בדיוק.

לכל פרוייקט $\displaystyle i$ יש "חשיבות" לא-שלילית $\displaystyle h(i)$. אנו רוצים למקסם את סך האיכויות המשוקללות. במילים אחרות, אנו רוצים למקסם את $\displaystyle \max _{i_{1},i2,\ldots ,i_{n}:i_{1}\geq 0,\ldots ,i_{n}\geq 0,i_{1}+\cdots +i_{n}=n}\sum \left[h(i)q(i,j)\right]$.

אנא הצע אלגוריתם יעיל לפתרון הבעיה, כלומר אלגוריתם שימצא את הסכום הנ"ל המקסימלי וכן ידפיס את אופן הקצאת העובדות לכל פרוייקט. הנח שq(i, j) וh(i) הן פונקציות נתונות לך, שעלות קריאה להן היא $\displaystyle O(1)$.

המבנה הרקורסיבי

נגדיר את $\displaystyle m(i,j)$ כאיכות המשוקללת הגבוהה ביותר האפשרית כאשר יש $\displaystyle j$ עובדות ו$\displaystyle i$ פרוייקטים.

משפט: $\displaystyle m(i,j)$ = $\displaystyle h(1)q(1,j)$, אם $\displaystyle i=1$. $\displaystyle \max _{j'\;|0\leq j'\leq j}\left[h(i)q(i,j')+m(i-1,j-j')\right]$, אם $\displaystyle i>1$.

הוכחה: אם יש פרוייקט יחיד, אז ברור שכדאי להקצות את כל העובדות לו (שהרי נתון שהוספת עובדות אינה יכולה להוריד את איכות הפרוייקט). לכן, אם יש פרוייקט יחיד ו$\displaystyle j$ עובדות, נקבל שאיכותו הטובה ביותר היא $\displaystyle q(1,j)$.

נניח שיש $\displaystyle i>1$ פרוייקטים. אם נקצה $\displaystyle j'$ עובדות לפרוייקט ה$\displaystyle i$, אז איכות הפרוייקט תהיה $\displaystyle q(i,j')$, ונוותר עם $\displaystyle j-j'$ עובדות. על פי הגדרתנו, $\displaystyle m(i-1,j-j')$ הוא הטוב ביותר שנוכל להשיג במקרה זה.

פסוודו-קוד

נתרגם את נוסחת הנסיגה הקודמת לפסוודו-קוד.

Max-Value(i, j)
1	if i == 1
2		return h(1) q(1, j)

3	max-value = 0
4	for j' in [0, ..., j]
5		guess = Max-Value(i - 1, j - j') + h(i) q(i, j')
6		if guess > max-value
7			max-value = guess

8	return max-value

הדפסת פרטי הפתרון

נוסיף עוד מטריצה גלובלית A כך שA[i][j] מתארת את מספר העובדות האופטימלי שכדאי להקצות לפרוייקט ה$\displaystyle i$ אם יש $\displaystyle i$ פרוייקטים ו$\displaystyle j$ עובדות.

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

Max-Value(i, j)
1	if i == 1
2		A[1][j] = j
3		return h(1) q(1, j)

4	max-value = 0
5	for j' in [0, ..., j]
6		guess = Max-Value(i - 1, j - j') + h(i) q(i, j')
7		if guess > max-value
8			A[i][j] = j'
9			max-value = guess

10	return max-value

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

Print-Assignments(i, j)
1	if i == 0
2		return

	# The optimal assignment assigns j' workers to project i.
3	j' = A[i][j] 

4	Print('Assign ' + j' + ' workers to project ' + i)

5 	Print-Assignments(i - 1, j - j')

כך נפעיל את שתי הפונקציות:

1	A = Make-Matrix(k, n)

2	max-value = Max-Value(k, n)

3	Print(max-value)

4	Print-Assignments(k, n)

הוספת תזכור (memoization)

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

Max-Value(i, j)
1	if i == 1
2		M[1][j] = h(1) q(1, j)
3		return h(1) q(1, j)

4	max-value = 0
5	for j' in [0, ..., j]
6		guess = Max-Value(i - 1, j - j') + h(i) q(i, j')
7		if guess > max-value
8			M[i][j] = guess
9			max-value = guess

10	return max-value

ניתוח סיבוכיות

כרגיל, נגדיר את $\displaystyle T'(i,j)$ כזמן הריצה של Max-Value(i, j) כאשר כל קריאה רקורסיבית היא $\displaystyle O(1)$. קל לראות שמתקיים $\displaystyle T'(i,j)=\Theta (j)$

כרגיל, נמצא את זמן הריצה האמיתי של הקריאות הרקורסיביות כך:

$\displaystyle \sum _{i=1}^{k}\sum _{j=1}^{n}[T'(i,j)]=$
$\displaystyle \sum _{i=1}^{k}\sum _{j=1}^{n}[\Theta (j)]=$
$\displaystyle \sum _{i=1}^{k}[\Theta (n^{2})]=$
$\displaystyle \Theta (k\cdot n^{2}).$

יש לקחת בחשבון גם את זמן הריצה של אתחול המטריצה (M ואת הדפסת פרטי הפתרון:

• אתחול המטריצה אורך$\displaystyle \Theta (k\cdot n)$
• הדפסת הפרטים אורכת $\displaystyle \Theta (k)$

הסיבוכיות הכוללת, לכן, היא

$\displaystyle \Theta (k\cdot n)+\Theta (k)+\Theta (k\cdot n^{2})=\Theta (k\cdot n+k+k\cdot n^{2})=\Theta (k\cdot n^{2})$

פתרון תת-מחרוזת עולה ארוכה ביותר ע"י תת-מחרוזת משותפת ארוכה ביותר

שאלה

נניח שנתנה לך פונקציה יעילה LCS(X, Y) הפותרת את בעיית תת-המחרוזת המשותפת הארוכה ביותר. אנא הצע אלגוריתם יעיל Convert(X) המקבל מחרוזת, ומחזיר מחרוזת שתקיים תמיד שLCS(X, Convert(X)) הוא אורך תת-המחרוזת העולה הארוכה ביותר של X.

אנא הוכח את נכונות תשובתך, ונתח את סיבוכיות הפונקציה Convert במונחי ארכו של X.

תשובה

הפונקציה Convert(X) פשוט תחזיר את המערך ממויין בסדר עולה. (אם נשתמש במיון מיזוג, אז הסיבוכיות תהיה $\displaystyle \Theta (n\log(n))$).

נניח שהמערך המקורי הוא $\displaystyle X$, והמערך הממויין הוא $\displaystyle X'$.

כל תת-מחרוזת עולה של $\displaystyle X$, נניח $\displaystyle Y$, היא תת-מחרוזת משותפת ל$\displaystyle X$ ו$\displaystyle X'$: היא בהכרח תת-מחרוזת של $\displaystyle X$ לפי ההגדרה, והיא תת-מחרוזת של $\displaystyle X'$ מפני שהיא מחרוזת עולה שאיבריה הם איברי $\displaystyle X$.

לכן, בפרט, תת-המחרוזת המשותפת הארוכה ביותר היא גם בהכרח תת-המחרוזת העולה הארוכה ביותר של $\displaystyle X$.

הדפסה יפה

שאלה

ברצוננו להדפיס פסקת טקסט בצורה יפה.

נתונות לנו $\displaystyle n$ מילים, Word[1], Word[2], ..., Word[n]. עלינו להחליט היכן לסיים כל שורה בפסקה, לפי הכללים הבאים:

1. בכל שורת טקסט יש מקום ל$\displaystyle M$ תווים (אין מילה בעלת יותר מ$\displaystyle M$ תווים).
2. יש להדפיס רווח יחיד בין כל שתי מילים באותה שורה.

דוגמה: נניח ש$\displaystyle M=20$, והמילים הן If they have no rice, let them eat ladoo. נוכל לבנות פסקה כך: If they have no rice, let them eat ladoo. אך לא כך: If they have no rice, let them eat ladoo. (בדוגמה השניה יש יותר מ20 תווים בשורה הראשונה).

אם בשורה יש $\displaystyle m'$ תווים (כולל הרווחים בין המילים), אז יופי השורה הוא $\displaystyle {\frac {1}{(M-m'+1)^{2}}}$. יופי הפסקה מוגדר כסכום היופי של השורות שלו, למעט השורה האחרונה.

דוגמה: בפסקה If they have no rice, let them eat ladoo. יש 15 תווים בשורה הראשונה, ו14 תווים בשורה השניה. יופי הפסקה, לכן הוא $\displaystyle {\frac {1}{(20-15+1)^{2}}}+{\frac {1}{(20-14+1)^{2}}}={\frac {1}{6^{2}}}+{\frac {1}{7^{2}}}$.

אנא מצא אלגוריתם יעיל למציאת הפסקה היפה ביותר. הנח ש$\displaystyle n$ הוא משתנה גלובלי נתון, ושקיימת פונקציה Length המקבלת מספר $\displaystyle i$ ומחזירה את מספר התווים במילה ה$\displaystyle i$.

תשובה

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