Αλγόριθμο του Kruskal - η κατασκευή του βέλτιστου πλαισίου

Στις αρχές του 19ου αιώνα, γεωμέτρης Γιάκομπ Steiner από το Βερολίνο που το έργο για το πώς να συνδέσετε τρία χωριά, έτσι ώστε το μήκος τους ήταν η συντομότερη. Αργότερα, ο ίδιος συνόψισε το πρόβλημα: πρέπει να βρούμε ένα σημείο σε ένα αεροπλάνο, η απόσταση από αυτό σε n άλλα σημεία ήταν η χαμηλότερη. Κατά τον 20ο αιώνα, συνεχίζει να εργάζεται για το θέμα αυτό. Αποφασίστηκε να διαρκέσει μερικά σημεία και τη διασύνδεσή τους με τέτοιο τρόπο ώστε η απόσταση μεταξύ τους ήταν η συντομότερη. Όλα αυτά είναι μια ειδική περίπτωση του προβλήματος που μελετάται.

«Άπληστοι» αλγόριθμο

αλγόριθμο του Kruskal αναφέρεται στο «άπληστο» αλγόριθμο (που ονομάζεται επίσης κλίση). Η ουσία αυτών που - το υψηλότερο κέρδος σε κάθε βήμα. Όχι πάντα, «άπληστοι» αλγόριθμοι παρέχουν την καλύτερη λύση στο πρόβλημα. Υπάρχει μια θεωρία, που δείχνει ότι κατά την εφαρμογή τους σε συγκεκριμένα καθήκοντα που δίνουν την καλύτερη δυνατή λύση. Αυτή είναι η θεωρία της matroids. αλγόριθμο του Kruskal αναφέρεται σε τέτοια προβλήματα.

Η εύρεση ενός ελάχιστου βάρους σφαγίου

Είδαν αλγόριθμος κατασκευάζει ένα βέλτιστο πλήθος των πλαισίων. Το πρόβλημα της είναι ως εξής. Dan μη-κατευθυνόμενο γράφημα χωρίς παράλληλες ακμές και βρόχους, και το σύνολο των ακμών δίνεται η συνάρτηση βάρους W, η οποία εκχωρεί τον αριθμό σε κάθε ακμή e - βάρος νεύρωση - w (e). Το βάρος κάθε υποσυνόλου του πλήθους των νευρώσεων είναι το άθροισμα των βαρών των ακμών του. Απαιτείται να βρείτε το σκελετό ενός μικρού βάρους.

περιγραφή

αλγόριθμο του Kruskal λειτουργεί. Πρώτον, όλες οι ακμές του αρχικού γράφου διατεταγμένα σε αύξουσα σειρά των βαρών. Αρχικά, το πλαίσιο δεν περιέχει καμία πλευρά, αλλά περιλαμβάνει όλες τις κορυφές. Μετά το επόμενο βήμα του αλγορίθμου στην ήδη κατασκευαστεί τμήμα του σφαγίου, το οποίο είναι ένα που εκτείνονται σε δάσος, προστίθεται μία άκρη. Δεν έχει επιλεγεί αυθαίρετα. Όλες οι ακμές του γραφήματος, που δεν ανήκουν στο πλαίσιο, μπορεί να ονομάζεται το κόκκινο και το πράσινο. Η κορυφή κάθε κόκκινες άκρες βρίσκονται στην ίδια συνιστώσα υπό συνδεσιμότητα κατασκευή δάσος, και οι πράσινες κορυφές - διαφορετικά. Ως εκ τούτου, αν προσθέσετε στο κόκκινο άκρο, υπάρχει ένας κύκλος, και αν το πράσινο - όπως λαμβάνεται μετά το βήμα αυτό το ξύλο που συνδέονται συστατικά θα είναι μικρότερη από ένα. Έτσι, η προκύπτουσα κατασκευή δεν μπορεί να προσθέσει καμία κόκκινη άκρη, αλλά κάθε πράσινο ακμή μπορεί να προστεθεί για να πάρει το δάσος. Και προσθέτει μια πράσινη άκρη με ελάχιστο βάρος. Το αποτέλεσμα είναι ένα πλαίσιο ελάχιστων βάρους.

εκτέλεση

Χαρακτηρίζει την τρέχουσα δάσος ΣΤ Διαιρεί το σύνολο των κορυφών στον τομέα της συνδεσιμότητας (έντυπα ένωσή τους F, και είναι ξένα μεταξύ τους). Και στις δύο άκρες των κόκκινων κορυφών που βρίσκονται σε ένα κομμάτι. Μέρος (x) - η λειτουργία που για κάθε κορυφή x επιστρέφει ένα τμήμα του ονόματος, ανήκει x. Unite (x, y) - μια διαδικασία που χτίζει ένα νέο διαμέρισμα, που αποτελείται από το συνδυασμό των τμημάτων Χ και Υ και όλα τα άλλα μέρη. Έστω n - αριθμός των ακμών. Όλες αυτές οι έννοιες που περιλαμβάνονται στον αλγόριθμο του Kruskal. εφαρμογή:

1. Τακτοποιήστε όλες τις άκρες του γραφήματος από το 1ο έως n-th βάρη αύξουσα. (Ai, bi - i με την κορυφή αριθμό άκρη).

2. για i = 1 έως η κάνουμε.

3. x: = Μέρος (ai).

4. y: = Μέρος (bi).

5. Αν x δεν ισούται y τότε Unite (x, y), για να συμπεριλάβει με τον αριθμό άκρη F i.

ορθότητα

Έστω T - πλαίσιο του αρχικού γραφήματος κατασκευάστηκε χρησιμοποιώντας τον αλγόριθμο Kruskal και S - αυθαίρετη πλαίσιό του. Πρέπει να αποδείξουμε ότι w (T) δεν είναι μεγαλύτερο από w (S).

Ας M - πλήθος πτερυγίων S, P - μια πληθώρα πτερυγίων T. Εάν S δεν είναι ίσο με Τ, τότε υπάρχει μία νεύρωση πλαίσιο et Τ, που δεν ανήκουν στο S. S. et γειτνιάζουν ο κύκλος, αυτό ονομάζεται C. C αφαιρέσετε από οποιεσδήποτε es άκρη, που ανήκουν Σ Έχουμε αποκτήσει ένα νέο πλαίσιο, επειδή οι ακμές και κορυφές είναι το ίδιο. Το βάρος του δεν είναι μεγαλύτερο από w (S), δεδομένου ότι w (et) δεν είναι πλέον w (ES) σε μια δύναμη αλγόριθμο Kruskal. Αυτή η λειτουργία (υποκατάστατο νευρώσεις Τ S στις νευρώσεις) θα επαναληφθεί για όσο διάστημα λαμβάνετε T. Το βάρος του κάθε μετέπειτα λαμβανόμενου πλαισίου δεν είναι μεγαλύτερη από την προηγούμενη βάρος, πράγμα που σημαίνει ότι w (T) δεν είναι μεγαλύτερο από w (S).

Η ευρωστία του αλγορίθμου Kruskal που προκύπτει από το θεώρημα της Rado-Edmonds στο matroids.

Παραδείγματα Εφαρμογών αλγόριθμος Kruskal

Dan γράφημα με κόμβους a, b, c, d, e και νευρώσεις (α, β), (α, ε), (β, γ), (b, e), (c, d), (γ, ε) , (δ, ε). Τα βάρη των ακμών φαίνονται στον πίνακα και στο σχήμα. Αρχικά, κατασκευή δασικών F περιέχει όλες τις κορυφές του γραφήματος και δεν περιέχει καμία πλευρά. Αλγόριθμος Kruskal προσθέστε πρώτη νεύρωση (α, ε), δεδομένου ότι το βάρος είχε το χαμηλότερο, και οι κορυφές Α και Ε είναι σε διαφορετικά συστατικά συνδεσιμότητα ξυλείας F (νεύρωση (α, ε) είναι πράσινη), τότε η νεύρωση (c, d), επειδή ότι τουλάχιστον το βάρος αυτό ακμή των ακμών γραφήματος, που δεν ανήκουν σε F, και είναι πράσινο, τότε για τους ίδιους λόγους προκύψουν ακμή (a, b). Αλλά η ακμή (β, ε) έχει περάσει, παρά το γεγονός ότι ο ίδιος και το ελάχιστο βάρος των υπολοίπων άκρων, επειδή είναι κόκκινο: οι κορυφές Β και Ε ανήκουν στην ίδια συνιστώσα της σύνδεσης των δασών F, δηλαδή, αν προσθέσουμε σε F την άκρη (β, ε), σχηματίζεται του κύκλου. Στη συνέχεια προστέθηκε πράσινο ακμή (β, γ), διέρχεται κόκκινη άκρη (γ, ε), και στη συνέχεια d, e. Έτσι, οι ακμές προστίθενται διαδοχικά (α, ε), (c, d), (α, b), (β, γ). Από 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).

αλγόριθμο του Kruskal βρίσκει πρακτική εφαρμογή, για παράδειγμα, να βελτιστοποιήσει τις επικοινωνίες λάστιχο, οι δρόμοι σε νέα συγκροτήματα κατοικιών κοινότητες σε κάθε χώρα, καθώς και σε άλλες περιπτώσεις.