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

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

"חמדן" אלגוריתם

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

מציאת משקל קרקאס מינימום

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

תיאור

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

יישום

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

1. מסדרים את כל הקצוות של הגרף מ -1 עד משקולות עולה n-ה. (Ai, דו - אני עם מספר קצה הקודקוד).

2. עבור i = 1 n לעשות.

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

4. y: = חלק (BI).

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

תקינות

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

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

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

דוגמאות יישום אלגוריתם Kruskal

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

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

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

הרצף של הצלעות הוסיפו (1.6); (0,3), (2,6) או (2,6), (0,3) - לא חשוב; (3,4); (0,1), (1,6) או (1,6), (0,1), גם אכפת (5,6).

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