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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

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

קפיצה אל: ניווט, חיפוש

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

תוכן עניינים

1 תת-סידרה עולה ארוכה ביותר
- 1.1 שאלה
- 1.2 תשובה
2 תת-סידרה בדלנית מקסימאלית כפלית
- 2.1 שאלה
- 2.2 תשובה
3 חיתוך בד
- 3.1 שאלה
- 3.2 תשובה
4 תת-מחרוזת משותפת ארוכה ביותר
- 4.1 שאלה
- 4.2 תשובה
5 גשר זבלה
- 5.1 שאלה
- 5.2 תשובה
6 זמן הריצה של הכפלת שרשרת מטריצות תחת Memoization
- 6.1 שאלה
- 6.2 תשובה
7 נוסע מתמיד ביטוני אויקלידי
- 7.1 שאלה
- 7.2 תשובה
8 רשת חומוסיות
- 8.1 שאלה
- 8.2 תשובה
9 תכנון פרוייקטים
10 פתרון תת-מחרוזת עולה ארוכה ביותר ע"י תת-מחרוזת משותפת ארוכה ביותר
- 10.1 שאלה
- 10.2 תשובה
11 הדפסה יפה
- 11.1 שאלה
- 11.2 תשובה

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

[עריכה] שאלה

הגדרה:

נתונה סידרה $\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.

[עריכה] תשובה

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

נגדיר את הרישה ה $\displaystyle i$ של מחרוזת $\displaystyle X$ כ $\displaystyle X_i = x_1, ..., x_i$ .‏
נגדיר כ $\displaystyle l(i)$ את אורך הLIS של $\displaystyle X_i$ שאיברה האחרון הוא $\displaystyle x_i$ .
נשים לב ש:
1. $\displaystyle \max_{1 \le i \le n}[l(i)]$ הוא אורך הLIS של $\displaystyle X$ .
2. $\displaystyle l(i)$ מקיים את הנוסחה $\displaystyle l(i) = 1 + \max_{1 \le j < i, \; x_j\le x_i}[l(j)]$ .

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

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

נאתחל את כל אחד מאיברי L ל $\displaystyle \infty$ .
נעבור בלולאה, משמאל לימין, על איברי X. כשנגיע לאיבר ה:
1. נחפש את האיבר הגדול ביותר ב בL[1], ..., L[i - 1] שאינו גדול מX[i].
2. אם מצאנו איבר כזה בכניסה ה $\displaystyle j$ של L, נקבע L[j + 1] = X[i].
3. אם לא, נקבע L[1] = X[i].
נמצא את האיבר הגדול ביותר ב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-3 מאתחלים את L. קל לראות שהסיבוכיות לינארית.
ב4-6 מעדכנים את L על פי ההסבר שראינו למעלה. הפונקציה Smaller-Index, שמימושה אינו מופיע כאן, ניתנת למימוש בקלות באופן דומה למה שראינו ב[[מבני נתונים ואלגוריתמים - מחברת קורס/#|]] (שים לב שL ממוין). הסיבוכיות היא $\displaystyle \sum_{i = 1}^n[O(\log(i))] = O(n \cdot \log(n))$ .
ב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\}$ .

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

אם $\displaystyle i = 1$ , אז בוודאי שנבחר באיבר הראשון (כל איבר הוא לפחות 1); נקבל בהכרח $\displaystyle x_1$ .
אם $\displaystyle i = 2$ , אז בוודאי שנבחר באיבר הראשון או באיבר השני (כל איבר הוא לפחות 1); נקבל בהכרח $\displaystyle \max\{x_1, x_2\}$ .
אם , אז או שנבחר ב או שלא (אלו שתי האפשרויות היחידות).
- אם נבחר ב $\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)

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

נאתחל המשתנים הגלובליים, ונקרא לMax-Product(n).
נקרא ל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$ . כלומר:

חתיכת בד במידה $\displaystyle (n_1, m_1)$ שווה $\displaystyle p_1$ שקלים.
חתיכת בד במידה $\displaystyle (n_2, m_2)$ שווה $\displaystyle p_2$ שקלים.
...
חתיכת בד במידה $\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)$ :

0 אם $\displaystyle (i, j)$ אינה אחת מ $\displaystyle k$ המידות בעלות התועלת.
$\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 \le i' < i}m(i', j) + m(i - i', j),$
$\displaystyle \max_{1 \le 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)\}$ .

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

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

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

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

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

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

כדאי לחתוך את פיסת הבד אפקית באיזשהו $\displaystyle i'$ . במקרה זה נקבל שתי חתיכות בד, האחת במידות $\displaystyle (i', j)$ ,‏ והשניה במידות $\displaystyle (i - i', j)$ . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא $\displaystyle m(i', j)$ ,‏ ועבור השניה $\displaystyle m(i - i', j)$ .
כדאי לחתוך את פיסת הבד אנכית באיזשהו $\displaystyle j'$ . במקרה זה נקבל שתי חתיכות בד, האחת במידות $\displaystyle (i, j')$ ,‏ והשניה במידות $\displaystyle (i, j - j')$ . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא $\displaystyle m(i, j')$ ,‏ ועבור השניה $\displaystyle m(i, j - j')$ .
כלל לא משתלם לחתוך את פיסת הבד: הטוב ביותר האפשרי הוא 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 היינו ממשים זאת בעזרת מטריצה של מבנים):

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

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

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$ :

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

שימו לב:

בכל אחד משני הסעיפים:

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

[עריכה] תשובה

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

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

כפי שצוין בשאלה, נגדיר את אורך $\displaystyle X$ כ $\displaystyle m$ , ואת אורך $\displaystyle Y$ כ $\displaystyle n$ .
נסמן את הרישה ה $\displaystyle i$ של מחרוזת $\displaystyle X$ כ $\displaystyle X_i$ . במילים אחרות, $\displaystyle X_i = x_1, ..., x_i$ .‏
נגדיר כ $\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$ .
אם לא,‏ אז:
1. אם $\displaystyle x_i = y_j$ , אז $\displaystyle l(i, j) = 1 + l(i - 1, j - 1)$ .
2. אם $\displaystyle x_i \ne 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 \ne y_j$ ; יש שלוש אפשרויות:

$\displaystyle Z$ מסתיימת ב $\displaystyle x_i$ - אם כן, הLCS בהכרח מהצורה $\displaystyle Z'x_i$ , כאשר $\displaystyle Z'$ היא הLCS של $\displaystyle X_i$ ו $\displaystyle Y_{j - 1}$ .
$\displaystyle Z$ מסתיימת ב $\displaystyle y_j$ - אם כן, הLCS בהכרח מהצורה $\displaystyle Z'y_j$ , כאשר $\displaystyle Z'$ היא הLCS של $\displaystyle X_{i - 1}$ ו $\displaystyle Y_j$ .
$\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$ :

'x' מסמלת את ההחלטה לוותר על התו האחרון ב $\displaystyle X_i$ .
'y' מסמלת את ההחלטה לוותר על התו האחרון ב $\displaystyle Y_j$ .
'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 \le j < i} \left\{m(j) + k + m(i-j)\right\}\right\}$ .

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

אם $\displaystyle i = 1$ ,‏ אז אין מה לחתוך; ההובלה תעלה $\displaystyle f(1)$ .
אם $\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:

$\displaystyle T'(i, j) = \Theta(j - i + 1)$ (נזכר ש $\displaystyle T'(i, j)$ מוגדרת כזמן שאורכת Min-Time(i, j) בהנחה שכ"א מהקריאות הרקורסיביות היא $\displaystyle O(1)$ ).
$\displaystyle T(1, n) = \sum_{i = 1}^n\sum_{j = i}^n[T'(i, j)]$ .
$\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$ , ולעוד צמתים. הקווים המקווקווים מציינים שהקריאות אינן בהכרח ישירות.

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

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

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

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

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

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

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

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

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

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

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

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

קל להשתכנע שבשלב בו נחליף את צומת הראש בצומת לא מודגש, רשמנו בצד את כל האיברים מהצורה $\displaystyle T'(i, j)$ , כאשר $\displaystyle 1 \le i \le n$ ו $\displaystyle j \le i \le 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$ .

[עריכה] תשובה

[עריכה] מספר סימונים ואבחנה פשוטה

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

כפי שצוין בשאלה, נגדיר את אורך $\displaystyle P$ כ $\displaystyle n$ .
נסמן את הנקודות שבמערך כ $\displaystyle p_1 = (x_1, y_1), p_2 = (x_2, y_2), ..., p_n = (x_n, y_n)$ . כאמור, אנו מניחים שהנקודות כבר ממוינות כך ש $\displaystyle x_1 \le x_2 \le ... \le x_n$ .
נסמן את המרחק בין שתי נקודות $\displaystyle p = (x, y)$ ו $\displaystyle p' = (x', y')$ כ $\displaystyle d(x, y) = \sqrt{(x - x')^2 + (y - y')^2}$ .
נאמר ששני מסלולים שקולים אם אחד מתקבל מהשני ע"י החלפת כווני החיצים.

דוגמה:

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

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

משפט:

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

[עריכה] בעיה דומה לא-מעגלית

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

המסלול מתחיל ב $\displaystyle p_i$ וממשיך כלפי שמאל עד ל $\displaystyle p_1$ .
כשהמסלול מגיע (מכוון ימין) ל $\displaystyle p_1$ , הוא מסתובב ימינה, וממשיך עד ל $\displaystyle p_j$ ‏‏ שם הוא מסתיים.
המסלול עובר דרך כל אחד מהנקודות $\displaystyle p_1, p_2, ..., p_i$ בדיוק פעם אחת.

שימו לב:

המסלול שעליו דיברנו זה עתה אינו מעגלי. הוא מתחיל ב $\displaystyle p_i$ , ומסתיים ב $\displaystyle p_j \ne p_i$ .

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

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

משפט:

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

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

מ $\displaystyle p_1$ ימינה ל $\displaystyle p_j$
מ $\displaystyle p_j$ ימינה ישירות ל $\displaystyle p_n$
מ $\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 \ge 1$ .
$\displaystyle m(i, i - 1) = min_{1 \le 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$ .

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

$\displaystyle m(i, 1)$ הוא אורך המסלול הזול ביותר שעובר שמאלה מ $\displaystyle p_i$ ל $\displaystyle p_1$ , מ $\displaystyle p_1$ פונה ימינה, אינו מגיע לאף נקודה אחרת מכוון ימין, ומכסה את כל הנקודות משמאלה ל $\displaystyle p_i$ . לכן, בהכרח, מדובר במסלול שעובר נקודה אחרי נקודה מ $\displaystyle p_i$ ל $\displaystyle p_1$ .
$\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 בתרשים הבא מציג זאת.

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

[עריכה] פסוודו-קוד

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

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)

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

IJ-Length(i, j) מממש את נוסחת הנסיגה שראינו מקודם לבעיה הלא-מעגלית.
Min-Bitonic-Euclidean() מוצא את הנקודה $\displaystyle j$ הימנית ביותר כפי שראינו מקודם בקשר בין הבעיה המעגלית והבעיה הלא-מעגלית.
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)$ :

איתחול המטריצה הוא $\displaystyle \Theta(n^2)$ .
נסמן כ $\displaystyle T'(i, j)$ את זמן הריצה של IJ-Length(i, j),‏ ‏ בהנחה שכל אחת מהקריאות הרקורסיביות היא $\displaystyle O(1)$ . אפשר לראות ש $\displaystyle T'(i, j) = O(1)$ ,‏ כל עוד $\displaystyle j \ne 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$ מציינים את מספרי הבתים ברחוב בהם יש מקום פנוי להקמת סניף חדש. הרשת שוקלת היכן להקים את הסניפים החדשים:

מסקר שוק, הרשת מעריכה שבבית מספר $\displaystyle m_i$ רווחיה הצפויים יהיו $\displaystyle p_i$ ‏( $\displaystyle p_i$ הוא מספר חיובי כלשהו).
הרשת אינה מוכנה להקים שני סניפים שמרחקם זה מזה הוא פחות מ $\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 &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)אורכת $\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 \le i \le k$ ומספר עובדות $\displaystyle 1 \le j \le n$ , ‏ $\displaystyle q(i, j)$ הוא מספר המייצג את איכות ביצוע הפרוייקט ה $\displaystyle$ i אם ישבצו לו $\displaystyle j$ עובדות. הנח:

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

לכל פרוייקט $\displaystyle i$ יש "חשיבות" לא-שלילית $\displaystyle h(i)$ . אנו רוצים למקסם את סך האיכויות המשוקללות. במילים אחרות, אנו רוצים למקסם את $\displaystyle \max_{i_1, i2, \ldots, i_n : i_1 \ge 0, \ldots, i_n \ge 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 \le j' \le 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]. עלינו להחליט היכן לסיים כל שורה בפסקה, לפי הכללים הבאים:

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

דוגמה:

נניח ש $\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$ .

[עריכה] תשובה

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

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

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

תוכן עניינים

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

[עריכה] שאלה

[עריכה] תשובה

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

[עריכה] שאלה

[עריכה] תשובה

[עריכה] המבנה הרקורסיבי

[עריכה] מימוש רקורסיבי נאיבי

[עריכה] שימוש בmemoization

[עריכה] הדפסת האיברים

[עריכה] ניתוח סיבוכיות

[עריכה] חיתוך בד

[עריכה] שאלה

[עריכה] תשובה

[עריכה] המבנה הרקורסיבי

[עריכה] מימוש רקורסיבי נאיבי

[עריכה] שימוש בmemoization

[עריכה] הדפסת החלטות החיתוך

[עריכה] ניתוח סיבוכיות

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

[עריכה] שאלה

[עריכה] תשובה

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

[עריכה] מציאת אורך הLCS

[עריכה] ניתוח סיבוכיות

[עריכה] הדפסת איברי הLCS

[עריכה] גשר זבלה

[עריכה] שאלה

[עריכה] תשובה

[עריכה] המבנה הרקורסיבי

[עריכה] מימוש נאיבי

[עריכה] שימוש בmemoization

[עריכה] הדפסת נקודות השבירה

[עריכה] ניתוח סיבוכיות

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

[עריכה] שאלה

[עריכה] תשובה

[עריכה] א'

[עריכה] ב'

[עריכה] ג'

[עריכה] נוסע מתמיד ביטוני אויקלידי

[עריכה] שאלה

[עריכה] תשובה

[עריכה] מספר סימונים ואבחנה פשוטה

[עריכה] בעיה דומה לא-מעגלית

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

[עריכה] נוסחת נסיגה לבעיה הלא-מעגלית

[עריכה] פסוודו-קוד

[עריכה] תזכור (Memoization)

[עריכה] ניתוח סיבוכיות

[עריכה] רשת חומוסיות

[עריכה] שאלה

[עריכה] תשובה

[עריכה] תכנון פרוייקטים

[עריכה] שאלה

[עריכה] תשובה

[עריכה] המבנה הרקורסיבי

[עריכה] פסוודו-קוד

[עריכה] הדפסת פרטי הפתרון

[עריכה] הוספת תזכור (memoization)

[עריכה] ניתוח סיבוכיות

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

[עריכה] שאלה

[עריכה] תשובה

[עריכה] הדפסה יפה

[עריכה] שאלה

[עריכה] תשובה

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא