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

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

עריכה

שאלה

עריכה

הגדרה:

נתונה סידרה   של מספרים שונים זה מזה.   היא תת-סידרה עולה של   אם:

  1. קיימת סדרה עולה ממש של אינדקסים   כך ש  לכל  .
  2.   היא סידרה עולה.




דוגמה:

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



הגדרה:

אם   היא סידרה, אז   היא הLIS (או longest increasing subsequence), אם היא הארוכה ביותר מבין תתי-הסדרות העולות של  .


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

תשובה

עריכה

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

  1. נגדיר את הרישה ה  של מחרוזת   כ .‏
  2. נגדיר כ  את אורך הLIS של   שאיברה האחרון הוא  .
  3. נשים לב ש:
    1.   הוא אורך הLIS של  .
    2.   מקיים את הנוסחה  .

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

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

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



דוגמה:

נניח שX == [1, 5, 2, 3]. תחילה נאתחל את המערך L, כך שL == [∞, ∞, ∞, ∞].

כעת נעבור בלולאה על איברי X:

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


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



משפט:

בסוף האיטרציה ה  של הלולאה:

  1. L ממוין.
  2. אם האיבר ה  בL אינו  , אז יש תת-סידרה עולה ב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 ממוין). הסיבוכיות היא  .
  3. ב7-10 מחפשים את המקסימום בL. קל לראות שהסיבוכיות לינארית.


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

עריכה

שאלה

עריכה

נתונה סידרה   של מספרים גדולים או שווים ל1. תת-סידרה   של X נקראת חברותית אם היא מכילה לפחות שני איברים עוקבים של X, ובדלנית אם היא איננה חברותית.




דוגמה:

נניח ש . אז:

  1.   היא תת-סידרה חברותית.
  2.   היא תת-סידרה בדלנית.
  3.   היא תת-סידרה חברותית.
  4.   היא תת-סידרה בדלנית.
  5.   היא תת-סידרה בדלנית.


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




דוגמה:

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

תשובה

עריכה

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

עריכה

נגדיר כ  את המכפלה הגדולה ביותר האפשרית של תת-סידרה בדלנית של   (שים לב שתת-הסדרה אינה בהרכח משתמשת ב ).



משפט:

  מקיימת את נוסחת הנסיגה הבאה:

  1. אם  , אז  .
  2. אם  , אז  .
  3. אם  , אז  .



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

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

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

 

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

עריכה

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

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

קל לראות שסיבוכיות האלגוריתם גבוהה מדי. היא נתונה ע"י הפתרון לנוסחה   (כלומר אקספוננציאלית, מפני שזו סדרת 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 מחזיק בכניסה ה  את ההכרעה האם תת-הסדרה הטובה ביותר עד   אכן משתמשת באיבר ה  או לא. קטע הקוד הבא מראה כיצד להדפיס את האינדקסים של תת-הסידרה הטובה ביותר המסתיימת ב .

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) נתון על ידי  , כאשר   הוא זמן הריצה של Max-Product(i) בהנחה שכל קריאה רקורסיבית היא   (ראו הניתוח בדג הסלמון).
  • מהתבוננות, קל לראות שהדפסת האיברים היא  .


חיתוך בד

עריכה

שאלה

עריכה

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

נתונות   מידות,  , שלהן מותאמים מחירים  . כלומר:

  1. חתיכת בד במידה   שווה   שקלים.
  2. חתיכת בד במידה   שווה   שקלים.
  3. ...
  4. חתיכת בד במידה   שווה   שקלים.חוץ מ  מידות אלה, כל המידות האחרות חסרות ביקוש, ולכן כל חתיכת בד במידה שונה

ממידות אלה שווה 0 שקלים. הנח שכל   ו  הוא מספר שלם חיובי ממש.




דוגמה:

בתרשים הבא, A מראה פיסת בד במידות  , וB מראה שתי מידות בעלת ערך: העליונה בעלת המידות  , והתחתונה בעלת המידות  . נניח שהמידה העליונה שווה 35 שקל, והתחתונה שווה 2 שקלים.


 
.


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




דוגמה:

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

בתרשים הבא:

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


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


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

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

  1. 0 אם   אינה אחת מ  המידות בעלות התועלת.
  2.   אם  .


 

כדאי לדעת:

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

תשובה

עריכה

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

עריכה

נגדיר כ  את מקסימום הרווח מפיסת בד במידות  .‏



משפט:

  נתונה על ידי נוסחת הנסיגה הבאה:

 
 
 
 
(כאשר   הוא הערך המוחזר מהפונקציה Value(i, j)).


 

כדאי לדעת:

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

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


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

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

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

 
חיתוך אופקי.

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

 
חיתוך אנכי.


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

  1. כדאי לחתוך את פיסת הבד אפקית באיזשהו  . במקרה זה נקבל שתי חתיכות בד, האחת במידות  ,‏ והשניה במידות  . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא  ,‏ ועבור השניה  .
  2. כדאי לחתוך את פיסת הבד אנכית באיזשהו  . במקרה זה נקבל שתי חתיכות בד, האחת במידות  ,‏ והשניה במידות  . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא  ,‏ ועבור השניה  .
  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'

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

עריכה

נגדיר כ  את סיבוכיות Max-Cuts(i, j) בהנחה שכל קריאה רקורסיבית היא  . קל מאד לראות מהקוד ש . נשים לב גם ש , ולכן  . סיבוכיות   חסומה מלמעלה על ידי  .

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


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

עריכה

שאלה

עריכה

הגדרה:

מחרוזת היא רצף של תווים. אם  ,‏  ,‏ ו  הן שלוש מחרוזות, אז:

  1.   היא תת-מחרוזת של   אם קיימת סדרה עולה ממש של אינדקסים   כך ש  לכל  .
  2.   היא תת-מחרוזת משותפת של   ו  אם היא תת-מחרוזת הן של   והן של  




דוגמה:

  ו  הן מחרוזות.

אם   ו , אז:

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



הגדרה:

אם   ו  הן מחרוזות, אז   היא הLCS (או longest common subsequence), אם היא הארוכה ביותר מבין תתי-המחרוזות המשותפות ל  ול .

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

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


 

שימו לב:

בכל אחד משני הסעיפים:
  1. הנח שX וY הם שני מערכים גלובליים המתארים את המחרוזות   ו , בעלות האורכים   ו  בהתאמה.
  2. אנא הוכח נכונות תשובתך, ונתח את סיבוכיותה במונחי   ו .

תשובה

עריכה

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

עריכה

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

  1. כפי שצוין בשאלה, נגדיר את אורך   כ , ואת אורך   כ .
  2. נסמן את הרישה ה  של מחרוזת   כ . במילים אחרות,  .‏
  3. נגדיר כ  את אורך הLCS של   ו . במילים אחרות,   היא אורך תת-הסדרה הארוכה ביותר המשותפת ל  ו .


 

עכשיו תורכם:

וודא שהמך מבין מדוע לפי הגדרה זו,   הוא אורך הLCS של   ו .



משפט:

  מקיים את הנוסחה הבאה:

  1. אם   או  ,‏ אז  .
  2. אם לא,‏ אז:
    1. אם  , אז  .
    2. אם  , אז  .



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


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

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

לחלופין, נניח ש ; יש שלוש אפשרויות:

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


 

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

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

עריכה

נגדיר את   כזמן שאורכת LCS-Length בהנחה שכל אחת מקריאותיה הרקורסיביות היא  . קל לראות ש .

זמן הריצה של LCS-Length(m, n) חסום מלמעלה על ידי  . חוץ מכך ישנו האתחול 1-4 שאורך גם כן  . הזמן הכולל, לכן, הוא  .

הדפסת איברי ה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 מתארת בכניסה ה  את ההחלטה לגבי הLCS של   ו :

  1. 'x' מסמלת את ההחלטה לוותר על התו האחרון ב .
  2. 'y' מסמלת את ההחלטה לוותר על התו האחרון ב .
  3. 'b' מסמלת את ההחלטה לוותר על התו האחרון בשניהם. זה בדיוק המצב בו   נמצא כחלק מה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])

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

גשר זבלה

עריכה

שאלה

עריכה

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



דוגמה:

נניח   ו  (ראה A בתרשים הבא). אפשר לשבור את הגשר ב4 אפנים:

  1. שוברים בנקודות 1 ו2. מתקבלים 3 חלקים בעלי אורך 1 כל אחד (ראה B בתרשים הבא). עלות השבירה היא  .
  2. שוברים בנקודה 1. מתקבלים 2 חלקים: הראשון בעל אורך 1, והשני בעל אורך 2 (ראה C בתרשים הבא). עלות השבירה היא  .
  3. שוברים בנקודה 2. מתקבלים 2 חלקים: הראשון בעל אורך 2, והשני בעל אורך 1 (ראה D בתרשים הבא). עלות השבירה היא  .
  4. לא שוברים באף נקודה. מתקבל חלק יחיד בעל אורך 3. עלות השבירה היא  .
 
דוגמה לגשר הזבלה.


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


 

שימו לב:

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




דוגמה:

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

  1. עלות ההובלה היא  .
  2. עלות ההובלה היא  .
  3. עלות ההובלה היא  .
  4. עלות ההובלה היא  .


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

תשובה

עריכה

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

עריכה

נגדיר כ  את העלות הזולה ביותר לטיפול בקטע באורך  .



משפט:

  נתונה על ידי נוסחת הנסיגה הבאה:

  1. אם  ,‏ אז  .
  2. אם  ,‏ אז  .



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

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


 


 

כדאי לדעת:

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

מימוש נאיבי

עריכה

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

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אם החלטנו לא לחלק את הקטע, והוא  אם החלטנו לשבור בנקודה 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) בהנחה שכל קריאה רקורסיבית היא   כ . קל לראות ש . זמן הריצה חסום מלמעלה על ידי  .

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


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

עריכה

שאלה

עריכה

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

  1.   (נזכר ש  מוגדרת כזמן שאורכת Min-Time(i, j) בהנחה שכ"א מהקריאות הרקורסיביות היא  ).
  2.  .
  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


נשים לב שאם נניח שכל קריאה רקורסיבית אורכת  , אז יש לנו מספר קריאות שכ"א היא   (1-6, 11), ולולאה בת   איטרציות, כאשר כל איטרציה היא  . זמן הריצה, לכן הוא  .

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

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

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

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

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

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

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

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

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

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

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

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

נחזור על אותה הפעולה עבור הצומת  .

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

כנ"ל לגבי הצומת  .

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

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

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

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


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

נשלב את שני הסעיפים הקודמים:  .

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


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

עריכה

שאלה

עריכה

הגדרה:

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


 

כדאי לדעת:

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

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


הגדרה:

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




דוגמה:

בתרשים הבא, A מראה מישור בעל   נקודות; B מראה את המסלול הקצר ביותר, אך המסלול אינו ביטוני.

 
מישור ומסלולים.

בתרשים הבא, A וB מראים כל אחד מסלול ביטוני אפשרי.

 
מסלולים ביטוניים.


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


 

שימו לב:

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

תשובה

עריכה

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

עריכה

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

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



דוגמה:

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

 
שני מסלולים שקולים.


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



משפט:

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


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

עריכה

נגדיר את   ‏( )‏ כעלות המסלול הזול ביותר שמקיים את התנאים הבאים:

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

שימו לב:

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

ומסתיים ב .

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

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

עריכה

משפט:

מחיר המסלול הביטוני הזול ביותר הוא  .


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

  1. מ  ימינה ל 
  2. מ  ימינה ישירות ל 
  3. מ  שמאלה חזרה ל 

עלות הקטע 2 היא בדיוק  . סכום עלויות הקטע 1 ו3 הוא בדיוק  .

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


 

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

עריכה

משפט:

  נתון על ידי נוסחת הנסיגה הבאה:

  1.  , לכל  .
  2.  , לכל  .
  3.  , לכל  .



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

  1.   הוא אורך המסלול הזול ביותר שעובר שמאלה מ  ל , מ  פונה ימינה, אינו מגיע לאף נקודה אחרת מכוון ימין, ומכסה את כל הנקודות משמאלה ל . לכן, בהכרח, מדובר במסלול שעובר נקודה אחרי נקודה מ  ל .
  2.   הוא אורך המסלול הזול ביותר שעובר שמאלה מ  ל , מ  ימינה ל , ומכסה את כל הנקודות משמאלה ל . נסמן כ  את הנקודה שאליה עובר המסלול ישירות מ ; A בתרשים הבא מציג זאת.
     
    מקרה 2 בהוכחת נוסחת הנסיגה.
    היות שהוכחנו למעלה שלמסלולים שקולים יש מחיר זהה, נוכל לטעון שB בתרשים הקודם בעל אותו מחיר כA.
  3.   הוא אורך המסלול הזול ביותר שעובר שמאלה מ  ל , מ  ימינה ל , ומכסה את כל הנקודות משמאלה ל . היות ש , המסלול חייב להתחיל במעבר ישיר (שמאלה) מ  ל .
     
    מקרה 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() מוצא את הנקודה   הימנית ביותר כפי שראינו מקודם בקשר בין הבעיה המעגלית והבעיה הלא-מעגלית.
  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]

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

עריכה

הסיבוכיות היא  :

  1. איתחול המטריצה הוא  .
  2. נסמן כ   את זמן הריצה של IJ-Length(i, j),‏ ‏ בהנחה שכל אחת מהקריאות הרקורסיביות היא  . אפשר לראות ש ,‏ כל עוד  , ואחרת  . קל לראות שסך כל ריצת הפונקציה הוא

 .

רשת חומוסיות

עריכה

שאלה

עריכה

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

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



דוגמה:

אם   והרשת בוחרת להקים סניף בבית מספר 135, אסור לה להקים סניף בבית מספר 143, שכן  .


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

תשובה

עריכה

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

נגדיר כ  את מירב הרווח שאפשר להרוויח מפתיחת סניפים הלקוחים מתוך  הבתים הראשונים.



משפט:

לפי הגדרת  :

  1. הפתרון הטוב ביותר הוא בעל רווח  .
  2. הפונקציה נתונה על ידי נוסחת הנסיגה:
    •  
    • לכל  ,‏  
  3.   מונוטונית לא-יורדת ב .



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

 

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

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 מתאר האם השתמשנו באיבר ה או לא. נשתמש בו ע"י קריאה לPrint-Nums(k, n), כאשר Print-Nums מוגדרת כך:

Print-Nums(k, i)
1	if i &amp;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)אורכת  . אם נגדיר כ  את זמן הקריאה לMax-Profit(M, P, k, i)בהנחה שכל קריאה רקורסיבית היא  , אז  , והסיבוכיות היא  . מצד שני, מיון המערך הוא  , ולכן נקבל  .


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

עריכה

שאלה

עריכה

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

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

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

לכל פרוייקט   יש "חשיבות" לא-שלילית  . אנו רוצים למקסם את סך האיכויות המשוקללות. במילים אחרות, אנו רוצים למקסם את  .

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

תשובה

עריכה

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

עריכה

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



משפט:

  =

  •  , אם  .
  •  , אם  .


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

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

 

פסוודו-קוד

עריכה

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

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] מתארת את מספר העובדות האופטימלי שכדאי להקצות לפרוייקט ה  אם יש   פרוייקטים ו  עובדות.

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

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


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

עריכה

כרגיל, נגדיר את   כזמן הריצה של Max-Value(i, j) כאשר כל קריאה רקורסיבית היא  . קל לראות שמתקיים  

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

 
 
 
 

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

  • אתחול המטריצה אורך 
  • הדפסת הפרטים אורכת  

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

 


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

עריכה

שאלה

עריכה

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

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

תשובה

עריכה

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


נניח שהמערך המקורי הוא  , והמערך הממויין הוא  .

כל תת-מחרוזת עולה של  , נניח  , היא תת-מחרוזת משותפת ל  ו : היא בהכרח תת-מחרוזת של   לפי ההגדרה, והיא תת-מחרוזת של