מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/מבני נתונים לקבוצות זרות
הגדרה: שתי קבוצות, , , זרות אם אין להם איברים משותפים: . |
דף זה עוסק במניפולציות שונות של מבני נתונים המתארים קבוצות זרות זו לזו.
כדאי לדעת: *פתרון בעיה זו חשוב משתי סיבות:
|
מימוש C++ |
הבעיה
עריכהמייצרים קבוצות זרות, כל אחת בת איבר יחיד. כעת מאחדים בכל פעם שתי קבוצות כלשהן. במהלך סדרת האיחודים ולאחריהם רוצים לשאול, בהנתן שני איברים, האם הם חלק מאותה קבוצה או לא.
דוגמה: סטודנטים מתארגנים לקבוצות לימוד למבחן. נניח את ההנחה המקורבת שאם שני סטודנטים מחליטים ללמוד באותה קבוצה, אז הקבוצה שאליה שייך הסטודנט הראשון מתאחדת עם הקבוצה שאליה שייך הסטודנט השני. נרצה להיות מסוגלים, בהינתן שני סטודנטים, להחליט האם הם שייכים לאותה קבוצה או לא.נניח שיש שמונה סטודנטים: . נתן לחשוב עליהם בתחילה כ8 קבוצות זרות, שכ"א מורכבת מאיבר יחיד:
לבסוף, לכן, קבלנו את הקבוצות הזרות : נרצה להיות מסוגלים, בהינתן ו לדוגמה, לענות האם הם שייכים לאותה קבוצה (במקרה זה - לא). |
ממשק
עריכההפסוודו-קוד הבא מראה את הממשק של מבנה הנתונים שבו נשתמש לבעיה כזו שראינו:
# 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) )
הגדרה: לעתים יש מבני נתונים שנתן לממש אותם בדרכים שונות. כדאי להבדיל בין הדברים הבאים:
אלה המושגים הנהוגים בהנדסת תכנה. בתחום מבני הנתונים והאלגוריתמים, לפעמים קוראים למבנה נתונים שרק הממשק שלו הוצג - ADT, או abstract data type. |
הנחות ומטרה
עריכהנתבונן בסדרת פעולות שכ"א מהן היא Make-Set
,
Union
,
או Find-Set
.
- נגדיר את כמספר הפעולות בסדרה.
- נגדיר את כמספר פעולות
Make-Set
בסדרה (נשים לב שבהכרח ).
דוגמה: בדוגמה הקודמת שראינו היו 8 פעולות |
כדי לפשט מעט את הפתרון, נניח שאנו יודעים את מראש, ונשתמש כרצוננו במשתנים גלובאליים. (לאחר שמבינים את הפתרון, קל להפטר מהנחות אלו.)
מטרתנו היא למצוא מימוש כך שסדרת הפעולות תעלה סה"כ במקרה הגרוע (אם כי, במימושים אחרים נראה שאפשר אף להגיע ליעילות טובה יותר).
מימוש רשימות נאיבי
עריכההרעיון הכללי
עריכהנחזיק מערך גלובאלי, 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()}}
הנה המבנה לאחר שורה זו:
|
דוגמה: בדוגמה שלעיל היתה השורה 8 t8= Make-Set()}}
הנה המבנה לאחר שורה זו:
|
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
דוגמה: בדוגמה שלעיל היתה השורה |
דוגמה: בדוגמה שלעיל היתה השורה |
האינווריאנטה
עריכהמהתבוננות במימוש שתי הפעולות שראינו, קל לזהות את האינווריאנטה הבאה.
משפט: אם |
המשפט אומר למעשה את הדבר הבא. כל החוליות ברשימה המקושרת של Lists[1]
בעלות הערך 1 בvalue
, כל החוליות ברשימה המקושרת של Lists[2]
בעלות הערך 2 בvalue
, וכולי.
ראשית, קל לראות שהדבר נכון לכל חוליה שנוצרה כרגע ע"י Make-Set
.
הוכחה: Make-Set
מייצרת חוליה שערך הvalue
שלה הוא size
. היא מכניסה חוליה זו לרשימה בLists[size]
.
כעת נוכיח את המשפט באינדוקציה.
הוכחה: ההוכחה היא באינדוקציה על מספר הפעולה בסדרה, .
(בסיס האינדוקציה) עבור , הטענה בהכרח נכונה. הפעולה הראשונה בסדרת הפעולות היא מסוג Make-Set
(הפעולות משני הסוגים האחרים מקבלות ערכים מוחזרים מMake-Set
). ראינו זה עתה הוכחה לטענה עבור Make-Set
.
(מעבר האינדוקציה) נניח שהטענה נכונה עד (לא כולל) לפעולה ה , ונתבונן בפעולה ה . אם הפעולה מסוג Make-Set
, אז הטענה ממשיכה להתקיים. נניח לכן שהפעולה היא מהצורה Union(u, v)
. אם ערך u.value
הוא , אז, מהנחת האינדוקציה, החוליה נמצאת בLists[p]
. באותו אופן, אם ערך v.value
הוא , אז, מהנחת האינדוקציה, החוליה נמצאת בLists[q]
. הפעולה Union(u, v)
קובעת את הערכים בחוליות Lists[q]
ל , ותעביר אותן לLists[p]
. לכן הטענה תמשיך להתקיים לאחר הפעולה ה .
ניתוח
עריכהקל להווכח בדברים הבאים:
משפט:
|
מכאן קל לראות שמימוש זה אינו מתאים לדרישותינו המקוריות:
משפט: מימוש זה אינו פועל תמיד בזמן . |
את המשפט תתבקש להוכיח בשיעורי הבית.
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
המייצרות קבוצה בעלת גודל מ קבוצות זרות.
משפט: נתונה ע"י נוסחת הנסיגה |
הוכחה: בהכרח מייצרים את הקבוצה על ידי פעולת Union
המאחדת שתי קבוצות, האחת בעלת גודל , והשניה בעלת גודל .
- יצירת הקבוצה הראשונה אורכת זמן .
- יצירת הקבוצה השניה אורכת זמן .
- פעולתה האיחוד האחרונה אורכת זמן .
מטעמי סימטריה, נוכל להגדיר ש , או, בצורה אחרת, .
אפשר לפתור נוסחה זו באמצעים אלגבריים (ראה שאלה זו).
משפט: . |
הטענה הבאה קלה למדי.
משפט: זמן הריצה הגרוע ביותר של סדרת פעולות |
הוכחה: אם סדרת פעולות הUnion
מייצרת קבוצה בעלת גודל , אז הטענה נובעת משני המשפטים הקודמים. אחרת, סדרת הפעולות מותירה אותנו עם יותר מקבוצה יחידה. במקרה זה, עוד מספר פעולות Union
היו מביאות אותנו לקבוצה יחידה.
דוגמה: נניח שסדרת סדרת פעולות ה |
מכאן ברור שהמקרה בו סדרת הפעולות מותירה אותנו עם קבוצה יחידה, הוא המקרה הגרוע ביותר.
כעת נוכל לנתח את סיבוכיות סדרת הפעולות.
משפט: מימוש זה פועל תמיד בזמן . |
הוכחה: יש לכל היותר פעולות שאינן פעולות Union, ובנוסף יש (אולי) פעולות Union
.
סדרה בת (לכל היותר) פעולות שאינן Union
, אורכת .
סדרת פעולות הUnion
אורכת לכל היותר .
הסיבוכיות לכן היא לכל היותר .
מימושים אחרים
עריכהישנם מימושים אחרים שעבורם סדרת הפעולות תעלה רק כאשר היא הפונקציה ההפכית לפונקציית אקרמן, הגדלה באיטיות רבה מאד. הפונקציה גדלה כה לאט, שעבור ערכי מעשיים, הוא קבוע.
כדאי לדעת: *בספר הקורס, הפרק "Disjoint Sets" (תת-פרק 4) מכסה נושא זה.
|
הפרק הקודם: תורי קדימויות |
מבני נתונים לקבוצות זרות תרגילים |
הפרק הבא: גרפים |