האלגוריתם של קרוסקל ומבנה הנתונים Union/Find

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

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

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

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

edge.weight = 4

כאן לקחתי את האובייקט edge ואמרתי “מעכשיו יש לך שדה שנקרא weight וערכו 4, למקרה שמישהו שואל”. בשפות כמו C או Java, צריך להצהיר מראש על כל השדות שיהיו לאובייקט; שפות כמו Javascript או רובי או פייתון הן יותר מקלות בקטע הזה, ולכן אני מעדיף את הגישה שלהן כשאני בא לתאר אלגוריתם בצורה פשוטה. כמובן, זה אומר שמי שרוצה לממש את האלגוריתם ב-C צריך להסתבך קצת יותר עם “בניית פיגומים” שיאפשרו לו לעשות את הדברים שאני עושה כאן, אבל אני סומך על הקורא הנבון שיצליח לעשות את זה ולמצוא את הדרך הנוחה ביותר עבורו; העיקר פה הוא האלגוריתם, לא הקוד הספציפי שלי.

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

make_set: function(x){
		x.disjoint_set_rep = x;
}

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

עד כמה הפתרון הזה יעיל? ובכן, להחזיר את הנציג של איבר זה מיידי = פשוט ניגשים אל השדה המתאים אצלו. זה לוקח זמן של \( O(1) \) צעדי חישוב. מצד שני, איחוד היא פעולה בעייתית - אם אנחנו מאחדים את המחלקות של שני איברים, נהיה חייבים לשנות את הנציג שעליו מצביעים כל האיברים באחת משתי המחלקות שאנו מאחדים. זה אומר שנצטרך איכשהו לעבור סדרתית על כולם. ברמת הקוד שלי, בכלל לא ברור איך אפשר לעשות את זה כי אני לא שומר את כל האיברים במקום מרכזי אחד (כרגע כל מה שיש לי הוא מידע נוסף בתוך כל איבר), אבל זה מילא, נניח שאני כן שומר אותם במיקום מרכזי. עדיין, צריך לעבור על כל האיברים שבכלל שייכים למבנה הנתונים שלי, לבדוק לכל אחד מהם אם הוא באותה קבוצה כמו אחד מהאיברים שמאחדים, ואם כן - לשנות בהתאם את הנציג שלו. אם יש \( n \) איברים בסך הכל במבנה הנתונים, זה אומר שכל פעולת Union דורשת \( O(n) \) צעדי חישוב. זה לא נשמע כזה גרוע עד שחושבים מה קורה, למשל, בדוגמת המבוך שלנו: אנחנו הולכים לקרוא ל-Union בדיוק \( n-1 \) פעמים, עד שכל המחלקות “יתאחדו”. אם כל פעם כזו עולה לי \( O(n) \) זמן חישוב, אז זמן החישוב הכולל שאשקיע בביצוע פעולות Union/Find יהיה \( O(n^2) \) - וזמן ריבועי זה לא משהו בכלל. אם יש לנו 1,000 איברים ואנו מבצעים 1,000 פעולות איחוד, זמן הריצה הכולל יהיה בסדר גודל של 1,000,000 - לא טוב!

זה מוביל אותי לנקודה עדינה שנוגעת לאופן שבו מודדים את הסיבוכיות של מבנה נתונים כמו Union/Find: אפשר למדוד את הסיבוכיות הגרועה ביותר של כל פעולה לכשעצמה, אבל מכיוון שזה מבנה נתונים שהאובייקט שהוא מתאר “אוכל את עצמו” עם הזמן, לפעמים נכון יותר למדוד את הזמן הכולל שלוקח לבצע סדרת פעולות, ולבדוק רק מהו זמן הריצה הממוצע לביצוע פעולה. סיבוכיות שנמדדת באופן הזה נקראת משוערכת (Amortized). זה מדד סיבוכיות קצת שונה ממדידת סיבוכיות “המקרה הגרוע ביותר” הטיפוסית, אבל היא יותר הגיונית בהקשר של מבני נתונים כמו Union/Find, בעיקר עם המימוש שנשתמש בו בסוף ו”משפר את עצמו תוך כדי ריצה”.

אז מה שנעשה הוא כך: נניח שיש במבנה הנתונים \( n \) איברים שכולם הוכנסו אליו כבר בהתחלה (כלומר, בוצעו \( n \) פעולות make_set) ואז מגיעה סדרה של פעולות של Union ו-Find, ונראה מה הזמן המקסימלי שנדרש לביצוע כל הפעולות הללו. בסופו של דבר מדד הסיבוכיות שלנו יהיה תלוי בשני פרמטרים - \( n,m \) כאשר \( m \) מודד את מספר הפעולות הכולל שבוצע על המבנה (נהוג להניח שהוא כולל גם את \( n \) פעולות ה-make_set כדי שהוא יהיה תמיד לפחות \( n \)). כרגע, במימוש הנוכחי שלנו, במקרה הגרוע ביותר שבו כל הפעולות אחרי היצירה הן Union, הזמן הכולל של הריצה יהיה \( O(mn) \) - לא מרשים.

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

find: function(x){
		if (x != x.disjoint_set_pred){
			return find(x.disjoint_set_pred);
		}
		return x.disjoint_set_pred;
	},

אני קורא עכשיו לשדה של x בשם disjoint_set_pred ולא disjoint_set_rep כי אנחנו מצביעים כעת לא לנציג, אלא ל”איבר שבא לפני x בעץ”.

עכשיו, כמה קלקלנו? התשובה היא שדי הרבה. מה הסיטואציה הגרועה ביותר שיכולה להתרחש? שיש לנו מחלקת שקילות גדולה מסדר גודל של \( n \) איברים, ואיכשהו יצא שהעץ שבו הם מסודרים הוא “שרוך”, כלומר לכל צומת יש בן יחיד, ואנחנו מפעילים Find על העלה של השרוך הזה. אז Find יטפס לו למעלה למעלה בעץ עד שיגיע אל השורש, מה שייקח לו \( n \) צעדים; הקפצנו את המחיר של Find מ-\( O(1) \) ל-\( O(n) \). מצד שני, שיפרנו את Union פלאים, כי עכשיו כל מה שצריך לעשות כדי לאחד שתי קבוצות של אובייקטים שונים היא לקחת את הנציגים שלהם, ולגרום לאחד הנציגים להצביע אל הנציג השני. בקוד זה הולך להיראות ככה:

union: function(x,y){
	var a = DisjointSets.find(x);
	var b = DisjointSets.find(y);
	a.disjoint_set_pred = b;
}

הפונקציה הזו לוקחת זמן של \( O(1) \) כדי לבצע את האיחוד בפועל אחרי שבוצעו שתי פעולות ה-Find, אבל כמובן שכרגע מצבנו לא מזהיר כי פעולות ה-Find עצמן הן יקרות. אז לעת עתה נראה שקלקלנו את זמן הביצוע של Find ללא הצדקה ולא שיפרנו את זמן הביצוע של Union. המחיר של ביצוע סדרה של \( m \) פעולות עדיין יהיה \( O(mn) \). אז מה עושים? כאן מתחיל הקסם: אנחנו הולכים לתקן קצת את Union בצורה שתבטיח ש-Union יצור עץ מאוזן יחסית ולא משהו שנראה כמו שרוך, ואנחנו הולכים לתקן קצת את Find בצורה שתבטיח שהוא “ידחוס” את העץ שעליו הוא פועל ויעביר אותו לייצוג יעיל יותר עבורנו.

נתחיל מהאופטימיזציה של Find, שהיא יותר קלה להבנה. אנחנו רוצים שבמצב האופטימלי, כל צומת יצביע ישירות אל הנציג שלו; כל הקטע הזה של הפניה עקיפה (להצביע על מישהו שמצביע על מישהו שמצביע על מישהו שמצביע על הנציג) קיים רק כי פעולת Union תהיה יקרה מדי לביצוע בלעדיו. אבל זה לא אומר שאי אפשר לאפטמז את מבנה הנתונים תוך כדי ביצוע: אם אנחנו הפעלנו Find על איבר x ובסופו של דבר מצאנו את הנציג של x, למה לא לנצל את ההזדמנות הזו כדי לעדכן את המצביע של x כדי שיצביע ישירות על הנציג? בצורה הזו, אפילו אם x אכן היה בקצה של “שרוך” והזמן שנדרש כדי למצוא את הנציג שלו היה \( O(n) \), קריאות עתידיות ל-Find על אותו x יעלו לנו רק \( O(1) \) זמן.

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

find: function(x){
		if (x != x.disjoint_set_pred){
			x.disjoint_set_pred = find(x.disjoint_set_pred);
		}
		return x.disjoint_set_pred;
	},

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

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

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

אז בואו נוסיף לכל צומת גם פיסת מידע נוספת, שאקרא לה rank (ולמה לא “עומק”? תכף אסביר, אבל נסו לחשוב בעצמכם) ואיחוד יפעל כך: קודם כל מוצאים את נציגי שתי המחלקות שרוצים לאחד; אחר כך משווים את ה-rank של שניהם; אם ה-rank של אחד מהם גדול מזה של השני, גורמים לשני להצביע על הראשון; אם הם שווים בוחרים אחד באופן שרירותי כדי שיצביע על השני, ומגדילים את ה-rank של זה שמצביעים עליו ב-1. הנה הקוד:

union: function(x,y){
		var a = find(x);
		var b = find(y);
		if (a.disjoint_set_rank > b.disjoint_set_rank){
			b.disjoint_set_pred = a;
		}
		else{
			a.disjoint_set_pred = b;
			if (a.disjoint_set_rank	== b.disjoint_set_rank){
				b.disjoint_set_rank = b.disjoint_set_rank + 1;
			}
		}
	}

אוקיי, ולמה אני קורא בשם rank ולא בשם “עומק” לתכונה הזו? אלמלא האופטימיזציה הראשונה, מה שאני קורא לו rank אכן היה עוקב באופן מדויק אחרי עומק העצים של כל הנציגים; אבל האופטימיזציה הראשונה יכולה לשנות את זה - היא מקטינה ללא הרף את עומק העצים הללו, ולא טורחת לעדכן את ה-rank בהתאם (אם תחשבו על כך קצת תראו שכדי לעשות את זה היא חייבת לעשות טיול בכל העץ - מה שהוא גם מסובך ברמת הקוד וגם יגדיל את זמן הריצה של find). לכן אנחנו “מתפשרים” - rank הוא חסם מלעיל על עומק העץ של הנציג, וזה מספיק טוב לנו.

עכשיו, הניתוח המדויק של האופן שבו שתי האופטימיזציות הללו משפרות את האלגוריתם הוא קשה. אני לא הולך להציג אותו כרגע, אבל הוא מוצג במלואו, למשל, בספר האלגוריתמים של Cormen ושות’. אני רוצה להציג רק את השורה התחתונה שלו - הסיבוכיות המשוערכת של מבנה הנתונים. הסיבוכיות הזו היא \( O(m\alpha(n)) \), כאשר הפונקציה \( \alpha(n) \) הוא פונקציה שגדלה מאוד, מאוד, מאוד, מאוד, מאוד לאט. לכל צורך מעשי אי פעם אפשר לחשוב על הערך שלה כחסום על ידי 5. מה שזה אומר הוא שזמן הריצה המשוערך של \( m \) פעולות הוא כמעט לינארי ב-\( m \), עם קלקול שהוא ממש זניח ולא מורגש בפועל.

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

var DisjointSets = {
	make_set: function(x){
		x.disjoint_set_pred = x;
		x.disjoint_set_rank = 0;
	},

	find: function(x){
		if (x != x.disjoint_set_pred){
			x.disjoint_set_pred = DisjointSets.find(x.disjoint_set_pred);
		}
		return x.disjoint_set_pred;
	},

	union: function(x,y){
		var a = DisjointSets.find(x);
		var b = DisjointSets.find(y);
		if (a.disjoint_set_rank > b.disjoint_set_rank){
			b.disjoint_set_pred = a;
		}
		else{
			a.disjoint_set_pred = b;
			if (a.disjoint_set_rank	== b.disjoint_set_rank){
				b.disjoint_set_rank = b.disjoint_set_rank + 1;
			}
		}
	}
}

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

ועכשיו אפשר סוף סוף להציג את הפונקציה של קרוסקל, שהיא חלק מהמחלקה של גרף:

kruskal_min_spanning_tree: function(){
		var min_queue = new Array();
		this.each_edge(function(e){min_queue.push(e)});
		min_queue.sort(function(a,b){return (a.w - b.w)})
		var vertices = new Array();
		for (var i = 0; i < this.n; i++){
			vertices.push({});
			DisjointSets.make_set(vertices[i]);
		}
		var tree_edges = new Array();
		while (min_queue.length > 0){
			e = min_queue.shift();
			if (DisjointSets.find(vertices[e[0]]) != DisjointSets.find(vertices[e[1]])){
				DisjointSets.union(vertices[e[0]],vertices[e[1]]);
				tree_edges.push(e);
			}
		}

		return tree_edges;
	},

שורות 2-4 בונות רשימה ממויינת של הקשתות, כשהמיון הוא מהקלה ביותר (ראשונה) אל הכבדה ביותר.בשורות 5-9 אני מייצר לכל קודקוד של הגרף אובייקט ומפעיל עליו את make_set כדי ליצור קבוצה שמכילה כרגע רק אותו (אני חייב שכל צומת יהיה מיוצג על ידי אובייקט כדי שאפשר יהיה להפעיל עליו את make_set וכרגע בגרף הצמתים הם רק מספרים - כל זה הוא עניין טכני של ג’אווהסקריפט שלא רלוונטי כל כך באופן כללי). בשורה 10 אני מאתחל את הרשימה שבה נשמור את הקשתות שניקח אל העץ. רק משורה 11 מתחיל האלגוריתם האמיתי: כל עוד יש קשתות ברשימה אני שולף ממנה את הראשונה, בודק האם הצמתים שמחוברים לקשת שייכים לאותה קבוצה, ואם לא - מאחד את הקבוצות שלהם ומוסיף את הקשת לעץ. טריוויאלי, אחרי כל עבודת ההכנה שעשינו.

ושאלת המחץ - מה הסיבוכיות של האלגוריתם? סיבוכיות של אלגוריתמים על גרפים לרוב מודדים כפונקציה של מספר הצמתים V ומספר הקשתות E. כאן שלב המיון של הקשתות לוקח זמן \( O(E\log E) \) כאשר משתמשים באלגוריתם מיון טוב (נאמר, מיון ערימה). לאחר מכן מבצעים \( O(E) \) פעולות של Find (לכל קשת אנחנו בודקים את הקצוות שלה), ובנוסף לכך בדיוק \( V-1 \) פעולות של Union. מה שאומר שאצלנו \( m=O(V+E) \). לכן הסיבוכיות הכוללת של השימוש ב-Union/Find היא \( O((V+E)\alpha(V)) \). כדי לא לעצור כאן נניח עוד הנחה - שמספר הקשתות הוא לפחות מסדר גודל של מספר הצמתים (אם הוא קטן יותר מ-\( V-1 \) הגרף המקורי לא יהיה קשיר ולכן לא נוכל למצוא לו עץ פורש ממילא; אם כי כפי שאמרתי, במקרה הזה נמצא עץ פורש עבור רכיבי הקשירות). תחת ההנחה הזו, \( V=O(E) \), אפשר לפשט את הסיבוכיות של שלב ה-Union/Find ל-\( O(E\alpha(E)) \). עכשיו, בגלל ש-\( \alpha \) היא פונקציה שגדלה מאוד לאט, היא בפרט גדלה יותר לאט מאשר לוגריתם (שהיא בעצמה פונקציה שגדלה באופן איטי למדי), כלומר, בניסוח פורמלי, \( \alpha(E)=O(\log E) \). המסקנה היא שהסיבוכיות של שלב ה-Union/Find חסומה על ידי \( O(E\log E) \) כמו שלב המיון ולכן זו גם הסיבוכיות הכוללת של האלגוריתם (שימו לב לתוצאה המפתיעה - שלב המיון הוא השלב הכי כבד מבחינה חישוביות באלגוריתם!). לרוב נהוג לנסח את הסיבוכיות של האלגוריתם בניסוח \( O(E\log V) \) שהוא אפשרי בגלל שבכל גרף, \( E \) הוא לכל היותר \( V^2 \) ולכן הלוגריתמים שלהם מאותו סדר גודל.

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

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