הבלוג של גרי רשף

25/05/2010

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

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

אשתמש באלגוריתם של Prim אותו אממש בעזרת CTE רקורסיבי:
1. נמספר את הקשתות בסדר עולה לפי האורך, ונתחיל עם הקטנה ביותר.
2. "נצבור" בעמודה S_in את הקשתות הכלולות בעץ הפורש המינימלי (כלומר- שני הקודקודים של כל קשת).
3. כל קשת – בסדר עולה של אורכים – תיבדק ביחס ל-S_in, ואם אחד הקודקודים שם ואחד לא (בכל צעד יש להוסיף את הקשת המינימלית המתחברת לעץ) – היא תצורף לעץ הפורש המינימלי, והסריקה של הקשתות תתחיל מחדש.
4. עמודה Kodkodim סופרת כמה קודקודים כבר יש בעץ, והאלגוריתם ימשך עד שמספר הקודקודים בעץ יהיה KodkodimS (סה"כ קודקודים בגרף- נמדד בהתחלה ולא תלוי בפתרון).
5. עמודת Idcun מציינת אם בוצע עדכון בשורה זו (1) או לא (0), ולכן היא מציינת גם את מספר הקודקודים שהתווספו לעץ הפורש.
שיטה זו – של שימוש במחרוזת הצוברת את המידע – שימושית בבעיות CTE רקורסיבי מכיוון שהוא מוגבל ואינו מאפשר להשתמש בַּרקורסיה ב-Top, Left Join, Group By, Exists וכו'.
בנוסף- גם כאן אני משתמש ברקורסיה כפולה, כלומר- ה-CTE כולל עוגן ושתי רקורסיות (ולא אחת כמקובל). עלי להודות שלמרות שהאופציה הזו עובדת – אני לא בטוח לגמרי שאני מבין את ההגיון שלה, ומקווה שהוא לא ישתנה בגרסאות עתידיות.. בכל מקרה- אנסה להתחקות אחריו באחד הפוסטים הקודמים.

נתחיל בהקמת טבלה (Minimum Spanning Tree), ואתרגל על הגרף המוצג בויקיפדיה:

Use tempdb;

Go

Create Table T_MST(K1 Varchar(10), K2 Varchar(10), Oreh Int);

Go

Insert Into T_MST Values ('A','B',4);

Insert Into T_MST Values ('A','C',1);

Insert Into T_MST Values ('A','D',4);

Insert Into T_MST Values ('B','E',9);

Insert Into T_MST Values ('B','F',9);

Insert Into T_MST Values ('B','G',7);

Insert Into T_MST Values ('B','C',5);

Insert Into T_MST Values ('C','D',3);

Insert Into T_MST Values ('C','G',9);

Insert Into T_MST Values ('D','G',10);

Insert Into T_MST Values ('D','J',18);

Insert Into T_MST Values ('E','F',2);

Insert Into T_MST Values ('E','I',4);

Insert Into T_MST Values ('E','H',6);

Insert Into T_MST Values ('F','I',2);

Insert Into T_MST Values ('F','G',8);

Insert Into T_MST Values ('G','I',9);

Insert Into T_MST Values ('G','J',8);

Insert Into T_MST Values ('H','I',3);

Insert Into T_MST Values ('H','J',9);

Insert Into T_MST Values ('I','J',9);

Go

וכעת לשליפה עצמה:

With V_MST As

(Select    ROW_NUMBER() Over(Order By Oreh) No,

        K1,

        K2,

        Oreh

From    T_MST),

T As 

(Select    No,

        K1,

        K2,

        Oreh,

        (-1) Idcun,

        2 Kodkodim,

        (Select COUNT(*) From (Select K1 From T_MST Union Select K2 From T_MST) T) KodkodimS,

        Cast(','+K1+','+K2+',' As Varchar(Max)) S_in

From    V_MST

Where    No=1

 

Union All

Select    No,

        K1,

        K2,

        Oreh,

        Idcun,

        Kodkodim+Idcun Kodkodim,

        KodkodimS,

        S_In+Case When Idcun=1 Then K1+','+K2+',' Else '' End S_in

From    (Select    V_MST.No,

                V_MST.K1,

                V_MST.K2,

                V_MST.Oreh,

                Case When ((T.S_in Like '%,'+V_MST.K1+',%' And T.S_in Not Like '%,'+V_MST.K2+',%')

                            Or (T.S_in Not Like '%,'+V_MST.K1+',%' And T.S_in Like '%,'+V_MST.K2+',%'))

                    Then 1 Else 0 End Idcun,

                T.Kodkodim,

                T.KodkodimS,

                T.S_in

        From    T

        Inner Join V_MST

                On T.No+1=V_MST.No

        Where    T.Kodkodim<T.KodkodimS

                And T.Idcun<=0) T

 

Union All

Select    V_MST.No,

        V_MST.K1,

        V_MST.K2,

        V_MST.Oreh,

        0 Idcun,

        T.Kodkodim,

        T.KodkodimS,

        T.S_in

From    T

Inner Join V_MST

        On T.Idcun=1

        And V_MST.No=1

Where    T.Kodkodim<T.KodkodimS)

Select    *

From    T

Where    Idcun<>0

Option (MaxRecursion 0);

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

מודעות פרסומת

3 תגובות »

  1. […] אשר אין לו שעה.. רצה הגורל והאתגר התפרסם סמוך לפרסום הפוסט שלי על העץ הפורש המינימלי, והאתגר של איציק כלל למעשה חיפוש של עץ פורש – לאו דווקא […]

    פינגבאק של Identifying Related Tables - גרי רשף — 19/01/2012 @ 19:09

  2. […] כן- אשמח להתעדכן), אבל כן נתקלתי בבעיות שרק כך הן נפתרו (עץ פורש מינימלי או Packing Date Intervals), ולכן אנצל את ההזדמנות לעקוב אחר […]

    פינגבאק של CTE רקורסיבי - גרי רשף — 19/01/2012 @ 19:04

  3. […] אשר אין לו שעה.. רצה הגורל והאתגר התפרסם סמוך לפרסום הפוסט שלי על העץ הפורש המינימלי, והאתגר של איציק כלל למעשה חיפוש של עץ פורש – לאו דווקא […]

    פינגבאק של Identifying Related Tables « הבלוג של גרי רשף — 15/06/2010 @ 08:45


RSS feed for comments on this post. TrackBack URI

להשאיר תגובה

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

הלוגו של WordPress.com

אתה מגיב באמצעות חשבון WordPress.com שלך. לצאת מהמערכת / לשנות )

תמונת Twitter

אתה מגיב באמצעות חשבון Twitter שלך. לצאת מהמערכת / לשנות )

תמונת Facebook

אתה מגיב באמצעות חשבון Facebook שלך. לצאת מהמערכת / לשנות )

תמונת גוגל פלוס

אתה מגיב באמצעות חשבון Google+ שלך. לצאת מהמערכת / לשנות )

מתחבר ל-%s

יצירה של אתר חינמי או בלוג ב־WordPress.com.

%d בלוגרים אהבו את זה: