Στις αρχές του 19ου αιώνα, το γεωμετρητή του Βερολίνου Jacob Steinerθέστε το καθήκον του πώς να συνδέσετε τρία χωριά έτσι ώστε το μήκος τους να είναι το μικρότερο. Στη συνέχεια, γενικεύτηκε αυτό το πρόβλημα: απαιτείται να βρεθεί ένα σημείο στο αεροπλάνο, έτσι ώστε η απόσταση από αυτό σε άλλα σημεία να είναι η μικρότερη. Τον 20ο αιώνα, οι εργασίες συνεχίστηκαν σε αυτό το θέμα. Αποφασίστηκε να ληφθούν πολλά σημεία και να τα συνδέσετε με τέτοιο τρόπο ώστε η απόσταση μεταξύ τους να είναι η μικρότερη. Όλα αυτά είναι μια ειδική περίπτωση του υπό μελέτη προβλήματος.
Άπληστοι αλγόριθμοι
Ο αλγόριθμος του Kruskal ανήκει στους «άπληστους» αλγόριθμους(ονομάζονται επίσης κλίση). Η ουσία αυτών είναι η μεγαλύτερη απόδοση σε κάθε βήμα. Οι άπληστοι αλγόριθμοι δεν δίνουν πάντα την καλύτερη λύση στο πρόβλημα. Υπάρχει μια θεωρία που δείχνει ότι όταν εφαρμόζεται σε συγκεκριμένα προβλήματα, παρέχουν μια βέλτιστη λύση. Αυτή είναι η θεωρία των μητροειδών. Ο αλγόριθμος του Kruskal ανήκει σε τέτοια προβλήματα.
Βρίσκοντας το πλαίσιο ελάχιστου βάρους
Ο εξεταζόμενος αλγόριθμος κατασκευάζει το βέλτιστογράφημα πλαισίου σύρματος. Το πρόβλημα είναι ως εξής. Σας δίνεται ένα μη κατευθυνόμενο γράφημα χωρίς πολλαπλά άκρα και βρόχους, και στο σύνολο των άκρων του, δίνεται μια συνάρτηση βάρους w, η οποία εκχωρεί σε κάθε άκρη e έναν αριθμό - το βάρος της άκρης - w (e). Το βάρος κάθε υποσυνόλου από το σύνολο των άκρων καθορίζεται από το άθροισμα των βαρών των άκρων του. Απαιτείται να βρείτε το πλαίσιο με το μικρότερο βάρος.
Περιγραφή
Ο αλγόριθμος του Kruskal λειτουργεί έτσι.Πρώτον, όλες οι άκρες του αρχικού γραφήματος είναι διατεταγμένες σε αύξουσα σειρά βαρών. Αρχικά, ο σκελετός δεν περιέχει άκρα, αλλά περιλαμβάνει όλες τις κορυφές του γραφήματος. Μετά το επόμενο βήμα του αλγορίθμου, ένα άκρο προστίθεται στο ήδη κατασκευασμένο τμήμα του σκελετού, το οποίο είναι ένα εκτεταμένο δάσος. Δεν επιλέγεται αυθαίρετα. Όλα τα άκρα του γραφήματος που δεν ανήκουν στο περίγραμμα καλωδίων μπορούν να ονομάζονται κόκκινο και πράσινο. Οι κορυφές κάθε κόκκινου άκρου βρίσκονται στο ίδιο στοιχείο συνδεσιμότητας του υπό κατασκευή δάσους και οι κορυφές του πράσινου άκρου βρίσκονται σε διαφορετικές. Επομένως, εάν προσθέσετε ένα κόκκινο άκρο εκεί, εμφανίζεται ένας κύκλος και εάν είναι πράσινος, το στοιχείο σύνδεσης στο δάσος που λαμβάνεται μετά από αυτό το βήμα θα είναι μικρότερο. Έτσι, δεν μπορεί να προστεθεί κόκκινη άκρη στην προκύπτουσα κατασκευή, αλλά οποιοδήποτε πράσινο άκρο μπορεί να προστεθεί για τη δημιουργία ενός δάσους. Και προστίθεται ένα πράσινο άκρο με ελάχιστο βάρος. Το αποτέλεσμα είναι το ελαφρύτερο πλαίσιο.
Εφαρμογή
Ας υποδηλώσουμε το τρέχον δάσος F.Χωρίζει το σύνολο κορυφών του γραφήματος σε περιοχές σύνδεσης (οι ενώσεις τους σχηματίζουν F και δεν τέμνονται σε ζεύγη). Οι κόκκινες άκρες έχουν και τις δύο κορυφές στο ίδιο τμήμα. Το μέρος (x) είναι μια συνάρτηση που, για κάθε κορυφή x, επιστρέφει το όνομα του τμήματος στο οποίο ανήκει το x. Το Unite (x, y) είναι μια διαδικασία που δημιουργεί ένα νέο διαμέρισμα, που αποτελείται από την ένωση των τμημάτων x και y και όλων των άλλων τμημάτων. Ας είναι ο αριθμός των άκρων στο γράφημα. Όλες αυτές οι έννοιες περιλαμβάνονται στον αλγόριθμο του Kruskal. Εκτέλεση:
Παραγγείλετε όλες τις άκρες του γραφήματος από την 1η έως την 9η με αύξουσα σειρά βαρών. (ai, bi είναι οι κορυφές του άκρου με τον αριθμό i).
για i = 1 έως n.
x: = Μέρος (ai).
y: = Μέρος (bi).
Εάν το x δεν είναι ίσο με το y τότε Unite (x, y), συμπεριλάβετε το άκρο i στο F.
Ορθότητα
Αφήστε το T να είναι ο σκελετός του αρχικού γραφήματος που κατασκευάστηκε χρησιμοποιώντας τον αλγόριθμο Kruskal και το S να είναι ο αυθαίρετος σκελετός του. Πρέπει να αποδείξουμε ότι το w (T) δεν υπερβαίνει το w (S).
Αφήστε το M να είναι το σύνολο των άκρων S, P είναι το σύνολο των άκρωνT. Αν το S δεν είναι ίσο με το T, τότε υπάρχει ένα άκρο et του πλαισίου T που δεν ανήκει στο S. Ας ενωθούμε et στο S. Ένας κύκλος σχηματίζεται, ας το ονομάσουμε C. Αφαιρούμε από το C οποιαδήποτε άκρη ανήκουν στο S. Παίρνουμε ένα νέο πλαίσιο, επειδή οι άκρες, και υπάρχουν τόσες κορυφές σε αυτό. Το βάρος του δεν υπερβαίνει το w (S), αφού το w (et) είναι το πολύ w (es) βάσει του αλγορίθμου Kruskal. Θα επαναλάβουμε αυτήν τη λειτουργία (αντικαθιστώντας τις άκρες S με τις άκρες T) μέχρι να πάρουμε το T. Το βάρος κάθε επόμενου πλαισίου που προκύπτει δεν είναι μεγαλύτερο από το βάρος του προηγούμενου, οπότε προκύπτει ότι το w (T) δεν είναι μεγαλύτερο από w (S).
Επίσης, η ορθότητα του αλγορίθμου Kruskal προκύπτει από το θεώρημα Rado-Edmonds σχετικά με τα matroids.
Παραδείγματα εφαρμογής του αλγορίθμου Kruskal
Σας δίνεται ένα γράφημα με κορυφές a, b, c, d, e και άκρα (a,b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). Τα βάρη των πλευρών φαίνονται στον πίνακα και στο σχήμα. Αρχικά, το υπό κατασκευή δάσος F περιέχει όλες τις κορυφές του γραφήματος και δεν περιέχει άκρα. Ο αλγόριθμος του Kruskal προσθέτει πρώτα το άκρο (a, e), καθώς έχει το μικρότερο βάρος, και οι κορυφές a και e βρίσκονται σε διαφορετικά συνδεδεμένα στοιχεία του δάσους F (η άκρη (a, e) είναι πράσινη) και μετά η άκρη ( c, d), επομένως ότι αυτό το άκρο έχει το μικρότερο βάρος των άκρων του γραφήματος που δεν ανήκει στο F, και είναι πράσινο, τότε το άκρο (a, b) προστίθεται για τους ίδιους λόγους. Αλλά η άκρη (b, e) παραλείπεται, παρόλο που έχει το μικρότερο βάρος από τις υπόλοιπες άκρες, επειδή είναι κόκκινο: οι κορυφές b και e ανήκουν στο ίδιο συνδεδεμένο στοιχείο του δάσους F, δηλαδή, αν προσθέσουμε η άκρη (b, e) έως F, παίρνουμε τον κύκλο. Στη συνέχεια προστίθεται ένα πράσινο άκρο (b, c), ένα κόκκινο άκρο (c, e) παραλείπεται και, στη συνέχεια, d, e. Έτσι, τα άκρα (a, e), (c, d), (a, b), (b, c) προστίθενται διαδοχικά. Ο βέλτιστος σκελετός του αρχικού γραφήματος αποτελείται από αυτούς. Έτσι λειτουργεί ο αλγόριθμος σε αυτήν την περίπτωση Βαμμένο Αυτό το έδειξε ένα παράδειγμα.
Το σχήμα δείχνει ένα γράφημα που αποτελείται από δύο συνδεδεμένα στοιχεία. Οι έντονες γραμμές δείχνουν τις άκρες του βέλτιστου σύρματος (πράσινο) που κατασκευάζεται χρησιμοποιώντας τον αλγόριθμο Kruskal.
Το πάνω σχήμα δείχνει το αρχικό γράφημα και το κάτω δείχνει το πλαίσιο ελάχιστου βάρους που έχει κατασκευαστεί για αυτό χρησιμοποιώντας τον θεωρούμενο αλγόριθμο.
Η ακολουθία των προστιθέμενων ακμών: (1,6); (0.3), (2.6) ή (2.6), (0.3) - δεν έχει σημασία. (3.4) · (0.1), (1.6) ή (1.6), (0.1) είναι επίσης αδιάφορο (5.6).
Ο αλγόριθμος της Kruskal βρίσκει πρακτική εφαρμογή, για παράδειγμα, για τη βελτιστοποίηση της διάταξης επικοινωνιών, δρόμων σε νέες γειτονιές οικισμών κάθε χώρας, καθώς και σε άλλες περιπτώσεις.
