10. גרפים

מבנה נתונים ואלגוריתמים

10.1 עצים פורשים מינימלית

אלגוריתמים חמדניים

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

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

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

בעיית העץ הפורש מינימלית

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

תחילה נזדקק למספר הגדרות:

גרף

גרף הוא סדרה של קדקודים וצלעות המקשרות ביניהם. נסמן:

G = (V,E)

כאשר V היא סדרת הקדקודים ו- E היא סדרה של צלעות שאותה נסמן:

E = { (v_i,v_j) }

כאשר v_i ו- v_j שייכים ל- V.

מסלול

מסלול p באורך k דרך גרף, הוא רצף של קדקודים הקשורים ביניהם:

p = <v₀,v₁,...,v_k>

כאשר עבור כל i ב- (0,k-1),(v_i,v_i+1) שייך ל- E.

מעגל

גרף אינו מכיל מעגלים אם אין אף מסלול (באורך השונה מאפס) דרך הגרף, p=<v₀,v₁,...,v_k>, כך ש- v₀ = v_k.

עץ פורש

עץ פורש של גרף G, הוא סדרה של |V|-1 צלעות המקשרות את כל הקדקודים שבגרף.

עץ פורש מינימלית

באופן כללי, ניתן לבנות עצים פורשים רבים עבור גרף G. אם עלות c_ij מקושרת עם כל צלע e_ij = (v_i,v_j), אזי עץ פורש מינימלית מהווה סדרה של צלעות E_span, היוצרת את העץ הפורש כך ש: C = sum( c_ij | all e_ij in E_span ) הוא מינימלי.

האלגוריתם של קרוסקל (Kruskal's Algorithm)

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

האלגוריתם הבסיסי נראה כך:

 Forest MinimumSpanningTree( Graph g, int n, double **costs ) {
  Forest T;
  Queue q;
  Edge e;
  T = ConsForest( g );
  q = ConsEdgeQueue( g, costs );
  for(i=0;i<(n-1);i++) {
  do {
  e = ExtractCheapestEdge( q );
  } while ( !Cycle( e, T ) );
  AddEdge( T, e );
  }
  return T;
 }
 
 
הצעדים הם:
1. בניית היער - כך שכל צומת היא בעץ נפרד.
2. מיקום הצלעות בתור קדימויות.
3. עד להוספת n-1 צלעות:
 a. הוצאת הצלע הזולה ביותר מהתור.
 b. אם הוספת הצלע יוצרת מעגל, ההוספה לא מבוצעת. 
 c. אם הצלע לא יוצרת מעגל, מבוצעת הוספה שלה ליער תוך איחוד שני עצים. 
 
בכל צעד יחוברו יחד שני עצים, כך שלבסוף יישאר עץ אחד בלבד ביער T. 
 
ניתן להיעזר בערמה עבור תור הקדימויות. העיקרון הוא לאתר מעגלים. לשם כך יש צורך במבנה של מציאת איחוד (union find).
 
מבנה מציאת איחוד
על מנת להבין מבנה זה יש צורך במבט על חלוקה של סדרה.
 
חלוקה
·  חלוקה היא סדרה של סדרות אלמנטים של סדרה. 
· כל אלמנט של הסדרה שייך לאחד מהסדרות בחלוקה.
· אף אלמנט של הסדרה אינו שייך ליותר מתת-סדרה אחת.
 
או במילים אחרות:
· כל אלמנט של הסדרה שייך לאחת ורק לאחת מסדרות החלוקה.
 
יער העצים הוא חלוקה של סדרה הצמתים המקורית. בתחילה בכל תת-סדרה יש בדיוק צומת אחת.
בהמשך האלגוריתם אנו יוצרים איחוד של שני עצים (תת-סדרות), עד שלבסוף בחלוקה יש רק 
תת-סידרה אחת המכילה את כל הצמתים.
 
ניתן לראות חלוקה כסדרה של מחלקות שקולות. כל תת-סדרה של החלוקה מכילה סדרה של אלמנטים שקולים (הצמתים
המחוברים לאחד מהעצים של היער). רעיון זה הוא המפתח לאלגוריתם לאיתור מעגל. בכל תת-סדרה מסומן אלמנט אחד
כמייצג תת-הסדרה. כל אלמנט בתת-הסדרה שקול, ומיוצג על ידי האלמנט שנבחר להיות הנציג.
 
שאשר מוסיפים אלמנטים לעץ, דואגים שכל האלמנטים מצביעים למייצגים שלהם. כאשר יוצרים איחוד של שתי סדרות, פשוט 
דואגים לכך שהמייצג של אחת הסדרות מצביע לכל אחד מהאלמנטים של הסדרה האחרת.
 
מבחן המעגל יהיה: מציאת המייצגים עבור שני הצמתים בקצוות הצלע המועמדת. אם שניהם זהים, הרי ששני הצמתים כבר
נמצאים בעץ מקושר אחד, והוספת צלע זו תיצור מעגל. החיפוש אחר המייצג הוא פשוט מעקב אחר שרשרת קשרים.
 
כל צומת זקוקה למצביע מייצג. בתחילה כל צומת היא המייצגת של עצמה, כך שהמצביע נקבע ל- NULL. כאשר זוג הצמתים
הראשון מאוחד ליצירת עץ, המצביע המייצג של אחד הצמדים מופנה להצביע לעברו של הצומת השני, אשר הופך להיות המייצג
של העץ. כאשר שני עצים מאוחדים המצביע המייצג של המייצג של אחד העצים נקבע להצביע לכל אלמנט של העץ השני (ברור
כי חיפושי מייצגים יהיו מהירים יותר אם אחד מהמייצגים יצביע ישירות לעבר האחר).
 
הקלק כאן על מנת לצפות בפעולות של האלגוריתם של קרוסקל
 
פעולות חמדניות
בכל שלב, לא מנסים להסתכל קדימה יותר מאשר צעד אחת - פשוט בוחרים את הצעד הטוב ביותר בכל שלב. ברור כי בחלק
מהמצבים גישה קצרת רואי שכזו מובילה לאסון! הגישה הפשטנית מתקשה להראות כי אלגוריתם חמדני מוביל לפתרון אופטימלי
של בעיית עץ פורש מינימלית (MST - minimal spanning tree). הוכחה על דרך השלילה היא טכניקת הוכחה נפוצה ובה נעשה
שימוש: נדגים כי אם לא נעשה את הבחירה התאוותנית, הפתרון שייווצר לא יהיה אופטימלי.
הוכחת אלגוריתם ה- MST הינה, למרבה השמחה, אחת מההוכחות הפשוטות ביותר בדרך השלילה.
 
מבני נתונים עבור גרפים
ניתן היה לשים לב כי דנו בגרפים בדרך מופשטת: הגדרנו כי הם מכילים צמתים (קדקודים) וצלעות, והזכרנו פעולות כגון הוספת
צלעות וסגירת מעגל. זה אפשר לנו להגדיר ADT - טיפוס נתונים מופשט, ללא התחשבות בפרטי היישום, כמו למשל, כיצד ניתן
לאחסן את תכונות הגרף. דבר זה אומר שפתרון מלא עבור בעיית ה- MST ,למשל, ניתן להגדרה לפני שבכלל החלטנו כיצד
לאחסן את הגרף במחשב. בכל אופן, סוגיית הייצוג אינה יכולה להידחות לנצח, כך שעלינו לבחון כעת דרכים לייצוג גרף 
במחשב. כפי שראינו קודם, הביצוע של האלגוריתם יקבע בין השאר על ידי מבנה הנתונים שייבחר.
 

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