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

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

< מבני נתונים ואלגוריתמים - מחברת קורס | גרפים | חיפוש רוחבי

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

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

תוכן עניינים

1 סדר הדפסת הצמתים וזמן הריצה
- 1.1 שאלה
- 1.2 תשובה
  - 1.2.1 סדר ההדפסות
  - 1.2.2 ניתוח זמן הריצה
2 זמן הריצה ברכיב קשירות קטן
- 2.1 שאלה
- 2.2 תשובה
3 "חיפוש רוחבי" עם שק במקום תור
- 3.1 שאלה
- 3.2 תשובה
  - 3.2.1 הדפסה לפי הסדר
  - 3.2.2 הדפסת כל הצמתים פעם יחידה
4 חלוקת סטודנטים לשתי כיתות
- 4.1 שאלה
- 4.2 תשובה

[עריכה] סדר הדפסת הצמתים וזמן הריצה

[עריכה] שאלה

להלן גרסה של אלגוריתם החיפוש הרוחבי:

BFS(G, s)
1	q = Make-Queue()
 
2	Visited = Make-Array( |V| )
 
3	for u in V
4		Visited[u] = False
 
5	Print s
6	Visited[s] = True
7	Enqueue(q, s)
 
8	while not Empty(q)
9		u = Dequeue(q)
 
10		For every neighbor v of u
11			if Visited[v] == False
12				Print v
13				Visited[v] = True
14				Enqueue(q, v)

גרסה זו עוברת על כל הצמתים ברכיב הקשירות של $\displaystyle s$ ומדפיסה אותם לפי סדר ההגעה מ $\displaystyle s$ .

להלן גרף $\displaystyle G$ שבו צומת המוצא הוא $\displaystyle s$ .

הנח שבשורה 10, אם לצומת $\displaystyle u$ יש יותר משכן יחיד, סדר הצמתים הוא כסדרם המספרי.

באיזה סדר יודפסו האיברים?
נניח ש $\displaystyle G = (V, E)$ קשיר מ $\displaystyle s$ (יש מסלול מ $\displaystyle s$ לכל צומת). אנא הוכח שהאלגוריתם יעבוד בזמן $\displaystyle \Theta(|V| + |E|)$ .

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

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

תחילה יודפס 1 כמובן.
באיטרציה הראשונה של 8-14, התור יכיל את 1.‏ 10-14 ידפיסו את 2 ו6 ויכניסו אותם לתור (בסדר הזה).
באיטרציה השניה, 2 יהיה בראש התור. 3 יודפס ויוכנס לתור.
באיטרציה השלישית, 6 יהיה בראש התור. 5 ו7 יודפסו ויוכנסו לתור (בסדר הזה). כעת התור יכיל את 3, 5, ו7 (3 בראש התור)
נמשיך כך הלאה.

הצמתים יודפסו בסדר הבא (משמאל לימין): $\displaystyle 1, 2, 6, 3, 5, 7, 4$ .

[עריכה] ניתוח זמן הריצה

1-2 ו5-7 הן $\displaystyle O(1)$
3-4 הן $\displaystyle \Theta(|V|)$ .
הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת. בפרט, הבדיקה ב8 והפעולה ב9 עולות $\displaystyle \Theta(|V|)$ .
באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג $\displaystyle u, v$ כך ש $\displaystyle (u, v) \in E$ . הלולאה תורמת לכן $\displaystyle \Theta(|E|)$ .

שימו לב:

חשוב להבין שלמרות שהלולאה 10-14 נמצאת בתוך הלולאה 8-14, זמן הריצה של 10-14 אינו המכפלה $\displaystyle \Theta(|V|\cdot|E|)$ .

ניזכר בניתוח זמן הריצה של לולאות. הלולאה החיצונית רצה על כל הצמתים. הלולאה הפנימית רצה, לכל צומת, על הקשתות היוצאות ממנה. לכן הלולאה הפנימית רצה בדיוק $\displaystyle \Theta(|E|)$ פעמים.

הסיבוכיות, לכן, היא $\displaystyle O(1) + \Theta(|V|) + \Theta(|V|) + \Theta(|E|) = \Theta(|V| + |E|)$ .

[עריכה] זמן הריצה ברכיב קשירות קטן

[עריכה] שאלה

נחזור שוב לאלגוריתם בשאלה סדר הדפסת הצמתים וזמן הריצה, אך כעת נניח שיש מסלול מ $\displaystyle s$ רק ל $\displaystyle |V|^{\alpha}$ מהצמתים, כאשר $\displaystyle \alpha < 1$ הוא קבוע כלשהו.

האם זמן הריצה הוא בהכרח $\displaystyle \Theta(|V| + |E|)$ ?
האם ייתכן שזמן הריצה הוא $\displaystyle \Theta(|V| + |E|)$ ?

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

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

[עריכה] "חיפוש רוחבי" עם שק במקום תור

[עריכה] שאלה

נתון טיפוס אבסטרקטי "שק" בעל הממשק הבא:

#Makes a new sack.
Make-Sack()
 
# Inserts an element (v) to a sack (ks).
Insert(k, v)
 
# Returns whether the sack is empty.
Empty(k)
 
# Deletes *some* element from a (non-empty) sack (k) and returns the value of 
#	the deleted element.
Delete(k)

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

להלן ווריאציה אפשרית של אלגוריתם החיפוש הרוחבי, אך כעת עם שק במקום תור:

Sack-Search(G, s)
1	k = Make-Sack()
 
2	Visited = Make-Array( |V| )
 
3	for u in V
4		Visited[u] = False
 
5	Print s
6	Visited[s] = True
7	Insert(k, s)
 
8	while not Empty(q)
9		u = Delete(k)
 
10		For every neighbor v of u
11			if Visited[v] == False
12				Print v
13				Visited[v] = True
14				Insert(k, v)

נניח שהגרף קשיר מ $\displaystyle s$ (יש מסלול מ $\displaystyle s$ לכל צומת).

האם Sack-Search בהכרח ידפיס כל צומת בדיוק פעם יחידה?
האם סדר ההדפסות בהכרח יהיה לפי מרחק הצמתים מ $\displaystyle s$ ?

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

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

הטענה איננה נכונה. קל למצוא דוגמאות נגדיות.

דוגמה:

נניח שהגרף הוא המתואר בתרשים הבא.

בגרף זה, סדר ההדפסות יכול להיות (משמאל לימין): $\displaystyle 1, 2, 3, 4, 6, 7, 5$ .

עכשיו תורך:

וודא שהנך מסוגל להראות סידרה אפשרית של תוצאות Delete שיביאו לתוצאה האמורה.

[עריכה] הדפסת כל הצמתים פעם יחידה

הטענה נכונה.

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

נוכיח שכל צומת מודפס ומוכנס לשק במהלך הריצה. ההוכחה היא באינדוקציה על $\displaystyle \ell$ , מרחק הצומת מ $\displaystyle s$ .

(בסיס האינדוקציה) עבור $\displaystyle \ell = 0$ הטענה בוודאי נכונה. יש רק צומת אחד שמרחקו מ $\displaystyle s$ הוא 0, $\displaystyle s$ עצמו, ו $\displaystyle s$ מודפס ב5 ומוכנס לשק ב7.

(מעבר האינדוקציה) נניח שהטענה נכונה לכל צומת שמרחקו מ $\displaystyle s$ הוא לכל היותר (לא כולל) $\displaystyle \ell$ . נתבונן כעת בצומת $\displaystyle v$ כלשהו שמרחקו מ $\displaystyle s$ הוא $\displaystyle \ell$ . אם כך, בהכרח קיים צומת $\displaystyle$ כך שיש מסלול מ $\displaystyle s$ ל $\displaystyle u$ באורך $\displaystyle \ell - 1$ , ו $\displaystyle v$ שכן של $\displaystyle u$ . מהנחת האינדוקציה, $\displaystyle u$ מתישהו יודפס ויוכנס לשק. שורה 9, לכן, מבטיחה גם ש $\displaystyle u$ מתשיהו יוצא מהשק. הלולאה 10-14 עוברת על כל שכני $\displaystyle u$ , ובפרט $\displaystyle v$ . האפשרות היחידה לפיה 12 לא תדפיס את $\displaystyle v$ היא ש11 נכשלה. אם 11 נכשלה, אבל, אז בהכרח $\displaystyle v$ כבר הודפסה והוכנסה לתור (רק שורה 13 יכולה לקבוע את הערך בVisited לTrue). לכן, בכל מקרה, $\displaystyle v$ בהכרח מודפסת ומוכנסת לתור.

[עריכה] חלוקת סטודנטים לשתי כיתות

[עריכה] שאלה

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

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

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

נתרגם את הבעיה לתורת הגרפים. נציג כל סטודנט כצומת, ונמתח קשת בין כל שני צמתים אם הם מתארים סטודנטים שלמדו בזוג. ההנחה שכל שני סטודנטים למדו "לפחות בעקיפין" זה עם זה מתורגמת לכך שהגרף קשיר. כעת נשים לב שהשאלה הופכת להיות האם ניתן לצבוע כל צומת בגרף באדום או שחור, כך שם יש קשת בין שני צמתים - צבעם שונה. יותר מכך: אם ניקח צומת כלשהו $\displaystyle s \in V$ , נובע מסימטריה שהשאלה שקולה לשאלה האם אפשר לצבוע את הגרף לפי הכללים האמורים לעיל כך ש $\displaystyle s$ ייצבע בשחור דווקא.

נאמר שצביעה היא חוקית אם:

$\displaystyle s$ צבוע שחור.
אין שני צמתים שביניהם קשת הצבועים באותו צבע.

להלן אלגוריתם הבודק האם לגרף קיימת צביעה חוקית.

Legal-Coloring(G, s)
1	q = Make-Queue()
 
2	Color = Make-Array( |V| )
 
3	for u in V
4		Color[u] = Nil
 
5	Color[s] = Black
6	Enqueue(q, s)
 
7	while not Empty(q)
8		u = Dequeue(q)
 
9		For every neighbor v of u
10			if Color[v] == Nil
11				Color[v] = (Color[u] == Black)? Red: Black
12				Enqueue(q, v)
13			else if Color[u] == color[v]
14				return False
 
15	return True

משפט:

בכל פעם שצומת $\displaystyle v$ מקבל צבע (אדום או שחור), אז בצביעה חוקית חייב צבעו של $\displaystyle v$ להיות הצבע שאותו קיבל.

הוכחה: ההוכחה היא באינדוקציה על האיטרציה של הלולאה 9-14.

(בסיס האינדוקציה) בתחילת האיטרציה הראשונה, רק $\displaystyle s$ קיבל צבע (שחור). על $\displaystyle s$ לקבל את הצבע שחור בצביעה חוקית, ו $\displaystyle s$ אכן מקבל את הצבע שחור בשורה 5.

(מעבר האינדוקציה) נניח שהטענה נכונה עד (לא כולל) לאיטרציה ה $\displaystyle i$ . באיטרציה זו מוצא $\displaystyle u$ מהתור בשורה 8. מכאן ברור שהוא קיבל את צבעו לפני איטרציה זו, ומהנחת האינדוקציה - צבעו הוא זה שבו הוא חייב להיות צבוע בצביעה חוקית. נתבונן כעת בצומת $\displaystyle v$ . הצומת חייב לקבל את צבעו ב11, כאשר הוא מקבל צבע הפוך לצבעו של $\displaystyle u$ . אבל היות שיש קשת בין $\displaystyle u$ ל $\displaystyle v$ , $\displaystyle v$ בהכרח חייב לקבל את הצבע ההפוך לצבעו של $\displaystyle u$ , ואכן שורה 11 עושה בדיוק זאת.

כעת נוכיח 14 מחזירה False - בהכרח אין צביעה חוקית.

הוכחה: 14 מתקיימת כאשר מאתרים קשת $\displaystyle (u, v) \in E$ בעוד של $\displaystyle u$ ול $\displaystyle v$ אותו צבע. אבל מהטענה הקודמת נובע שלו היתה צביעה חוקית, כל אחד משני הצמתים הנ"ל אכן צבוע בצבע בו הוא חייב להיות צבוע. היות שצבעיהם זהים ויש קשת ביניהם - בהכרח אין צביעה חוקית.

כעת נוכיח שאם 16 מחזירה True - בהכרח יש צביעה חוקית.

הוכחה: נניח בשלילה ש16 החזירה True אך הצביעה אינה חוקית. הצומת $\displaystyle s$ בוודאי צבוע שחור בסוף הריצה, ולכן חייבים להיות שני צמתים, $\displaystyle u$ ו $\displaystyle v$ , הצבועים באותו צבע למרות שיש קשת המחברת ביניהם. אחד משני הצמתים קיבל את צבעו לאחר השני, נניח שמדובר ב $\displaystyle u$ . נשים לב ש9 היתה עוברת גם על $\displaystyle v$ , ו13 היתה מזהה שהם צבועים באותו צבע, ולכן בהכרח 14 היתה מחזירה False. לא ייתכן, על כן, ש16 החזירה True.

עכשיו תורך:

האם האלגוריתם היה עובד לו היינו משתמשים בשק מהשאלה "חיפוש רוחבי" עם שק במקום תור? (בין הפותרים נכון יוגרל שק).

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

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

תוכן עניינים

[עריכה] סדר הדפסת הצמתים וזמן הריצה

[עריכה] שאלה

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

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

[עריכה] ניתוח זמן הריצה

[עריכה] זמן הריצה ברכיב קשירות קטן

[עריכה] שאלה

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

[עריכה] "חיפוש רוחבי" עם שק במקום תור

[עריכה] שאלה

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

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

[עריכה] הדפסת כל הצמתים פעם יחידה

[עריכה] חלוקת סטודנטים לשתי כיתות

[עריכה] שאלה

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

צפיות

כלים אישיים

ניווט

קהילה

חיפוש

תיבת כלים

הדפסה/ייצוא