אלגוריתמי קרוב לבעיית

מקצוע
שנת הגשה 2010
מספר מילים 9239

תקציר העבודה

אלגוריתמי קרוב לבעיית Densest k-Subgraph חיבור זה הוגש כעבודת גמר לקראת התואר "מוסמך אוניברסיטה" בהנדסת חשמל ואלקטרוניקה על – ידי העבודה נעשתה במחלקה להנדסת חשמל – מערכות אב תשנ"א לענבר באהבה, "כי באביב באת אלי…" תקציר עבודה זו דנה בקרוב בעיית Densest k-Subgraph. הבעיה הינה למצוא בגרף G עם n קדקודים תת גרף עם k קדקודים ומספר מקסימלי של קשתות. הבעיה הינה בעיה NP-HARD, ונשארת בעיה קשה גם כאשר הדרגה המקסימלית של כל קדקוד הינה 3. מטרת העבודה הינה להציע אלגוריתמי קרוב יעילים לבעיה (כלומר, בעלי זמן ריצה פולינומיאלי) ללא מגבלה על קלט האלגוריתמים. אלגוריתם קרוב יעיל  ידוע הינו אלגוריתם קרוב חמדני למציאת DkS בשם GADkS המוצג ב- ]Reference [8). בעבודה נציג שני אלגוריתמים המתבססים על אלגוריתם GADkS ואשר מנצלים את העובדה כי יחס הקרוב R של GADkS משתפר כאשר kàn. האלגוריתמים יחפשו בעזרת פונקציית גידול היוריסטית G(U) תתי גרפים של G המכילים את ה- DkS בעלי n` קדקודים כך ש- n` = O(k). על תתי גראפים אלה נפעיל את GADkS.
נשווה בין האלגוריתמים על ידי השוואת תוצאות הרצה על מאגר הגרפים LIBRARIES OF GRAPHS. השוואה זו תראה כי גישת האלגוריתמים הפולינומיאליים המוצעים משפרת את ביצועי אלגוריתם GADkS.
לסיכום נציע כיוון למחקר המשך למציאת טכניקה כללית יותר לשיפור ביצועים עבור בעיות אופטימיזציה קשות, המתבססת על טכניקת גידול המועמדים ל- DkS שבוצעה בעבודה זו.
תוכן עניינים

1 .      מבוא 10
1 .1.          הגדרות כלליות — 10
1 .1.1.             גרף (Graph) 10
1 .1.2.             תת גרף (Subgraph) – 10
1 .1.3.             תת גרף מושרה (Induced Subgraph) –. 10
1 .1.4.             גרף עם משקלים (Weighted Graph) –.. 10
1 .1.5.             דרגת קדקוד (Vertex Degree) -. 10
1 .1.6.             דרגת קדקוד עם משקלים (Vertex Weighted Degree) – 10
1 .1.7.             גרף r-רגולרי (r-regular Graph) … 11
1 .1.8.             קליק (Clique) –.. 11
1 .1.9.             אלגוריתם קרוב לבעיית אופטימיזציה -.. 11
1 .1.10.            סכימת קרוב –.. 11
1 .1.11.            סכימת קרוב פולינומיאלית (PTAS) –. 11
1 .1.12.            סכימת קרוב מלאה (FPTAS) – 11
1 .1.13.            יחס קרוב R עבור אלגוריתם A(G,w,k) -… 11
1 .2.          בעיית Densest k-Subgraph –.. 12
1 .2.1.             הגדרת הבעיה –. 12
1 .2.1.1.                דוגמא 12
1 .2.2.             סיבוכיות הבעיה -… 13
1 .2.2.1.               המקרה הכללי – 13
1 .2.2.2.               בעיית DkSd כאשר . 13
1 .2.2.3.               בעיית DkSd כאשר   , -… 14
1 .2.2.4.               סיבוכיות קרוב הבעיה בגרפים המכילים קליק בגודל k — 14
1 .2.2.5.               סיבוכיות הבעיה בגרפים דלילים — 15
1 .2.2.6.               סיבוכיות קרוב הבעיה בגרפים צפופים . 15
2 .      אלגוריתמי קרוב קיימים – 17
2 .1.          Algorithm GADkS -… 17
2 .1.1.             ביצועי האלגוריתם – 17
2 .1.2.             ניתוח זמן ריצה — 35
2 .2.          Algorithm DenseSubgraph –.. 35
2 .2.1.             ביצועי האלגוריתם – 36
2 .2.2.             ניתוח זמן ריצה — 37
3 .      אלגוריתמי קרוב מוצעים – 38
3 .1.          מבוא -… 38
3 .1.1.             התנהגות יחס הקרוב R של אלגוריתם GADkS –.. 38
3 .1.2.             חסרון אלגוריתם GADkS –. 39
3 .1.3.             גידול מועמדים להכלת DkS -.. 40
3 .2.          Algorithm ApproxDkS I . 41
3 .2.1.             חיפוש מקומי של DkS . 41
3 .2.2.             הגדרת האלגוריתם – 41
3 .2.3.             ניתוח זמן ריצה — 42
3 .2.3.1.               ניתוח זמן ריצה של 42
3 .2.4.             חיסרון החיפוש המקומי –.. 42
3 .3.          Algorithm ApproxDkS II 44
3 .3.1.             קדקודים שכיחים בפתרונות הביניים של ApproxDkS I 44
3 .3.2.             פיזור המקומיות של גישת אלגוריתם ApproxDkS I -. 44
3 .3.3.             הגדרת האלגוריתם – 46
3 .3.4.             ניתוח זמן ריצה — 46
4 .      ניתוח תוצאות – 47
4 .1.          כללי — 47
4 .2.          אופן הצגת תוצאות – 47
4 .2.1.             מדד השוואה r — 47
4 .2.2.             סדר ההצגה 48
4 .2.3.             אופן ההצגה 48
4 .3.          השוואת ApproxDkS I מול GADkS – 50
4 .3.1.             טבלה מסכמת –. 50
4 .3.2.             פילוג מדד ההשוואה r 50
4 .3.2.1.               פילוג כולל של r .. 50
4 .3.2.2.               פילוג r עבור ערכי k/n שונים . 51
4 .3.2.3.               פילוג מדד ההשוואה כפונקציה של k/n .. 52
4 .3.2.4.               פילוג מדד ההשוואה כפונקציה של n – 53
4 .4.          השוואת ApproxDkS II מול GADkS … 54
4 .4.1.             טבלה מסכמת –. 54
4 .4.2.             פילוג מדד ההשוואה r 55
4 .4.2.1.                פילוג כולל -… 55
4 .4.2.2.               פילוג עבור ערכי k/n שונים … 56
4 .4.2.3.               פילוג מדד ההשוואה r כפונקציה של k/n 57
4 .4.2.4.               פילוג מדד ההשוואה r כפונקציה של n .. 57
4 .5.          השוואת ApproxDkS II מול ApproxDkS I –. 58
4 .5.1.             השוואת עדיפות הרצות –… 58
4 .5.2.             פילוג מדד ההשוואה r 59
4 .5.2.1.                פילוג כולל -… 59
4 .5.2.2.               פילוג עבור ערכים שונים של k/n –. 59
4 .5.2.3.               פילוג מדד ההשוואה r כפונקציה של k/n 60
4 .5.2.4.               פילוג מדד ההשוואה r כפונקציה של n .. 61
5.      סיכום מסקנות … 62
6 .      עבודה להמשך (Further Research) -… 63
6 .1.          הכללת טכניקת שיפור ממוצע הביצועים -.. 63
6 .2.          שיפור פונקציית הגידול – 63
רשימת איורים איור 1: דוגמא של DkS.. 12
איור 2: דוגמת חסם תחתון עבור אלגוריתם GADkS.. 18
איור 3: דוגמת חסם תחתון עבור אלגוריתם GADkS כאשר n=24. 20 איור 4: מבנה  בדוגמת חסם תחתון עבור אלגוריתם GADkS כאשר n=24. 21
איור 5: המרת החלפה exchange(j,l) בין U ל- W… 29
איור 6: מבנה תרחיש קנוני. 31
איור 7 : יחס קרוב R של אלגוריתם  GADkS.. 39
איור 8 : גרף המהווה קלט לאגוריתם GADkS.. 40 איור 9: גרף בו GADkS עולה על ביצועי ApproxDkS I. 43
איור 10: פילוג r עבור כלל ההרצות (ApproxDkS I מול GADkS) 51
איור 11: פילוג r עבור ערכי k/n שונים (ApproxDkS I מול GADkS) 52
איור 12: פילוג r כפונקציה של k/n (ApproxDkS I מול GADkS) 53
איור 13: פילוג r כפונקציה של n (ApproxDkS I מול GADkS) 54
איור 14: פילוג r עבור כלל ההרצות (ApproxDkS II מול GADkS) 56
איור 15: פילוג r עבור ערכי k/n שונים (ApproxDkS II מול GADkS) 56
איור 16: פילוג r כפונקציה של k/n (ApproxDkS II מול GADkS) 57
איור 17: פילוג r כפונקציה של n (ApproxDkS II מול GADkS) 58
איור 18: פילוג r עבור כלל ההרצות (ApproxDkS II מול ApproxDkS I) 59
איור 19: פילוג r עבור ערכים שונים של k/n (ApproxDkS II מול ApproxDkS I) 60 איור 20: פילוג r כפונקציה של k/n (ApproxDkS II מול ApproxDkS I) 61
איור 21: פילוג r כפונקציה של n (ApproxDkS II מול ApproxDkS I) 61
רשימת טבלאות טבלה 1: סיכום תוצאות הביניים של פרוצדורת GrowDkS באלגוריתם ApproxDkS I. 44
טבלה 2: טבלה מסכמת עבור ApproxDkS I מול GADkS.. 50 טבלה 3: טבלה מסכמת של תוצאות ApproxDkS II מול GADkS.. 54
טבלה 4: טבלה מסכמת של תוצאות AprroxDkS II מול ApproxDkS I. 58
                   
1 .מבוא
             
1 .1.הגדרות כלליות סעיף זה יציג הגדרות וסימונים אשר ישמשו אותנו לאורך העבודה.
        
1 .1.1.גרף (Graph) בעבודה זו גרף  הוא גרף בלתי מכוון, פשוט וקשיר V זו קבוצת קדקודי הגרף ו-  צלעותיו.  יסומן ב- , ו-  יסומן ב- .
        
1 .1.2.תת גרף (Subgraph) תת גרף  של גרף  מוגדר על ידי קבוצה , ועל ידי  כך ש-  אם ורק אם  וגם .
        
1 .1.3.תת גרף מושרה (Induced Subgraph) תת גרף  של גרף  מוגדר על ידי קבוצה , כאשר. גרף זה נקרא גם גרף מושרה (induced) על ידי  .
        
1 .1.4.גרף עם משקלים (Weighted Graph) גרף עם משקלים הינו צמד (G, w), כאשר G הוא גרף ו- w היא פונקציית משקל w:E(G)®R+.         
1 .1.5.דרגת קדקוד (Vertex Degree) דרגת קדקוד v בגרף G, הינו מספר הקשתות ב- G הנוגעות ב- v.
        
1 .1.6.דרגת קדקוד עם משקלים (Vertex Weighted Degree) בגרף עם משקלים תוגדר דרגת הקדקוד כך:
        
1 .1.7.גרף r-רגולרי (r-regular Graph) גרף בו דרגת כל קדקוד הינה r.
        
1 .1.8.קליק (Clique) קליק  הינו גרף בעל  קדקודים בו בין כל צמד קדקודים קיימת קשת כלומר .
        
1 .1.9.אלגוריתם קרוב לבעיית אופטימיזציה אלגוריתם קרוב עבור בעיית אופטימיזציה P בעלת פתרון אופטימאלי S* יבטיח תוצאה S "קרובה" לתוצאה האופטמאלית. עבור בעיית מקסימיזציה, אלגוריתם קרוב ישיג תוצאה S כך ש- S < S*. עבור בעיית מינימיזציה, אלגוריתם קרוב ישיג תוצאה S כך ש- S > S*.
ביצועי אלגוריתם קרוב נמדדים בעזרת יחס קרוב R המוגדר בסעיף ‏1.1.13.
    
1 .1.10.סכימת קרוב סכימת קרוב הינו אלגוריתם קרוב, המקבל כקלט פרמטר e, ופולט תוצאה (בבעיית מינימום) המקיימת עבור בעיית מקסימום ההגדרה משתנה בהתאמה.
    
1 .1.11.סכימת קרוב פולינומיאלית (PTAS) סכימת קרוב פולינומיאלית (Polynomial Time Approximation Scheme) הינה סכימת קרוב הרצה בזמן פולינומיאלי ב- n (אך יכולה לרוץ בזמן סופר פולינומיאלי ב- ).
    
1 .1.12.סכימת קרוב מלאה (FPTAS) סכימת קרוב מלאה הינה סכימת קרוב הרצה בזמן פולינומיאלי ב- n וב- .