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

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

הגדרה:

שתי קבוצות, $\displaystyle S_{1}$ , $\displaystyle S_{2}$ ,‏‏ זרות אם אין להם איברים משותפים: $\displaystyle S_{1}\bigcap S_{2}=\emptyset$ .

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

כדאי לדעת:

*פתרון בעיה זו חשוב משתי סיבות:

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

מימוש C++

boost::disjoint_sets

הבעיה

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

דוגמה:

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

$\displaystyle 1$ ו $\displaystyle 2$ מחליטים ללמוד ביחד.
$\displaystyle 3$ ו $\displaystyle 4$ מחליטים ללמוד ביחד.
$\displaystyle 5$ ו $\displaystyle 6$ מחליטים ללמוד ביחד.
$\displaystyle 2$ ו $\displaystyle 5$ מחליטים ללמוד ביחד.
$\displaystyle 8$ ו $\displaystyle 2$ מחליטים ללמוד ביחד.

לבסוף, לכן, קבלנו את הקבוצות הזרות $\displaystyle \{1,2,5,6,8\},\{3,4\},\{7\}$ :

נרצה להיות מסוגלים, בהינתן $\displaystyle 1$ ו $\displaystyle 7$ לדוגמה, לענות האם הם שייכים לאותה קבוצה (במקרה זה - לא).

ממשק

הפסוודו-קוד הבא מראה את הממשק של מבנה הנתונים שבו נשתמש לבעיה כזו שראינו:

# Makes a set.
Make-Set()

# Finds a set by a "representative" (u).
Find-Set(u)

# Joins two sets by their "representatives" (u, v).
Union(u, v)

הנה הפסוודו-קוד המראה כיצד להשתמש בממשק:

1	t1 = Make-Set()
2	t2 = Make-Set()
3	t3 = Make-Set()
4	t4 = Make-Set()
5	t5 = Make-Set()
6	t6 = Make-Set()
7	t7 = Make-Set()
8	t8 = Make-Set()
	
9	Union(t1, t2)
10	Union(t3, t4)
11	Union(t5, t6)	
12	Union(t2, t5)
13	Union(t8, t2)

	# Prints True.
14	Print( Find-Set(t1) == Find-Set(t6) )

	# Prints False.
15	Print( Find-Set(t1) == Find-Set(t7) )

הגדרה:

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

ממשק (interface) - מה המבנה עושה
מימוש (implementation) - איך המבנה עושה זאת

אלה המושגים הנהוגים בהנדסת תכנה. בתחום מבני הנתונים והאלגוריתמים, לפעמים קוראים למבנה נתונים שרק הממשק שלו הוצג - ADT, או abstract data type.‏

הנחות ומטרה

נתבונן בסדרת פעולות שכ"א מהן היא Make-Set, ‏Union, או Find-Set.

נגדיר את $\displaystyle m$ כמספר הפעולות בסדרה.
נגדיר את $\displaystyle n$ כמספר פעולות Make-Set בסדרה (נשים לב שבהכרח $\displaystyle n\leq m$ ).

דוגמה:

בדוגמה הקודמת שראינו היו 8 פעולות Make-Set, 5 פעולות Union, ו4 פעולות Find-Set. בדוגמה זו, לכן, $\displaystyle m=8+5+4=17$ , ו $\displaystyle n=8$ .

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

מטרתנו היא למצוא מימוש כך שסדרת הפעולות תעלה סה"כ $\displaystyle O(n\log(n)+m)$ במקרה הגרוע (אם כי, במימושים אחרים נראה שאפשר אף להגיע ליעילות טובה יותר).

מימוש רשימות נאיבי

הרעיון הכללי

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

`Make-Set`

הנה הפסוודו-קוד ל Make-Set:

	# A global array of n Linked-lists.
1	Lists = Make-Array(n)

	# A global variable indicating how many sets were made.
2	size = 0


# Makes a set.
Make-Set()
	# Make a new list.
1	Lists[++size] = Make-List()

	# Insert in a link whose value is size.
2	Insert-Front(Lists[size], size)

	# Return the (pointer to the) first link.
3	return Lists[size].front

המערך הגלובאלי Lists (בשורה 1) משמש לשמירת הרשימות - Lists הוא מערך של רשימות מקשורת. המשתנה הגלובאלי size (בשורה 2) מתאר כמה קבוצות כבר ייצרנו; 1 + size תמיד יהיה אינדקס המערך בו ניצור את הרשימה הבאה.

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

דוגמה:

בדוגמה שלעיל היתה השורה

1	t1= Make-Set()}}

הנה המבנה לאחר שורה זו:

המערך Listsהוא מערך של רשימות מקושרות (אם כי אנו נצייר רק את חוליות הרשימה). כאן יש רשימה אחת (רק החוליה שלה מצויירת). לרשימה חוליה בודדת, שבה הערך 1.‏ t1מצביע לחוליה זו.

דוגמה:

בדוגמה שלעיל היתה השורה

8	t8= Make-Set()}}

הנה המבנה לאחר שורה זו:

שוב, המערך Lists הוא מערך של רשימות מקושרות (אם כי אנו נצייר רק את חוליות הרשימה). כאן יש 8 רשימות (רק החוליות שלהן מצויירות). לכל רשימה חוליה בודדת, ובהן הערכים 1, ..., 8.‏ t1, ..., t8מצביעים לחוליות אלו.

`Union`

נניח שרוצים לאחד שתי קבוצות, uו v (ע"י Union(u, v)).

ראשית נמצא את הרשימות המקשורות המתאימות. נזכור ש uהיא חוליה של רשימה מקושרת, ובהמשך נראה שהערך בה הוא אינדקס הרשימה המקושרת במערך הגלובאלי Lists. נקבע, לכן, l_u= Lists[u.value]. בדיוק באותו אופן נקבע l_v= Lists[v.value]. כעת אנו רוצים לאחד את שתי הרשימות לרשימה אחת גדולה, כך שהרשימה המאוחדת יושבת במקום בו ישבה l_u, וערכי כל חוליותיה אכן מעידים על כך. נעשה זאת בשני שלבים:

ברשימה המקושרת l_v, נעבור בלולאה ונשנה את ערכי כל האיברים לu.value.
נאחד את שתי הרשימות המקושרות l_u, ו l_v, כך ש l_uתקבל את כל החוליות, ו l_v תאבד את החוליות שלה (כלומר תהפוך לריקה).

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

# Joins two sets by their "representatives" (u, v).
Union(u, v)
1	l_u = Lists[u.value]
2	l_v = Lists[v.value]

	# Set all values in l_v to be u.value.
	# (This is one lf List's utility functions).	
3	List-Set-All(l_v, u.value)
	
	# l_u becomes a list whose links are the union of the links
	# 	of (the old) l_u and l_v.
	# 	l_v becomes the empty list.
	# (This is one of List's utility functions).	
4	List-Union(l_u, l_v)

הנה שתי פונקציות העזר:

# Takes a list (l) and a value (v).
# Modifies all the links in the list so that their value is v.
List-Set-All(l, v)
1	lnk = l.front

2	while lnk != Nil
3		lnk.value = v
4		lnk = lnk.next

# Takes two lists (l1, l2).
# Modifies them so that all the links are in the first list (l1),
#	and the second list (l2) is empty.
List-Union(l1, l2)
1	if l1.back != Nil
2		l1.back.next = l2.front
3	if l2.front != Nil
4		l2.front.prev = l1.back

5	l1.back = l2.back
6	l1.size = l1.size + l2.size

7	l2.front = l2.back = Nil
8	l2.size = 0

דוגמה:

בדוגמה שלעיל היתה השורה Union(t1, t2). חלקו העליון של התרשים הבא מראה את המצב לפני השורה (לשם הפשטות, t3, ..., t8 אינם מצויירים). חלקו התחתון של התרשים מראה את המצב לאחר השורה.

דוגמה:

בדוגמה שלעיל היתה השורה Union(t2, t8). חלקו העליון של התרשים הבא מראה את המצב לפני השורה (לשם הפשטות, t3, ..., t8אינם מצויירים). חלקו התחתון של התרשים מראה את המצב לאחר השורה.

האינווריאנטה

מהתבוננות במימוש שתי הפעולות שראינו, קל לזהות את האינווריאנטה הבאה.

משפט:

אם u מצביעה לחוליה, וu.value == j, אז החוליה שייכת לרשימה המקושרת שנמצאת בLists[j].

המשפט אומר למעשה את הדבר הבא. כל החוליות ברשימה המקושרת של Lists[1] בעלות הערך 1 בvalue, כל החוליות ברשימה המקושרת של Lists[2] בעלות הערך 2 בvalue, וכולי.

ראשית, קל לראות שהדבר נכון לכל חוליה שנוצרה כרגע ע"י Make-Set.

הוכחה: Make-Set מייצרת חוליה שערך הvalue שלה הוא size. היא מכניסה חוליה זו לרשימה בLists[size].

כעת נוכיח את המשפט באינדוקציה.

הוכחה: ההוכחה היא באינדוקציה על מספר הפעולה בסדרה, $\displaystyle i$ .

(בסיס האינדוקציה) עבור $\displaystyle i=1$ , הטענה בהכרח נכונה. הפעולה הראשונה בסדרת הפעולות היא מסוג Make-Set (הפעולות משני הסוגים האחרים מקבלות ערכים מוחזרים מMake-Set). ראינו זה עתה הוכחה לטענה עבור Make-Set.

(מעבר האינדוקציה) נניח שהטענה נכונה עד (לא כולל) לפעולה ה $\displaystyle i$ , ונתבונן בפעולה ה $\displaystyle i$ . אם הפעולה מסוג Make-Set, אז הטענה ממשיכה להתקיים. נניח לכן שהפעולה היא מהצורה Union(u, v). אם ערך u.value הוא $\displaystyle p$ , אז, מהנחת האינדוקציה, החוליה נמצאת בLists[p]. באותו אופן, אם ערך v.value הוא $\displaystyle q$ , אז, מהנחת האינדוקציה, החוליה נמצאת בLists[q]. הפעולה Union(u, v) קובעת את הערכים בחוליות Lists[q] ל $\displaystyle p$ , ותעביר אותן לLists[p]. לכן הטענה תמשיך להתקיים לאחר הפעולה ה $\displaystyle i$ .

ניתוח

קל להווכח בדברים הבאים:

משפט:

סיבוכוית Make-Setהיא $\displaystyle O(1)$ .
סיבוכוית Find-Setהיא $\displaystyle O(1)$ .
סיבוכוית Unionהיא $\displaystyle \Theta (n')$ במקרה הגרוע, כאשר $\displaystyle n'$ הוא גודל הקבוצה הגדולה מבין שתי הקבוצות שמאחדים.

מכאן קל לראות שמימוש זה אינו מתאים לדרישותינו המקוריות:

משפט:

מימוש זה אינו פועל תמיד בזמן $\displaystyle O(n\log(n)+m)$ .

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

`Find-Set`

כעת נותר לממש את Find-Set(u), אבל זה קל: לפי האינווריאנטה שזה עתה ראינו, פשוט מחזירים את u.value.

# Finds a set by a "representative"(u).
Find-Set(u)
1	return u.value

מימוש רשומות עם איחוד עפ"י גודל

הרעיון הכללי

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

`Union`

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

# Joins two sets by their "representatives" (u, v).
Union(u, v)
1	l_u = Lists[u.value]
2	l_v = Lists[v.value]

3	if Size(l_u) < Size(l_v) 
		# Exchange the lists.
4		l_u <-> l_v

	# Set all values in l_v to be u.value.
	#
	# (This is one lf List's utility functions).	
5	List-Set-All(l_v, u.value)
	
	# l_u becomes a list whose links are the union of the links
	# 	of (the old) l_u and l_v.
	# 	l_v becomes the empty list.
	#
	# (This is one lf List's utility functions).	
6	List-Union(l_u, l_v)'

דוגמה:

בדוגמה שלעיל היתה השורה Union(t1, t2). הנה מה שקורה:

כלומר אין שינוי לעומת מה שקרה מקודם.

דוגמה:

בדוגמה שלעיל היתה השורה Union(t8, t2). הנה מה שקורה:

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

ניתוח

קל להווכח בדברים הבאים:

משפט:

סיבוכוית Make-Setהיא $\displaystyle O(1)$ .
סיבוכוית Find-Setהיא $\displaystyle O(1)$ .
סיבוכוית Unionהיא $\displaystyle \Theta (n')$ במקרה הגרוע, כאשר $\displaystyle n'$ הוא גודל הקבוצה הקטנה מבין שתי הקבוצות שמאחדים.

כעת נראה סדרת משפטים המראה שמימוש זה מתאים לדרישותינו המקוריות.

נגדיר כ $\displaystyle T(n)$ את זמן הריצה הגרוע ביותר של סדרת פעולות Union המייצרות קבוצה בעלת גודל $\displaystyle n$ מ $\displaystyle n$ קבוצות זרות.

משפט:

$\displaystyle T(n)$ נתונה ע"י נוסחת הנסיגה $\displaystyle T(n)=\max _{1\leq i\leq n/2}[T(i)+T(n-i)+\Theta (i)]$

הוכחה: בהכרח מייצרים את הקבוצה על ידי פעולת Union המאחדת שתי קבוצות, האחת בעלת גודל $\displaystyle i$ , והשניה בעלת גודל $\displaystyle n-i$ .

יצירת הקבוצה הראשונה אורכת זמן $\displaystyle T(i)$ .
יצירת הקבוצה השניה אורכת זמן $\displaystyle T(n-i)$ .
פעולתה האיחוד האחרונה אורכת זמן $\displaystyle \Theta (\min(i,n-i))$ .

מטעמי סימטריה, נוכל להגדיר ש $\displaystyle i\leq n-i$ , או, בצורה אחרת, $\displaystyle i\leq n/2$ .

אפשר לפתור נוסחה זו באמצעים אלגבריים (ראה שאלה זו).

משפט:

$\displaystyle T(n)=\Theta (n\log(n))$ .

הטענה הבאה קלה למדי.

משפט:

זמן הריצה הגרוע ביותר של סדרת פעולות Union כלשהי, על $\displaystyle n$ קבוצות זרות. הוא $\displaystyle O(n\log(n))$ .

הוכחה: אם סדרת פעולות הUnion מייצרת קבוצה בעלת גודל $\displaystyle n$ , אז הטענה נובעת משני המשפטים הקודמים. אחרת, סדרת הפעולות מותירה אותנו עם יותר מקבוצה יחידה. במקרה זה, עוד מספר פעולות Union היו מביאות אותנו לקבוצה יחידה.

דוגמה:

נניח שסדרת סדרת פעולות הUnion מותירה 3 קבוצות. אז עוד 2 Union היו מותירות אותנו עם קבוצה יחידה.

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

כעת נוכל לנתח את סיבוכיות סדרת הפעולות.

משפט:

מימוש זה פועל תמיד בזמן $\displaystyle O(n\log(n)+m)$ .

הוכחה: יש לכל היותר $\displaystyle m$ פעולות שאינן פעולות Union, ובנוסף יש (אולי) פעולות Union.

סדרה בת (לכל היותר) $\displaystyle m$ פעולות שאינן Union, אורכת $\displaystyle O(m)$ . סדרת פעולות הUnion אורכת לכל היותר $\displaystyle O(n\log(n))$ .

הסיבוכיות לכן היא לכל היותר $\displaystyle O(m)+O(n\log(n))=O(n\log(n)+m)$ .

מימושים אחרים

ישנם מימושים אחרים שעבורם סדרת הפעולות תעלה רק $\displaystyle O(\alpha (n)+m)$ כאשר $\displaystyle \alpha$ היא הפונקציה ההפכית לפונקציית אקרמן, הגדלה באיטיות רבה מאד. הפונקציה גדלה כה לאט, שעבור ערכי $\displaystyle n$ מעשיים, $\displaystyle \alpha (n)$ הוא קבוע.

כדאי לדעת:

*בספר הקורס, הפרק "Disjoint Sets" (תת-פרק 4) מכסה נושא זה.

המימוש boost::disjoint_sets פועל בזמן זה.

הפרק הקודם:
תורי קדימויות

מבני נתונים לקבוצות זרות
תרגילים

הפרק הבא:
גרפים