מבני נתונים ואלגוריתמים - מחברת קורס/מבחן סופי מועד א' סמסטר קיץ 2007 - תשובות

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

שאלה 1

ראשית נבנה את רשת הזרימה המתוארת בתרשים הבא. בגרף זה $\displaystyle m+n+2$ צמתים:

1. צמתים $\displaystyle s_{1},\ldots s_{m}$, אחד לכל סטודנט
2. צמתים $\displaystyle t_{1},\ldots t_{n}$, אחד לכל חברה
3. צומת מקור $\displaystyle s$ וצומת בור $\displaystyle t$

נגדיר כ$\displaystyle w$ את Length(W).

בגרף יש $\displaystyle w+m+n$ קשתות:

1. קשת אחת לכל איבר בW בעלת קיבול 1
2. קשת מ$\displaystyle s$ לכל $\displaystyle s_{i}$ בעלת קיבול 1
3. קשת מכל $\displaystyle t_{j}$ ל$\displaystyle t$ בעלת קיבול $\displaystyle P[j]$

.

כעת נריץ את אלגוריתם Ford-Fulkerson. נחזיר כתשובה כל זוג $\displaystyle (s_{i},t_{j})$ שעבורו קיבלנו $\displaystyle f_{s_{i},t_{j}}=1$.

משפט: האלגוריתם מחזיר תשובה נכונה.

הוכחה: אנו יודעים שאלגוריתם Ford-Fulkerson משפר תמיד בגדלים שלמים (שהרי הקיבולים שלמים). קל מאד להוכיח (פורמלית, באינדוקציה), שבמקרה זה, חלק מהקשתות מ$\displaystyle s_{i}$ ל$\displaystyle t_{j}$ יזרימו 1, והשאר 0 (אלו האפשרויות היחידות). נצייר את הגרף המתקבל ממחיקת הקשתות שאינן מזרימות כלום:

.

נניח שיש קשת בין $\displaystyle s_{i}$ ל$\displaystyle t_{j}$. בהכרח הקשת מזרימה 1. מצד שני, הקשת המזרימה מ$\displaystyle s$ ל$\displaystyle s_{i}$ מזרימה גם היא 1. משימור הזרם נובע אם כן שאין קשת אחרת היוצאת מ$\displaystyle s_{i}$.טענה כמעט זהה מראה שאין קשת אחרת הנכנסת ל$\displaystyle t_{j}$. ברור גם שקשת זו היתה שייכת לגרף המקורי. מכאן נובע שהמערך המוחזר W' אכן משייך אחת לאחת סטודנט לחברה, ואינו ממציא שיוכים שלא הופיעו במקור. קל גם לראות שכל חברה אינה מעסיקה יותר סטודנטים מיכולתה. קל לראות שאם יש התאמה גדולה יותר, אז אפשר להגיע לזרימה גדולה יותר מהמושגת כאן, וזאת בסתירה לנכונות Ford-Fulkerson.

משפט: סיבוכיות האלגוריתם $\displaystyle O((m+n+w)\cdot \min\{m,n,w\})$.

הוכחה: אם משתמשים ברשימת שכנויות, אז בניית הגרף החדש היא $\displaystyle \Theta (m+n+w)$.כבר ראינו בניתוח אלגוריתם Ford-Fulkerson, שסיבוכיותו לינארית במספר הקשתות כפול גודל הזרימה המירבית. מספר הקשתות כאן הוא $\displaystyle m+n+w$, והזרימה המירבית היא $\displaystyle \min\{m,n,w\}$

שאלה 2

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

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

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

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

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

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

מימוש נאיבי

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

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

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

שימוש בmemoization

נוסיף memoization.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

שאלה 3

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

נניח שזהו הגרף המקורי:

הבעיה המקורית.

נבנה גרף חדש כך.

ראשית, נקח את צמתי הגרף $\displaystyle V$, ונשכפל אותם 3 פעמים, בקבוצות $\displaystyle A$,‏ $\displaystyle B$, ו$\displaystyle C$. לכל צומת $\displaystyle u$ בקבוצה $\displaystyle A$, יש צומת $\displaystyle |V|+u$‏ ב$\displaystyle B$,‏ וצומת ‏ $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.‏ התרשים הבא מראה זאת.

שכפול הצמתים.

כעת נוסיף גם קשתות:

1. במקום כל קשת $\displaystyle (u,v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל$\displaystyle u$ ב$\displaystyle A$ לצומת המתאים ל$\displaystyle v$ ב$\displaystyle A$.
2. במקום כל קשת $\displaystyle (u,v)$ בגרף המקורי, למעט הקשת השלילית, נמתח קשת מהצומת המתאים ל$\displaystyle u$ ב$\displaystyle B$ לצומת המתאים ל$\displaystyle v$ ב$\displaystyle B$.
3. במקום הקשת השלילית $\displaystyle (x,y)$ (בגרף המקורי), נמתח קשת מהצומת המתאים ל$\displaystyle x$ ב$\displaystyle A$ לצומת המתאים ל$\displaystyle y$ ב$\displaystyle B$ במחיר 0. התרשים הבא מראה זאת.

הוספת הקשתות.

נניח שלקשת השלילית היה מחיר $\displaystyle -z$. בנוסף נמתח עוד שני סוגי קשתות:

1. לכל צומת $\displaystyle u$ ב$\displaystyle A$, נמתח קשת במחיר $\displaystyle z$ בין $\displaystyle u$ ב$\displaystyle A$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.
2. לכל צומת $\displaystyle u$ ב$\displaystyle B$, נמתח קשת במחיר 0 בין $\displaystyle u+|V|$ ב$\displaystyle B$ לבין $\displaystyle 2\cdot |V|+u$ ‏ ב$\displaystyle C$.(לא נצייר קשתות אלו מטעמי נוחות.)

נשים לב שאם כל הגרפים הנ"ל מיוצגים ברשימת שכנויות, אז סיבוכיות הבניה היא $\displaystyle \Theta (|V|+|E|)$.

המשפט הבא מסביר את חשיבות הגרף החדש.

משפט: מחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ בגרף המקורי, קטן בדיוק ב$\displaystyle z$ ממחיר המסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle 2\cdot |V|+u$ ב$\displaystyle C$ בגרף החדש.

הוכחה: בגרף המקורי, ייתכן שהמסלול הזול ביותר מ$\displaystyle s$ ל$\displaystyle u$ לא השתמש בקשת השלילילת, וייתכן שהשתשמש בו. במקרה הראשון, תהיה קפיצה מ$\displaystyle A$ ישירות ל$\displaystyle C$, ובמקרה השני, תהיה קפיצה מ$\displaystyle A$ ל$\displaystyle B$ ומ$\displaystyle B$ ל$\displaystyle C$. הקפיצה מ$\displaystyle A$ ישירות ל$\displaystyle C$ עולה $\displaystyle z$ יותר מאשר המסלול המקורי. הקפיצות מ$\displaystyle A$ ל$\displaystyle B$ ומ$\displaystyle B$ ל$\displaystyle C$ גם כן עולות $\displaystyle z$ יותר מאשר המסלול המקורי, שכן עלות כל אחת משתי הקשתות היא 0, והנוסע לא קיבל את התשלום $\displaystyle z$ מהחברה.

כעת כל הקשתות אינן שליליות, ומותר להריץ את Dijkstra.

קל לראות שהסיבוכיות הכוללת היא זו של Dijkstra.

שאלה 4

1. הטענה נכונה. נניח שבערימה יש $\displaystyle s$ איברים. האיבר האחרון בערימה הוא באינדקס $\displaystyle s$, ואביו (אם יש לו) בהכרח יושב ב$\displaystyle \left\lfloor {\frac {s}{2}}\right\rfloor$. לכן, למרות שהלולאה אינה עוברת על כל האיברים, היא מדלגת רק על ערימות בעלי איבר יחיד, שהן, עפ"י תכונת הערימה, תקינות. הלולאה תתקן כל ערימה שדורשת תיקון, בדיוק מהסיבה שראינו בהרצאה. הסיבוכיות היא $\displaystyle \Theta (n)$. אפשר לראות שהלולאה עוברת על חצי מהאיברים, ולכן היא $\displaystyle \Omega (n)$. מצד שני, היא עושה פחות מBuild-Heap, וזו היתה $\displaystyle O(n)$, ולכן גם לולאה זו $\displaystyle O(n)$.
2. הטענה נכונה. אם ילדו השמאלי של איבר במקום $\displaystyle i$ נמצא באינדקס $\displaystyle 2\cdot i$, וילדו הימני נמצא באינדקס $\displaystyle 2\cdot i+1$, אז כל מסלול מהשורש לעלה עובר על סדרת אינדקסים מונוטונית עולה. לכן, אם המערך ממויין, כל מסלול מהשורש לעלה יעבור על סדרת ערכים מונוטונית לא-יורדת. הסיבוכיות הנה מיון מיזוג, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$.
3. הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [3,4,2,1]$. הסיבוכיות הנה $\displaystyle \Theta (n)$, בדיוק מהניתוח שכבר ראינו לגבי הפתרון מההרצאה.
4. הטענה נכונה. היות ש Bubble-Up(bh, i) אינו יכול להשפיע על איברים באינדקס מעל $\displaystyle i$, הקוד שקול לסדרת פעולות Insert. מאותה סיבה, הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$.
5. הטענה אינה נכונה, ומפורכת (לדוגמה) ע"י $\displaystyle [4,1,2,3]$. הסיבכויות היא זו של סדרת פעולות Insert, כלומר $\displaystyle \Theta \left(n\cdot \log(n)\right)$.