אלגוריתם קרוסקל - בניית השלד האופטימלי

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

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

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

מציאת השלד של משקל מינימלי

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

תיאור

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

יישום

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

1. לסדר את כל הקצוות של הגרף מ 1 עד nth עולה משקולות. (ai, bi הם הקודקודים של הקצה עם אינדקס i).

2. עבור i = 1 ל- n.

3. x: = חלק (ai).

4. y: = חלק (דו).

5. אם x אינו שווה ל- y ואז התאחדו (x, y), כלול את הקצה עם המספר i ב- F.

נכונות

תן T להיות השלד של הגרף המקורי נבנה באמצעות אלגוריתם Kruskal, ולתת S להיות שלד שרירותי שלה. יש להוכיח כי w (T) אינו חורג w (S).

תן M להיות קבוצה של הקצוות של S, P קבוצה של הקצוותט אם S הוא לא שווה T, אז קיים T פגר et קצה, לא שייך et ס ס לגבול עם המחזור, זה נקרא ג ג להסיר מכל es קצה, השייכים S. אנו להשיג מסגרת חדשה, בגלל קצוות ופסגות בו כמה שיותר. משקלו הוא לא יותר מאשר w (S), מאז w (et) כבר לא w (es) באלגוריתם Kruskal כוח. פעולה זו (צלעות T S תחליף על צלעות) תבוצע שוב כל עוד מקבלים ט המשקל של כל מסגרת נתקבלה לאחר אינו עולה על המשקל הקודם, ממנה משתמע כי w (T) אינו גדול מ w (S).

כמו כן, את התקינות של אלגוריתם Kruskal כדלקמן מן ראדו אדמונדס משפט על matroids.

דוגמאות ליישום האלגוריתם של קרוסקל

גרף עם קודקודים a, b, c, d, e וקצוות (a,ב), (א, ה), (ב, ג), (ב, ה), (ג, ד), (ג, ה), (ד, ה). משקולות הקצוות מוצגים בטבלה ובדמות. בתחילה, בניית יער F מכיל את כל הקודקודים של הגרף ואינו מכיל קצה אחד. אלגוריתם Kruskal הראשון להוסיף צלע (א, ה), שכן המשקל היה הנמוך ביותר, ואת הקודקודים A ו- E הם רכיבים שונים עץ קישוריות F (צלע (א, ה) הוא ירוק), אז הצלע (ג, ד), כי שלפחות משקל הקצה הזה של קצות גרף, לא שייך F, וזה ירוק, אז מאותן הסיבות לצבור יתרון (א, ב). אבל הקצה (ב, ה) מועבר, אף על פי שהוא והמשקל המינימאלי של הקצוות הנותרים, כי זה אדום: b הקודקודים והדואר שייך לאותו הרכיב של קישוריות יער F, כי הוא, ואם נוסיף F הקצה (ב, ה), נוצר מחזור. לאחר מכן הקצה הירוק (b, c) נוסף, הקצה האדום (c, e) מדלג, ולאחר מכן d, e. לפיכך, קצוות מתווספים ברצף (א, ה), (ג, ד), (א, ב), (ב, ג). מתוך זה, את השלד האופטימלי של הגרף המקורי מורכב. כך פועל האלגוריתם במקרה זה אני צבוע. דוגמה לכך.

הדמות מציגה גרף המורכב משני רכיבי קישוריות. קווים מודגשים מראים את הקצוות של המסגרת האופטימלית (ירוק), שנבנו באמצעות האלגוריתם Kruskal.

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

רצף של קצוות הוסיף: (1.6); (0,3), (2,6) או (2,6), (0,3) - לא משנה; (3.4); (0,1), (1,6) או (1,6), (0,1), הוא גם אדיש (5,6).

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