מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/תכנון דינאמי/תרגילים
תת-סידרה עולה ארוכה ביותר
עריכהשאלה
עריכה
הגדרה: נתונה סידרה של מספרים שונים זה מזה. היא תת-סידרה עולה של אם:
|
דוגמה: נניח ש . אם נקבע , אז היא תת-סידרה עולה של . גם אם נקבע תהיה תת-סידרה עולה של . |
הגדרה: אם היא סידרה, אז היא הLIS (או longest increasing subsequence), אם היא הארוכה ביותר מבין תתי-הסדרות העולות של . |
הנח שX
הוא מערך גלובלי המתאר את הסדרה , בעלת האורך . בשאלה זו עליך למצוא אלגוריתם יעיל למציאת אורך הLIS.
תשובה
עריכהנשתמש במספר סימונים ומשפטים פשוטים:
- נגדיר את הרישה ה של מחרוזת כ .
- נגדיר כ את אורך הLIS של שאיברה האחרון הוא .
- נשים לב ש:
- הוא אורך הLIS של .
- מקיים את הנוסחה .
בפתרון נשתמש במערך גלובלי L
המתאר, בכניסה ה , את האיבר הקטן ביותר עד כה המסיים תת-סידרה עולה באורך .
אלה שלבי פעולות הפתרון:
- נאתחל את כל אחד מאיברי
L
ל . - נעבור בלולאה, משמאל לימין, על איברי
X
. כשנגיע לאיבר ה :- נחפש את האיבר הגדול ביותר ב ב
L[1], ..., L[i - 1]
שאינו גדול מX[i]
. - אם מצאנו איבר כזה בכניסה ה של
L
, נקבעL[j + 1] = X[i]
. - אם לא, נקבע
L[1] = X[i]
.
- נחפש את האיבר הגדול ביותר ב ב
- נמצא את האיבר הגדול ביותר ב
L
שאינו , ונחזיר את האינדקס שלו כתשובה המבוקשת.
דוגמה: נניח ש כעת נעבור בלולאה על איברי
|
את המשפט הבא קל להוכיח באינדוקציה:
משפט: בסוף האיטרציה ה של הלולאה:
|
להלן הפסוודו-קוד המתאים:
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
ממוין). הסיבוכיות היא . - ב7-10 מחפשים את המקסימום ב
L
. קל לראות שהסיבוכיות לינארית.
תת-סידרה בדלנית מקסימאלית כפלית
עריכהשאלה
עריכהנתונה סידרה של מספרים גדולים או שווים ל1. תת-סידרה של X נקראת חברותית אם היא מכילה לפחות שני איברים עוקבים של X, ובדלנית אם היא איננה חברותית.
דוגמה: נניח ש . אז:
|
אנא כתוב אלגוריתם אשר מקבל סידרה ומדפיס תת-סידרה בדלנית שמכפלת איבריה גדולה ככל האפשר. (הנח שמכפלת איברי תת-סידרה ריקה היא 1.) קבע את Length(X)
כ , ונתח את סיבוכיות האלגוריתם במונחי .
דוגמה: נניח שהאלגוריתם מקבל כקלט את . במקרה זה, עליו להדפיס : זו תת-סידרה בדלנית של , , ואין תת-סידרה בדלנית אחרת שמכפלת איבריה גדולה מ35. |
תשובה
עריכההמבנה הרקורסיבי
עריכהנגדיר כ את המכפלה הגדולה ביותר האפשרית של תת-סידרה בדלנית של (שים לב שתת-הסדרה אינה בהרכח משתמשת ב ).
משפט: מקיימת את נוסחת הנסיגה הבאה:
|
הוכחה: נשים לב לנקודות הבאות:
- אם , אז בוודאי שנבחר באיבר הראשון (כל איבר הוא לפחות 1); נקבל בהכרח .
- אם , אז בוודאי שנבחר באיבר הראשון או באיבר השני (כל איבר הוא לפחות 1); נקבל בהכרח .
- אם , אז או שנבחר ב או שלא (אלו שתי האפשרויות היחידות).
- אם נבחר ב , אז לא נוכל לבחור ב ; במקרה זה נרצה להכפיל את בתוצאה הטובה ביותר האפשרית עד , שהיא .
- אם לא נבחר את , אז נרצה את תת-הסדרה הטובה ביותר עד , שהיא, עפ"י ההגדרה, .
בנקודה השלישית, היות שאיננו יודעים אם כדאי לבחור את האיבר ב או לא - ניקח את המקסימום משתי האפשרויות.
מימוש רקורסיבי נאיבי
עריכהלהלן פסוודו-קוד המממש רעיון זה:
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)
כיצד נשתמש בקוד, אם כן?
- נאתחל המשתנים הגלובליים, ונקרא ל
Max-Product(n)
. - נקרא ל
Print-Seq(n)
.
ניתוח סיבוכיות
עריכההסיבוכיות הכוללת הנה לינארית:
- מהתבוננות, ברור שהאתחול לינארי.
- הסיבוכיות של
Max-Product(n)
נתון על ידי , כאשר הוא זמן הריצה שלMax-Product(i)
בהנחה שכל קריאה רקורסיבית היא (ראו הניתוח בדג הסלמון). - מהתבוננות, קל לראות שהדפסת האיברים היא .
חיתוך בד
עריכהשאלה
עריכהנתונה פיסת בד שמידותיה (כלומר ארכה מטר, ורחבה מטר). הנח ש ו מספרים שלמים.
נתונות מידות, , שלהן מותאמים מחירים . כלומר:
- חתיכת בד במידה שווה שקלים.
- חתיכת בד במידה שווה שקלים.
- ...
- חתיכת בד במידה שווה שקלים.חוץ מ מידות אלה, כל המידות האחרות חסרות ביקוש, ולכן כל חתיכת בד במידה שונה
ממידות אלה שווה 0 שקלים. הנח שכל ו הוא מספר שלם חיובי ממש.
דוגמה: בתרשים הבא, A מראה פיסת בד במידות , וB מראה שתי מידות בעלת ערך: העליונה בעלת המידות , והתחתונה בעלת המידות . נניח שהמידה העליונה שווה 35 שקל, והתחתונה שווה 2 שקלים.
|
המטרה היא להפיק מהבד את מרב הערך, ע"י גזירת הבד אם יש תועלת בכך. בכל גזירה אפשר מותר לגזור את פיסת הבד לאורך או לרוחב. הנח שאין יכולת לסובב את פיסת הבד.
דוגמה: כיצד נוכל להשתמש בפיסת הבד מA שבדוגמה הקודמת? לו היינו יכולים לסובב אותה, היינו יכולים להפיק ממנה צורה ששווייה 35 שקל ללא גזירה אחת. עם זאת, עדיין יש סדרת גזירות שתפיק צורות בשווי 4 שקלים. בתרשים הבא:
יש עוד סדרות חיתוך שיניבו צורות בשווי 4 שקלים, אך אין סדרה שתניב יותר מכך. |
בשאלה זו עליך למצוא אלגוריתם יעיל למציאת סדרת החיתוך הרווחית ביותר. אנא הוכח שהאלגוריתם שמצאת עובד בסיבוכיות .
הנח שקיימת פונקציה Value(i, j)
המחזירה בזמן :
- 0 אם אינה אחת מ המידות בעלות התועלת.
- אם .
כדאי לדעת: אפשר לפתור את הבעיה בצורה הבאה. מכינים טבלה בגודל על ובתא ה- שמים את הרווח מחיתוך הבד לגודל . רווח זה יהיה המקסימום מהרווחים אותם אפשר להשיג מחיתוך הבד לרוחב, מחיתוך הבד לאורך, וממכירת הבד כפי שהוא (כפי שמוחזר מהפונקציהValue(i, j) ).
|
תשובה
עריכההמבנה הרקורסיבי
עריכהנגדיר כ את מקסימום הרווח מפיסת בד במידות .
משפט: נתונה על ידי נוסחת הנסיגה הבאה: |
כדאי לדעת: שים לב שהנוסחה הנ"ל כוללת בתוכה תנאי עצירה, מפני שעבור , מה שכתוב כאן הינו פשוט .אפשר גם לכתוב את נוסחת הנסיגה בדרכים אחרות, ובחלקן גם יופיעו תנאי עצירה בצורה מפורשת יותר. |
הוכחה: יש שלוש אפשרויות:
- כדאי לחתוך את פיסת הבד אפקית באיזשהו (כמתואר בתרשים הבא). נשים לב שאפשרות זו רלוונטית רק עבור עבור .
- כדאי לחתוך את פיסת הבד אנכית באיזשהו (כמתואר בתרשים הבא אחריו). נשים לב שאפשרות זו רלוונטית רק עבור עבור .
- כלל לא משתלם לחתוך את פיסת הבד.
בתרשים הבא, לדוגמה, חיתוך אופקי של הצורה בA בשורה ייצור שתי צורות מלבניות בB; לראשונה שבהן יהיו שורות:
בתרשים הבא, לדוגמה, חיתוך אנכי של הצורה בA בעמודה ייצור שתי צורות מלבניות בB; לראשונה שבהן יהיו עמודות:
כעת נדון בכל אחת משלוש האפשרויות:
- כדאי לחתוך את פיסת הבד אפקית באיזשהו . במקרה זה נקבל שתי חתיכות בד, האחת במידות , והשניה במידות . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא , ועבור השניה .
- כדאי לחתוך את פיסת הבד אנכית באיזשהו . במקרה זה נקבל שתי חתיכות בד, האחת במידות , והשניה במידות . עפ"י ההגדרה, הטוב ביותר שאפשר להשיג עבור הראשונה הוא , ועבור השניה .
- כלל לא משתלם לחתוך את פיסת הבד: הטוב ביותר האפשרי הוא
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'
ניתוח סיבוכיות
עריכהנגדיר כ את סיבוכיות Max-Cuts(i, j)
בהנחה שכל קריאה רקורסיבית היא . קל מאד לראות מהקוד ש . נשים לב גם ש , ולכן . סיבוכיות חסומה מלמעלה על ידי
.
גם כאשר לוקחים בחשבון את האתחול והדפסת הפרטים, הפתרון עדיין .
תת-מחרוזת משותפת ארוכה ביותר
עריכהשאלה
עריכה
הגדרה: מחרוזת היא רצף של תווים. אם , , ו הן שלוש מחרוזות, אז:
|
דוגמה: ו הן מחרוזות. אם ו , אז:
|
הגדרה: אם ו הן מחרוזות, אז היא הLCS (או longest common subsequence), אם היא הארוכה ביותר מבין תתי-המחרוזות המשותפות ל ול . |
בשאלה זו עליך למצוא אלגוריתם יעיל למציאת הLCS לכל שתי מחרוזות ו :
- אנא תאר אלגוריתם יעיל המוצא את אורך הLCS.
- אנא תאר אלגוריתם יעיל המדפיס את הLCS עצמו.
שימו לב: בכל אחד משני הסעיפים:
|
תשובה
עריכההמבנה הרקורסיבי של הבעיה
עריכהראשית מספר סימונים:
- כפי שצוין בשאלה, נגדיר את אורך כ , ואת אורך כ .
- נסמן את הרישה ה של מחרוזת כ . במילים אחרות, .
- נגדיר כ את אורך הLCS של ו . במילים אחרות, היא אורך תת-הסדרה הארוכה ביותר המשותפת ל ו .
עכשיו תורכם: וודא שהמך מבין מדוע לפי הגדרה זו, הוא אורך הLCS של ו . |
משפט: מקיים את הנוסחה הבאה:
|
הוכחה: אם או , אז (לפחות) אחת המחרוזות היא המחרוזת הריקה, ורק המחרוזת הריקה יכולה להיות תת-מחרוזת של המחרוזת הריקה. למחרוזת הריקה יש אורך 0, ומכאן החלק הראשון של המשפט.
מכאן נניח ששתי המחרוזות אינן ריקות.
נניח ש . ראשית, קל לראות שבהכרח תווה האחרון של הוא - אם זה לא היה המצב, אז גם היא מחרוזת משותפת ל ו , דבר שנוגד עפ"י ההגדרה את היותה של תת-המחרוזת המשותפת הארוכה ביותר. נחשוב כעת על כל תתי המחרוזות המשותפות מהצורה : עבור כל אחת מהן, קל לראות ש היא תת-מחרוזת משותפת ל ו , ולכן בהכרח הארוכה שבהן היא זו שהרישה שלה היא הLCS של ו .
לחלופין, נניח ש ; יש שלוש אפשרויות:
- מסתיימת ב - אם כן, הLCS בהכרח מהצורה , כאשר היא הLCS של ו .
- מסתיימת ב - אם כן, הLCS בהכרח מהצורה , כאשר היא הLCS של ו .
- אינה מסתיימת ב , וכן אינה מסתיימת ב - אם זה המצב, אז ה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 של ו :
'x'
מסמלת את ההחלטה לוותר על התו האחרון ב .'y'
מסמלת את ההחלטה לוותר על התו האחרון ב .'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 אפנים:
|
כעת יש להוביל את חלקי הגשר. הנח שקיימת פונקציה ידועה כך ש מתארת את עלות הובלתו של חלק בעל אורך i. הנח ש הוא מספר שלם חיובי לכל .
שימו לב: וודא שאינך מניח במובלע דברים שלא נאמרו לגבי . בפרט, אל תניח שהפונקציה מונוטונית עולה (עלות ההובלה נקבעת לפי שיקולים שאיננו יודעים.) |
דוגמה: בהמשך לדוגמה הקודמת שראינו, נניח , , ו . ארבע האפשרויות שראינו מקודם יעלו כך:
|
אנא מצא אלגוריתם יעיל למציאת נקודות השבירה כך שסך העלויות (שבירה והובלה) נמוך ככל האפשר. כלומר, אנא כתוב אלגוריתם יעיל שימצא את העלות המינימלית וכן ידפיס את נקודות השבירה של עלות זו.
תשובה
עריכההמבנה הרקורסיבי
עריכהנגדיר כ את העלות הזולה ביותר לטיפול בקטע באורך .
משפט: נתונה על ידי נוסחת הנסיגה הבאה:
|
הוכחה: נשים לב לנקודות הבאות:
- אם , אז אין מה לחתוך; ההובלה תעלה .
- אם , אז או שלא חותכים את הקטע, או שכן. אם לא חותכים, עלות השבירה 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:
- (נזכר ש מוגדרת כזמן שאורכת
Min-Time(i, j)
בהנחה שכ"א מהקריאות הרקורסיביות היא ). - .
- .
תשובה
עריכהא'
עריכהנתבונן בפסוודו-קוד עם 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.
הציור אינו מראה את כל צמתי הקריאה מטעמי נוחות. הצומת קורא לצומת , בעקיפין לצמתים ו , ולעוד צמתים. הקווים המקווקווים מציינים שהקריאות אינן בהכרח ישירות.
חלק מהצמתים מודגשים, וחלק אינם:
- צומת מודגש אם הוא מתאר קריאה "רצינית", כלומר אחת שבה החלק העיקרי בפונקציה מתבצע (שורות 3-11 ב
Min-Time
). - צומת אינו מודגש אם הוא מתאר קריאה "פושטית", בה לכל היותר רק חלק הmemoization מתבצע (שורות 1-2 ב
Min-Time
).
נשים לב לנקודות הבאות:
- אם צומת לא מודגש, אז אין לו ילדים, ובנוסף, הוא (מדוע?)
- כל צומת מופיע מודגש פעם אחת (מדוע?)
ננתח כעת בשלבים, לפי הרעיון הבא. בכל שלב:
- ניקח צומת מודגש שאין לו ילדים מודגשים.
- ננתח את זמן הריצה שלו, ונרשום את התוצאה בצד. נשים לב שאם לצומת אין ילדים מודגשים, אז כל קריאה רקורסיבית שלו היא אכן (מפני שזו איננה ממש קריאה רקורסיבית). זמן הריצה שלו, לכן, הוא אכן .
- נמיר אותו בצומת לא מודגש, מפני שניתחנו כבר את חלק הקוד המסובך בו (ורשמנו אותו בצד). כל שנותר הוא הקריאה לפונקציה, והיא לוקחת .
נתחיל בצומת המודגש. לצומת זה אין כלל ילדים, ולכן זמן הקריאה הוא בבירור . נרשום בצד שעד כה הקריאות שעברנו עליהן עלו , ונחליף את הצומת בצומת לא מודגש. זה מסמן את העובדה שניתחנו כבר את החלק "עם הבשר" בצומת , וכל שנותר הוא .
נחזור על אותה הפעולה עבור הצומת .
כנ"ל לגבי הצומת .
כעת נתבונן בצומת בשלב בו כל ילדיו אינם מודגשים. כל קריאה רקורסיבית של צומת זה כוללת שני מחירים:
- עצם הקריאה לפונקציה, שעולה
- זמן הקריאה האמיתי, שאותו כבר חייבנו (ורשמנו בצד), ולכן אין צורך לחייב אותו כאן שוב
הפועל היוצא הוא שבשלב זה, מותר לנו לחייב את הצומת אך ורק בקריאות רקורסיביות שעלות כל אחת מהן היא . זה בדיוק .
קל להשתכנע שבשלב בו נחליף את צומת הראש בצומת לא מודגש, רשמנו בצד את כל האיברים מהצורה
,
כאשר
ו . בצורה אחרת, מה שרשום בצד הוא
.
ג'
עריכהנשלב את שני הסעיפים הקודמים: .
כבר ראינו כיצד לפשט טור כפול זה בתרגילים בסדרי גדילה.
נוסע מתמיד ביטוני אויקלידי
עריכהשאלה
עריכה
הגדרה: (הנוסע המתמיד האוקלידי) נתונות נקודות במישור. כל נקודה מייצגת שדה תעופה, לצורך העניין. סוכן נסיעות מתחיל את מסלולו בשדה התעופה השמאלי ביותר; עליו לעבור בכל שדה תעופה ולנחות בשדה התעופה שממנו יצא לדרכו. מחיר הטיסה משדה תעופה אחד לשני הוא המרחק האוקלידי בין שני השדות. על הנוסע למצוא את המסלול שעלותו הכוללת נמוכה ככל האפשר. |
כדאי לדעת: לבעיית הנוסע המתמיד האוקלידי אין אלגוריתם יעיל ידוע - כל האלגוריתמים הידועים עובדים בזמן אקספוננציאלי. למרות שהדבר לא הוכח, יש סיבות המרמזות לכך שלא ייתכן אלגוריתם יעיל לבעיה זו. |
שאלה זו דנה בגרסה קלה יותר של הבעיה.
הגדרה: (מסלול ביטוני) מסלול הוא ביטוני אם הוא מורכב משני תתי מסלולים: בראשון נעים בכיוון ימין, ובשני נעים מימין חזרה לכוון שמאל. |
דוגמה: בתרשים הבא, A מראה מישור בעל נקודות; B מראה את המסלול הקצר ביותר, אך המסלול אינו ביטוני. בתרשים הבא, A וB מראים כל אחד מסלול ביטוני אפשרי. |
בשאלה זו עליך למצוא אלגוריתם למציאת המסלול הביטוני האוקלידי הזול ביותר לכל קבוצת נקודות במרחב: אנא תאר אלגוריתם יעיל המוצא את עלות המסלול הנמוכה ביותר.
שימו לב: #הנח שP הוא מערך גלובלי בעל אורך המתאר את הנקודות.
|
תשובה
עריכהמספר סימונים ואבחנה פשוטה
עריכהראשית מספר סימונים:
- כפי שצוין בשאלה, נגדיר את אורך כ .
- נסמן את הנקודות שבמערך כ . כאמור, אנו מניחים שהנקודות כבר ממוינות כך ש .
- נסמן את המרחק בין שתי נקודות ו כ .
- נאמר ששני מסלולים שקולים אם אחד מתקבל מהשני ע"י החלפת כווני החיצים.
דוגמה: בתרשים הבא, A וB מראים מסלולים שקולים. |
המשפט הבא נובע בקלות מהגדרת המרחק האוקלידי.
משפט: אם שני מסלולים שקולים, אז מחירם זהה. |
בעיה דומה לא-מעגלית
עריכהנגדיר את ( ) כעלות המסלול הזול ביותר שמקיים את התנאים הבאים:
- המסלול מתחיל ב וממשיך כלפי שמאל עד ל .
- כשהמסלול מגיע (מכוון ימין) ל , הוא מסתובב ימינה, וממשיך עד ל שם הוא מסתיים.
- המסלול עובר דרך כל אחד מהנקודות בדיוק פעם אחת.
שימו לב: המסלול שעליו דיברנו זה עתה אינו מעגלי. הוא מתחיל ב ,ומסתיים ב . |
אף על פי שהמסלול אינו בדיוק מהסוג שעליו מדברת השאלה, קל לחשבו ביעילות, וניתן להשתמש בו כדי לפתור את השאלה. נראה זאת כעת.
הקשר לבעיה המקורית (המעגלית)
עריכה
משפט: מחיר המסלול הביטוני הזול ביותר הוא . |
הוכחה: במסלול המעגלי הקצר ביותר, נסמן כ את הנקודה הימנית ביותר לפני שנמצאת בחלק המסלול לכוון ימין (ראה התרשים הבא). המסלול, לכן, מורכב משלושה חלקים:
- מ ימינה ל
- מ ימינה ישירות ל
- מ שמאלה חזרה ל
עלות הקטע 2 היא בדיוק . סכום עלויות הקטע 1 ו3 הוא בדיוק .
נוסחת נסיגה לבעיה הלא-מעגלית
עריכה
משפט: נתון על ידי נוסחת הנסיגה הבאה:
|
הוכחה: נשקול את כל המקרים האפשריים:
- הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל , מ פונה ימינה, אינו מגיע לאף נקודה אחרת מכוון ימין, ומכסה את כל הנקודות משמאלה ל . לכן, בהכרח, מדובר במסלול שעובר נקודה אחרי נקודה מ ל .
- הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל , מ ימינה ל , ומכסה את כל הנקודות משמאלה ל . נסמן כ את הנקודה שאליה עובר המסלול ישירות מ ; A בתרשים הבא מציג זאת. היות שהוכחנו למעלה שלמסלולים שקולים יש מחיר זהה, נוכל לטעון שB בתרשים הקודם בעל אותו מחיר כA.
- הוא אורך המסלול הזול ביותר שעובר שמאלה מ ל , מ ימינה ל , ומכסה את כל הנקודות משמאלה ל . היות ש , המסלול חייב להתחיל במעבר ישיר (שמאלה) מ ל .
פסוודו-קוד
עריכהלהלן פסוודו-קוד המשתמש ברעיון זה:
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()
מוצא את הנקודה הימנית ביותר כפי שראינו מקודם בקשר בין הבעיה המעגלית והבעיה הלא-מעגלית.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]
ניתוח סיבוכיות
עריכההסיבוכיות היא :
- איתחול המטריצה הוא .
- נסמן כ את זמן הריצה של
IJ-Length(i, j)
, בהנחה שכל אחת מהקריאות הרקורסיביות היא . אפשר לראות ש , כל עוד , ואחרת . קל לראות שסך כל ריצת הפונקציה הוא
.
רשת חומוסיות
עריכהשאלה
עריכהרשת החומוסיות מק-לאפה מתכננת להקים סניפים רבים לאורך רחוב איבן-גבירול בתל אביב. מציינים את מספרי הבתים ברחוב בהם יש מקום פנוי להקמת סניף חדש. הרשת שוקלת היכן להקים את הסניפים החדשים:
- מסקר שוק, הרשת מעריכה שבבית מספר רווחיה הצפויים יהיו ( הוא מספר חיובי כלשהו).
- הרשת אינה מוכנה להקים שני סניפים שמרחקם זה מזה הוא פחות מ ( הוא מספר שלם חיובי כלשהו).
דוגמה: אם והרשת בוחרת להקים סניף בבית מספר 135, אסור לה להקים סניף בבית מספר 143, שכן . |
אנא כתוב אלגוריתם יעיל המקבל את המערך M
(המכיל את מספרי הבתים), את המערך P
(המכיל את הרווחים הצפויים), ואת המספר k
(המציין את מגבלת המרחק), ומדפיס את מספרי הבתים שהקמת הסניפים בהם צפוייה למקסם את הרווחיות. אנא הוכח נכונות ונתח סיבוכיות.
תשובה
עריכהראשית נניח שהמערך M
ממויין, או, לחלופין, נמיין אותו בעזרת מיון מיזוג בסיבוכיות .
נגדיר כ את מירב הרווח שאפשר להרוויח מפתיחת סניפים הלקוחים מתוך הבתים הראשונים.
משפט: לפי הגדרת :
|
הוכחה: (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 &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 אם ישבצו לו עובדות. הנח:
- פונקציה לא שלילית (אין איכות שלילית).
- מונוטונית לא-יורדת ב (הוספת עובדות לפרוייקט אינה מורידה מאיכותו).
- ניתן להקצות 0 עובדות לפרוייקט.
- כל עובדת מוקצת לפרוייקט אחד בדיוק.
לכל פרוייקט יש "חשיבות" לא-שלילית . אנו רוצים למקסם את סך האיכויות המשוקללות. במילים אחרות, אנו רוצים למקסם את .
אנא הצע אלגוריתם יעיל לפתרון הבעיה, כלומר אלגוריתם שימצא את הסכום הנ"ל המקסימלי וכן ידפיס את אופן הקצאת העובדות לכל פרוייקט.
הנח ש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)
פשוט תחזיר את המערך ממויין בסדר עולה. (אם נשתמש במיון מיזוג, אז הסיבוכיות תהיה ).
נניח שהמערך המקורי הוא , והמערך הממויין הוא .
כל תת-מחרוזת עולה של , נניח , היא תת-מחרוזת משותפת ל ו : היא בהכרח תת-מחרוזת של לפי ההגדרה, והיא תת-מחרוזת של