3.2.2 O αλγόριθμος του Esau-William’s (E-W algorithm) για δενδρικές δομές    (Περιεχόμενα)

Στο τμήμα αυτό περιγράφουμε τον αλγόριθμο χωρητικότητας των Esau-William’s, του ελάχιστου δένδρου καλύμματος (E-W capacitated minimal spanning tree algorithm). Ο αλγόριθμος αυτός ονομάζεται αλγόριθμος χωρητικότητας (capacitated), γιατί δημιουργεί ένα ελάχιστο δένδρο κάλυμμα το οποίο έχει σχεδιαστεί έτσι ώστε να συμμορφώνεται με τους περιορισμούς της χωρητικότητας του καναλιού και το οποίο ονομάζεται ελάχιστο δένδρο κάλυμμα χωρητικότητας.

Ο αλγόριθμος των Esau-William’s (E-W)

Ο αλγόριθμος αυτός ξεκινά ενώνοντας όλους τους σταθμούς στον κεντρικό κόμβο. Στη συνέχεια επιχειρεί να αντικαταστήσει τα κανάλια, ένα - ένα, με φθηνότερα. Όταν προστίθεται ένα νέο κανάλι στο δέντρο, η αντίστοιχη σύνδεση στον κεντρικό κόμβο διαγράφεται. Κατά την επιλογή των καναλιών, ελέγχονται οι περιορισμοί για κύκλους στο γράφο και για την ροή της κυκλοφορίας και δεν επιτρέπονται οι αλλαγές καναλιών (πρόσθεσή τους δηλαδή στο δέντρο και αφαίρεσή τους από τον κεντρικό κόμβο), εάν κριθεί ότι αυτά παραβιάζουν τους παραπάνω περιορισμούς.

Βήμα 1: Ένωσε όλους τους κόμβους στον κεντρικό κόμβο

Βήμα 2: Υπολόγισε μια τιμή ανταλλαγής d_ij, η οποία θα αντιπροσωπεύει τη διαφορά ανάμεσα στο κόστος C_ij της σύνδεσης (i,j) και του κόστους C_i,l της σύνδεσης του τερματικού i στον κεντρικό κόμβο l.

(υπολόγισε για όλα τα i, j, όπου l είναι το κεντρικό σημείο)

Βήμα 3: Ταξινόμησε τα κανάλια με βάση την τιμή d_ij από τη χαμηλότερη προς την υψηλότερη

Βήμα 4: Αφαίρεσε όλα τα κανάλια με τιμή d_ij ίση με ή μεγαλύτερη από το μηδέν. Αν κανένα κανάλι δεν έχει μια αρνητική d_ij τιμή, τότε ο αλγόριθμος τερματίζει και το δίκτυο παραμένει ως έχει.

Βήμα 5: Επέλεξε το κανάλι με τη μικρότερη τιμή (την πιο αρνητική) d_ij. Έλεγξε για τυχόν κύκλους που μπορεί να δημιουργούνται από το επιλεγμένο κανάλι.

·        Αν το κανάλι δημιουργεί κύκλο, τότε θέσε την τιμή d_ij = +¥ και επέστρεψε στο βήμα 4.

·        Αν το κανάλι δε δημιουργεί κύκλο, έλεγξε αν μπορεί να χειριστεί το απαιτύμενο κυκλοφοριακό φορτίο.

o       Αν το κανάλι έχει αρκετή χωρητικότητα για να εξυπηρετήσει την απαιτούμενη κυκλοφορία, τότε αντικατέστησε το κανάλι (i,1) με το κανάλι (i,j). Υπολόγισε εκ νέου τις επηρεασμένες τιμές d_ij, ώστε να αντικατοπτρίζεται το γεγονός ότι ο κόμβος i είναι πια συνδεδεμένος στον κόμβο j και όχι στον κεντρικό κόμβο. Κατά συνέπεια, αντικατέστησε το C_i1 με το C_ij στους υπολογισμούς σου για το d_ij. Επέστρεψε στο βήμα 2.

o       Αν το κανάλι δεν έχει αρκετή χωρητικότητα για να χειριστεί την απαιτούμενη κυκλοφορία, τότε μην αντικαταστήσεις το κανάλι. Απλά θέσε d_ij = +¥ και επέστρεψε στο βήμα 2.

Τώρα θα παρουσιάσουμε ένα παράδειγμα της εφαρμογής του αλγορίθμου E-W. Οι πληροφορίες κόστους και δεδομένων φαίνονται στους πίνακες παρακάτω. Υποθέστε επίσης, ότι ο περιορισμός της ροής της κυκλοφορίας είναι 10 μονάδες. Θέλουμε να βρούμε εκείνο το δενδρικό δίκτυο που να συνδέει τους σταθμούς εργασίας 2,3,4 και 5 στον κεντρικό κόμβο 1 με το ελάχιστο κόστος.

Επίλυση του προβλήματος χρησιμοποιώντας τον αλγόριθμο E-W CMST

Βήμα 1: Ένωσε όλους τους κόμβους στον κεντρικό κόμβο. Αυτό φαίνεται στο πρώτο διάγραμμα του σχήματος 16.

Βήμα 2: Υπολόγισε μια τιμή ανταλλαγής d_ij, η οποία θα αντιπροσωπεύει τη διαφορά ανάμεσα στο κόστος C_ij της σύνδεσης (i,j) και του κόστους C_i,1 της σύνδεσης του τερματικού i στον κεντρικό κόμβο l.

Βήμα 3: Ταξινόμησε τα κανάλια με βάση την τιμή d_ij από τη χαμηλότερη προς την υψηλότερη. Βλέπε πίνακα 3.10

Βήμα 4: Αφαίρεσε όλα τα κανάλια με τιμή d_ij ίση με ή μεγαλύτερη από το μηδέν. Βλέπε πίνακα 3.11. Από τη στιγμή που κανένα κανάλι δεν έχει αρνητική d_ij τιμή, ο αλγόριθμος προχωρά.

Βήμα 5: Επέλεξε το κανάλι με τη μικρότερη τιμή (την πιο αρνητική) d_ij. Έλεγξε για τυχόν κύκλους που μπορεί να δημιουργούνται από το επιλεγμένο κανάλι. Το κανάλι είναι το (2,3), το οποίο αντικαθιστά το (2,1). Το (2,3) δε δημιουργεί κύκλο. Η συνδυασμένη κυκλοφορία των καναλιών (2,3) και (3,1) ισούται με 9 μονάδες που σημαίνει ότι δεν υπερβαίνει τον περιορισμό της κυκλοφορίας των 10 μονάδων. Οπότε το κανάλι επιλέγεται για αντικατάσταση του (2,1) και d_2,3 = C_2,3 - C_2,3 = 0. Ενημερώνοντας τις άλλες d_ij μεταβλητές που επηρεάστηκαν από τη μεταβολή: d_2,4 = C_2,4 - C_2,3 = (5-3)=2 και d_2,5 = C_2,5 - C_2,3 = (7-3) = 4. Αφού οι τιμές αυτές είναι θετικές δε χρειάζεται να ασχοληθούμε με αυτές τις γραμμές στην πορεία της εξέτασης της αντικατάστασής τους.

Βήμα 6: Επιστρέφοντας στο βήμα 4, απομακρύνουμε όλες τις συνδέσεις με τιμή d_ij μεγαλύτερη ή ίση του μηδενός. Από τη στιγμή που ακόμη υπάρχουν αρνητικές τιμές προχωράμε με την επίλυση του αλγορίθμου (πίνακας 3.12).

Βήμα 7: Επέλεξε το κανάλι με τη μικρότερη τιμή (την πιο αρνητική) d_ij. Έλεγξε για τυχόν κύκλους που μπορεί να δημιουργούνται από το επιλεγμένο κανάλι. Όπως φαίνεται στον πίνακα 3.12, το κανάλι (5,4) αντικαθιστά το (5,1). Το (5,4) δε δημιουργεί κύκλο. Η συνδυασμένη κυκλοφορία των καναλιών (5,4) και (4,1) ισούται με 8 μονάδες που σημαίνει ότι δεν υπερβαίνει τον περιορισμό της κυκλοφορίας των 10 μονάδων. Οπότε το κανάλι επιλέγεται για αντικατάσταση του (5,1) και d_5,4 = C_5,4 - C_5,4 = 0. Ενημερώνοντας τις άλλες d_ij μεταβλητές που επηρεάστηκαν από τη μεταβολή: d_5,3 = C_5,3 - C_5,4 = (5-3)=2, d_5,2 = C_5,2 - C_5,4 = (7-3) = 4 και d_4,5 = C_4,5 - C_4,5 = 0. Αφού οι τιμές αυτές είναι θετικές δε χρειάζεται να ασχοληθούμε με αυτές τις επικοινωνιακές γραμμές στην πορεία εξέτασης της αντικατάστασής τους.

Βήμα 8: Επιστρέφοντας στο βήμα 4, απομακρύνουμε όλες τις συνδέσεις με τιμή d_ij μεγαλύτερη ή ίση του μηδενός. Από τη στιγμή που ακόμη υπάρχουν αρνητικές τιμές προχωράμε με την επίλυση του αλγορίθμου (πίνακας 3.13).

Βήμα 9: Επέλεξε το κανάλι με τη μικρότερη τιμή (την πιο αρνητική) d_ij. Έλεγξε για τυχόν κύκλους που μπορεί να δημιουργούνται από το επιλεγμένο κανάλι. Το επιλεγμένο κανάλι είναι το(4,3). Αυτό το κανάλι θα υπερβεί τον περιορισμό στην κυκλοφορία των 10 μονάδων, μιας και οι κόμβοι 2,3,4 και 5 θα δημιουργήσουν μια συνδυασμένη κυκλοφορία 17 μονάδων. Οπότε το κανάλι απορρίπτεται και
d_ij = +¥.

Βήμα 10: Επιστρέφοντας στο βήμα 4, απομακρύνουμε όλες τις συνδέσεις με τιμή d_ij μεγαλύτερη ή ίση του μηδενός. Από τη στιγμή που δεν υπάρχουν αρνητικές τιμές, ο αλγόριθμος σταματά.