Σημειώσεις:Επικαλυπτικά Δέντρα
Από DistrSys
| MST |
| Πρόβλημα: Κατανεμημένες Δομές Δίκτυο: Γενικό Κλάση: {{{class}}} |
|
|
| Πολυπλοκότητα |
| Χρονική: {{{time}}} Επικοινωνίας: {{{communication}}} |
|
|
| Στη σύνταξη του κειμένου συνεισέφεραν οι Απόστολος Φίλιππας Βασίλειος Γεωργιτζίκης |
Πίνακας περιεχομένων |
Επικαλυπτικά Δέντρα Ελαχίστου Ύψους (Minimum Spanning Tree)
Το πρόβλημα είναι το να βρούμε ένα ελάχιστο, ή ελαχίστου βάρους επικαλυπτικό δέντρο (MST) σε εναν μή κατευθυντικό γράφο με ακμές με βάρος. Η βασική χρησιμότητα αυτού του δέντρου είναι οι επικοινωνίες εκπομπής σε όλο το δίκτυο (broadcast communications). Ένα MST μπορεί να ελαχιστοποιήσει το συνολικό κόστος της επικοινωνίας οποιαδήποτε διεργασίας σε όλες τις άλλες διεργασίες του δικτύου.
Το πρόβλημα
Ένα επικαλυπτικό δάσος ενός μή κατευθυντικού γράφου G =(v,E) είναι ένα δάσος (π.χ. ένας γράφος που είναι άκυκλος αλλά δεν είναι κατ ανάγκη συνδεδεμένος) που αποτελείται αποκλειστικά απο μή κατευθυντικές ακμές του E και περιέχει κάθε διεργασία του G. Ένα επικαλυπτικό δέντρο ενός μή κατευθυντικού γράφου G είναι ένα επικαλυπτικό δάσος του G το οποίο είναι συνδεδεμένο. Άν υπάρχουν βάρη σε αντιστοιχία με τις μή κατευθυντικές ακμές του E, τότε το βάρος οποιουδήποτε απο τους υπογράφους του G (όπως ένα επικαλυπτικό δέντρο ή ένα επικαλυπτικό δάσος του G) ορίζεται ως το άθροισμα των βαρών των ακμών του.
Αξίζει να σημειωθεί οτι μεταβάλουμε τον βασικό, μή κατευθυντικό γράφο στο δικό μας κατευθυντικό μοντέλο ως έναν κατευθυντικό γράφο έχωντας ακμές διπλής κατεύθυνσης μεταξύ όλων των γειτονικών ζευγαριών Θεωρούμε οτι κάθε κατευθυντική ακμή e=(i,j) αντιστοιχεί με έναν θετικό πραγματικό αριθμό βάρους (weight), weight(e) = 
, και υποθέτουμε πως για όλα τα i και j, =. Επίσης υποθέτουμε πως όλες οι διεργασίες γνωρίζουν αρχικά το βάρος όλων των 'προσκείμενων' ακμών της, ή, πιό συγκεκριμένα, οτι το βάρος μιας ακμής αντιπροσωπεύεται σωστά στις μεταβλητές weight των διεργασιών που συνδέει. Θεωρούμε οτι οι διεργασίες έχουν UIDs και πως γνωρίζουν το πλήθος τους n. Το πρόβλημα είναι να βρούμε ενα ελαχίστου ύψους (μή κατευθυντικό) επικαλυπτικό δέντρο για ολόκληρο το δίκτυο, και πιο συγκεκριμένα, η κάθε διεργασία πρέπει να αποφασίσει ποιές απο τις προσκείμενες ακμές είναι μέρος του MST και ποιές όχι.
Βασική Θεωρία
Όλοι οι γνωστοί αλγόριθμοι MST (Minimum Spanning Tree), διαδοχικοί και ταυτόχρονοι, βασίζονται στην ίδια θεωρία, την οποία αναλύουμε σε αυτό το τμήμα. Η βασιή στρατηγική για την δημιουργία ενός ελαχίστου επικαλυπτικού δέντρου περιλαμβάνει το ξεκίνημα με το μηδαμινό επικαλυπτικό δάσος αποτελούμενο απο n ξεχωριστούς κόμβους και την επαναλαμβανόμενη συνένωση των κόμβων συνδεδεμένων ακμών μέχρι να δημιουργηθεί ένα επικαλυπτικό δέντρο. Για να φτάσουμε σε ένα ελάχιστο επικαλυπτικό δέντρο, είναι σημαντικό η συνένωση να γίνει μόνο σε συγκεκριμένες επιλεγμένες ακμές -συγκεκριμένα, αυτές που έχουν το ελάχιστο εξερχόμενο βάρος. Αιτιολόγηση για αυτό τη μέθοδο επιλογής δίνεται απο το παρακάτω λήμμα.
Λήμμα
Έστω G=(V,E) ένας μή κατευθυντικός γράφος με βάρη, και έστω 
Έστω οτι υπάρχει ακμή ελαχίστου βάρους.
{e' : e' έχει ακριβώς μία άκρη στο V }
Επομένως υπάρχει επικαλυπτικό δέντρο για τον G που περιλαμβάνει το 
και e, και αυτό το δέντρο έχει το λιγότερο βάρος απο όλα τα επικαλυπτικά δέντρα για τον G που περιλαμβάνουν το .
Απόδειξη
Η απόδειξη γίνεται με χρήση αντίφασης. Υποθέτουμε οτι ο ισχυρισμός είναι λανθασμένος - επομένως, οτι υπάρχει επικαλυπτικό δέντρο T που περιέχει το , δεν περιέχει το e, και έχει μικρότερο βάρος απο οποιοδήποτε άλλο επικαλυπτικό δέντρο που περιέχει τα και e. Τώρα έστω T' ο γράφος που παίρνουμε απο την πρόσθεση του e στο T. Προφανώς το T' περιέχει έναν κύκλο, που έχει μια άλλη ακμή e' 
e που είναι εξερχόμενο απο το 
.
Με τηνν επιλογή του e, ξέρουμε οτι το weight(e') >= weight(e). Τώρα, λαμβάνουμε υπόψιν τον γράφο T, που δημιουργείται απο την διαγραφή του e' απο τον T'. Επομένως, το T είναι ένα επικαλυπτικό δέντρο για τον G που περιέχει τα UjEj και e, και το βάρος του δεν είναι μεγαλύτερο απο αυτό του T. Αυτό όμος δημιουργεί αντίφαση στην ισχυριζόμενη ιδιότητα του T.
Το παραπάνω λήμμα παρέχει την αιτιολόγηση για την παρακάτω γενική στρατηγική για τη δημιουργία ενός MST.
Γενική στρατηγική για ένα MST:
Ξεκινάμε με ένα μηδαμινό επικαλυπτικό δέντρο που αποτελείται απο μεμονομένους κόμβους και καμμία ακμή. Στη συνέχεια επαναλαμβάνουμε τα εξής: Επιλέγουμε ένα αυθαίρετο μέρος C του δάσους και μία αυθαίρετη εξερχόμενη ακμή e απο το C που έχει το ελάχιστο βάρος ανάμεσα στις εξερχόμενες ακμές του C. Συνδυάζουμε το C με το στοιχείο στην άλλη μεριά του e, συμπεριλαμβανομένης της e στο καινούργιο συνδιασμένο στοιχείο. Σταματάμε όταν το δάσος έχει μόνο ένα και μοναδικό στοιχείο.
Το παραπάνω λήμμα μπορεί να χρησιμοποιηθεί ώς επαγωγική απόδειξη που δείχνει ότι, σε οποιοδήποτε βήμα της δημιουργίας του MST, το δάσος είναι ένας υπογράφος του MST. Πολλοί γνωστοί διαδοχικοί αλγόριθμοι MST αποτελούν ειδικές περιπτώσεις αυτής της γενικής στρατηγικής. Για παράδειγμα, ο αλγόριθμος Prim-Dijkstra ξεκινάει με την διάκριση ενός εκ των αρχικών στοιχείων μονών κόμβων και επαναλαμβανόμενα προσθέτει την εξερχόμενη ακμή ελαχίστου βάρους απο το τρέχον στοιχείο, προσθέτοντας κάθε φορά ένα μόνο κόμβο μέχρι να ληφθεί ένα πλήρες επικαλυπτικό δέντρο. Ένα άλλο παράδειγμα είναι ο αλγόριθμος Kruskal ο οποίος προσθέτει επαναλαμβανόμενα την ακμή ελαχίστου βάρους ανάμεσα σε όλες τις ακμές που συνδέουν δύο ξεχωριστά στοιχεία μέχρι να υπάρξει μόνο ένα στοιχείο, που θα είναι το τελικό επικαλυπτικό δέντρο.
Για να χρησιμοποιηθεί η γενική στρατηγική σε μία κατανεμημένη εφαρμογή, θα ήταν καλό να είναι εφικτή η επέκταση του δάσους με ταυτόχρονο καθορισμό πολλαπλών ακμών. Δηλαδή, καθένα απο τα πολλά στοιχεία μπορεί να προσδιορίσει την εξερχόμενη ακμή ελαχίστου βάρους του ανεξάρτητα, και όλες οι προσδιορισμένες ακμές μπορούν να προστεθούν στο δάσος, και ώς εκ τούτου να προκαλέσουν πολλές ενώσεις στοιχείων να συμβούν μαζί. Το λήμμα όμως δεν μας εγγυάται την ορθότητα της παράλληλης αυτής στρατηγικής. Στην πραγματικότητα, σε γενικές γραμμές αυτή η στρατηγική δεν είναι σωστή.
Παράδειγμα - Δημιουργία κύκλων με παράλληλο αλγόριθμο MST
Έστω ο παρακάτω γράφος. Οι τελείες αντιπροσωπεύουν στοιχεία στο επικαλυπτικό δάσος. Οι τρείς ακμές με βάρη 1 είναι οι μόνες εξερχόμενες ακμές. Άν τα στοιχεία επιλέξουν τις εξερχόμενες ακμές ελαχίστου βάρους τους όπως φαίνεται απο τα βέλη, τότε θα δημιουργηθεί κύκλος.
Το πρόβλημα του κύκλου είναι όμως δυνατόν να αποφευχθεί, όμως, στην ειδική περίπτωση που όλες οι ακμές έχουν διακριτά βάρη. Αυτό ισχύει απο το παρακάτω λήμμα:
Λήμμα
Άν όλες οι ακμές ενός γράφου G έχουν διακριτά βάρη, τότε υπάρχει μόνο ένα MST για τον G.
Απόδειξη
Η απόδειξη είναι παρόμοια με την απόδειξη του πρώτου λήμματος. Έστω οτι υπάρχουν δυο διακριτά MST, τα T και T', και έστω e η ακμή ελαχίστου βάρους που υπάρχει μόνο στο ένα απο τα δύο δέντρα. Υποθέτουμε (χωρίς να χάνεται η γενικότητα) οτι e 
T. Τότε ο γράφος T που λαμβάνεται απο την πρόσθεση του e στον T περιέχει έναν κύκλο, και τουλάχιστον μία απο τις ακμές αυτού του κύκλου, e', δεν είναι στο T. Αφού τα βάρη των ακμών είναι διακριτά και η e' είναι σε μόνο ένα απο τα δύο δέντρα, πρέπει να έχουμε weight(e') > weight(e), με την επιλογή μας του e. Τότε αφαιρόντας το e' απο το T παράγεται ένα επικαλυπτικό δέντρο με μικρότερο βάρος απο το T', πράγμα που αποτελεί αντίφαση.
Τώρα ας αναθεωρήσουμε την γενική στρατηγική για την περίπτωση που ο γράφος έχει διακριτά βάρη σε κάθε ακμή, και επομένως, σύμφωνα με το δεύτερο λήμμα, υπάρχει ένα μοναδικό MST. Σε αυτή την περίπτωση, σε οποιοδήποτε στάδιο της δημιουργίας του MST, οποιοδήποτε στοιχείο στο δέντρο έχει ακριβώς μία εξερχώμενη ακμή ελαχίστου βάρους (την οποία συντομέβουμε σε MWOE- Minimum Weight Outgoing Edge). Το πρώτο λήμμα υπαινίσσεται οτι αν ξεκινήσουμε ένα βήμα με ένα δέντρο, όλες οι ακμές του οποίου ανήκουν στο μοναδικό MST, τότε όλες οι MWOE, για όλα τα στοιχεία, είναι επίσης στο μοναδικό MST. Οπότε μπορούμε να τις προσθέσουμε όλες με τη μία, χωρίς κανέναν κίνδυνο δημιουργίας κύκλου.
Ο αλγόριθμος SynchGHS
Ο αλγόριθμος χτίζει τα στοιχεία σε 'επίπεδα'. Για κάθε k, το στοιχεία του επιπέδου k αποτελούν ενα επικαλυπτικό δάσος, όπου το κάθε στοιχείο επιπέδου k αποτελείται απο ένα δέντρο που είναι υπογράφος του MST. Κάθε στοιχείο του επιπέδου k έχει τουλάχιστον 2^k κόμβους. Κάθε στοιχείο, σε κάθε επίπεδο, έχει ένα διακριτό κόμβο αρχηγό. Οι διεργασίες επιτρέπουν έναν συγκεκριμένο αριθμό γύρων, ο οποίος είναι O(n) για να ολοκληροθεί κάθε επίπεδο.
Ο αλγόριθμος ξεκινάει με τις συνιστώσες του επιπέδου 0 να αποτελούνται απο μεμονομένους κόμβους και καμμία ακμή. Υποθέτουμε επαγψγικά οτι οι συνιστώσες του επιπέδου k έχουν καθοριστεί (μαζί με τους αρχηγούς τους). Πιο συγγεκριμένα, θεωρούμε οτι κάθε διεργασία γνωρίζει το UID (Unique ID) του αρχηγού της συνιστώσας της. Αυτό το UID χρησιμοποιείται σαν αναγνωριστικό για ολόκληρη τη συνιστώσα. Κάθε διεργασία γνωρίζει επίσης ποιά απο τις προσπίπτουσες ακμές της ανήκουν στο δέντρο.
Για να λάβουμε της k+1 συνιστώσες, κάθε συνιστόσα επιπέδου k διενεργεί μια έρευνα κατα μήκως των ακμών του επικαλυπτικού δέντρου της για την MWOE της συνιστώσας. Ο αρχηγός εκπέμπει αιτήματα εύρεσης κατα μήκως των ακμών, χρησιμοποιώντας μια στρατηγική BFS. Κάθε διεργασία βρίσκει, ανάμεσα των προστπίπτουσων ακμών της, την μία με το ελάχιστο βάρος που είναι εξερχόμενη απο την συνιστώσα (άν υπάρχει τέτοια). Αυτό το κάνει με το να στέλνει δοκιμαστικά μηνύματα κατα μήκος όλων των ακμών της που δεν ανήκουν στο δέντρο,ρωτώντας εάν η διεργασία στην άλλη άκρη της ακμής ανήκει στην ίδια συνιστώσα. Αυτός ο προσδιορισμός γίνεται με την σύγκριση των αναγνωριστικών των συνιστωσών. Στη συνέχεια, η διεργασίες στέλνουν συγκλίνοντας αυτή την τοπική ακμή ελαχίστου βάρους προς τον αρχηγό, παίρνοντας τις ελάχιστες τιμές στον δρόμο τους. Η ελάχιστη τιμή απο όλες που θα λάβει ο αρχηγός είναι το MWOE ολόκληρης της συνιστόσας.
Όταν όλες οι συνιστώσες του επιπέδου k έχουν βρεί τα MWOE τους, οι συνιστώσες συνδυάζονται με όλα αυτά τα MWOE για να δημιουργήσουν τις συνιστώσες επιπέδου k+1. Για να γίνει αυτό ο αρχηγός της κάθε συνιστώσας επιπέδου k επικοινωνεί με την διεργασία που γειτονέβει με το MWOE λέγοντας της να θέσει την ακμή της ως υπάρχουσα στο δέντρο. Η διεργασία στο άλλο άκρο της ακμής επίσης ενημερώνεται ώστε να τεθεί ως μέρος του δέντρου.
Στη συνέχεια ένας νέος αρχηγός διαλέγεται για κάθε συνιστώσα του επιπέδου k+1, ώς εξής: Μπορεί να δειχθεί οτι για κάθε γκρούπ απο συνιστώσες επιπέδου k που μπορούν να συνδυαστούν σε μία συνιστώσα επιπέδου k+1, υπάρχει μια μοναδική ακμή e που είναι το κοινό MWOE δύο εκ των k συνιστώσων του γκρούπ. Θέτουμε τον καινούργιο αρχηγό να είναι η διεργασία με το μεγαλύτερο UID (εκ των δύο) που προσπίπτει στην e. Παρατηρούμε οτι ο αρχηγός μπορεί να αναγνωρίσει τον εαυτό του χρησιμοποιώντας μόνο τοπικά δεδομένα.
Τέλος, το UID του καινούργιου αρχηγού εκπέμπεται (broadcast) και έτσι διαδίδεται σε όλη την συνιστώσα.
Παράδειγμα: Ένας γράφος στον οποίο κάθε κόμβος έχει ακριβώς μία εξερχόμενη ακμή. Παρατηρήστε τον μοναδικό κύκλο.
Εν τέλει, μετά απο κάποιο αριθμό γύρων, το επικαλυπτικό δάσος αποτελείται απο μόνο μία συνιστώσα που περιλαμβάνει όλους τους κόμβους του δικτύου. Μετά μια νέα προσπάθεια να βρούμε ένα MWOE θα αποτύχει, επειδή καμμία διεργασία δεν θα βρεί μια εξερχόμενη ακμή. Όταν ο αρχηγός το μάθει αυτό, εκπέμπει ένα μήνυμα λέγοντας οτι ο αλγόριθμος έχει ολοκληρωθεί.
