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

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

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

שאלה[עריכה]

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

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)

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

להלן גרף שבו צומת המוצא הוא .

בעיית החיפוש הרוחבי.

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

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

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

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

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

הצמתים יודפסו בסדר הבא (משמאל לימין): .

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

  • 1-2 ו5-7 הן
  • 3-4 הן .
  • הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת. בפרט, הבדיקה ב8 והפעולה ב9 עולות .
  • באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג כך ש. הלולאה תורמת לכן .


שימו לב:

חשוב להבין שלמרות שהלולאה 10-14 נמצאת בתוך הלולאה 8-14, זמן הריצה של 10-14 אינו המכפלה .

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

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


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

שאלה[עריכה]

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

  1. האם זמן הריצה הוא בהכרח ?
  2. האם ייתכן שזמן הריצה הוא ?



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

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

  • 1-2 ו5-7 הן
  • 3-4 הן .
  • הלולאה 8-14 מתבצעת בדיוק פעם אחת עבור כל צומת ב. בפרט, הבדיקה ב8 והפעולה ב9 עולות .
  • באופן דומה, הלולאה 10-14 מתבצעת בדיוק פעם אחת עבור כל זוג כך ש. הלולאה תורמת לכן .

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

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


הכרח[עריכה]

הנה משפט עזר בו נשתמש:


משפט:

לכל ,‏


הוכחה: נשתמש בכללי גבולות וסדרי גדילה:






מש"ל.PNG

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

רכיב קשירות קטן.

מספר הקשתות בגרף הוא



הסיבוכיות היא רק , וקל לראות שביטוי זה אינו .

התכנות[עריכה]

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

רכיב קשירות קטן.


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

שאלה[עריכה]

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

#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)

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

  1. האם Sack-Search בהכרח ידפיס כל צומת בדיוק פעם יחידה?
  2. האם סדר ההדפסות בהכרח יהיה לפי מרחק הצמתים מ?

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

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

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



דוגמה:

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

בעיית החיפוש הרוחבי.

בגרף זה, סדר ההדפסות יכול להיות (משמאל לימין): .


עכשיו תורכם:

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


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

הטענה נכונה.


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

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

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

(מעבר האינדוקציה) נניח שהטענה נכונה לכל צומת שמרחקו מ הוא לכל היותר (לא כולל) . נתבונן כעת בצומת כלשהו שמרחקו מ הוא . אם כך, בהכרח קיים צומת הפענוח נכשל (שגיאת המרה. השרת ("https://wikimedia.org/api/rest_") השיב: "Cannot get mml. Expected width > 0."): {\displaystyle \displaystyle } כך שיש מסלול מ ל באורך , ו שכן של . מהנחת האינדוקציה, מתישהו יודפס ויוכנס לשק. שורה 9, לכן, מבטיחה גם ש מתשיהו יוצא מהשק. הלולאה 10-14 עוברת על כל שכני , ובפרט . האפשרות היחידה לפיה 12 לא תדפיס את היא ש11 נכשלה. אם 11 נכשלה, אבל, אז בהכרח כבר הודפסה והוכנסה לתור (רק שורה 13 יכולה לקבוע את הערך בVisited לTrue). לכן, בכל מקרה, בהכרח מודפסת ומוכנסת לתור.

מש"ל.PNG


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

שאלה[עריכה]

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

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

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

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

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

  • צבוע שחור.
  • אין שני צמתים שביניהם קשת הצבועים באותו צבע.

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

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



משפט:

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


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

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

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

מש"ל.PNG

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


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

מש"ל.PNG

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


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

מש"ל.PNG


עכשיו תורכם:

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