3.1.2 Ο αλγόριθμος του Prim    (Περιεχόμενα)

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

Ο αλγόριθμος του Prim

Βήμα 1: Βρες τον κεντρικό κόμβο του δικτύου

1(α): Υπολόγισε ένα βάρος (weight) για τον κάθε κόμβο i, αντιπροσωπευτικό του αθροίσματος όλης της κυκλοφορίας που εισέρχεται και εξέρχεται από τον κόμβο:

όπου i είναι ένας επιλεγμένος κόμβος από ένα σύνολο n κόμβων,

Τ_i,j είναι η κυκλοφορία που έρχεται από τον κόμβο i στον κόμβο j

T_j,i είναι η κυκλοφορία που έρχεται από τον κόμβο j στον κόμβο i

1(β): Υπολόγισε το βαθμό αξίας (Figure of merit) του κάθε κόμβου, i, ως εξής:

όπου i είναι ένας επιλεγμένος κόμβος από ένα σύνολο n κόμβων,

Cost_i,j είναι το κόστος του καναλιού από τον κόμβο i, στον κόμβο j.

Σημειώστε ότι στην (13), το i δε μπορεί να ισούται με το j.

1(γ): Ταξινόμησε τις αξίες από τις χαμηλότερες στις υψηλότερες

1(δ): Επέλεξε τον κόμβο με τη μικρότερη αξία ως τον κεντρικό σου κόμβο και ονόμασέ τον c.

Βήμα 2: Ανάθεσε κανάλια επικοινωνίας

2(α): Δεδομένων όλων των ζεύξεων (i,j), με i μέσα στο δέντρο και με j έξω από το δέντρο, υπολόγισε L’(i,j) ως εξής:

όπου Cost_i,j είναι το κόστος της ζεύξης μεταξύ των κόμβων i και j,

Cost_i,c είναι το κόστος της ζεύξης μεταξύ των κόμβων i και c

Και α είναι μια παράμετρος σχεδίασης η οποία παίρνει μια τιμή μεταξύ 0 και 1.

2(β): Ταξινόμησε τις τιμές L’(i,j) από τη χαμηλότερη προς την υψηλότερη

2(γ): Έλεγξε να δεις αν όλοι οι κόμβοι έχουν συνδεθεί στο δίκτυο. Αν όχι, συνέχισε στο επόμενο βήμα. Αν ναι, τότε σταμάτα τον αλγόριθμο. Η λύση έχει βρεθεί

2(δ): Επέλεξε τη μικρότερη τιμή L’(i,j) και αφαίρεσέ την από την ταξινομημένη λίστα. Πρόσθεσε τον κόμβο j και το κανάλι (i,j) στο δίκτυο. Έλεγξε να δεις αν έχουν παραβιαστεί κανόνες χωρητικότητας ή κύκλων. Αν έχουν παραβιαστεί, τότε αφαίρεσε τον κόμβο j και το κανάλι (i,j) από το δίκτυο και επέστρεψε στο βήμα 2(α).

2(ε): Ενημέρωσε L’(i,j), ώστε να αντικατοπτρίζει την πρόσθεση ενός νέου κόμβου στο δίκτυο. Επέστρεψε στο βήμα 2(α).

Στη συνέχεια, παρουσιάζουμε ένα παράδειγμα εφαρμογής αυτού του αλγορίθμου. Έστω λοιπόν ότι οι πληροφορίες για το πρόβλημά μας έχουν συλλεχθεί και είναι διαθέσιμες στον πίνακα 3.1 παρακάτω. Ας υποθέσουμε ότι γι’ αυτό το πρόβλημα ότι η μέγιστη κυκλοφοριακή ροή που μπορεί να υπάρχει σε ένα κανάλι είναι 10.000 μονάδες. Επειδή η χωρητικότητα της γραμμής στην περίπτωση αυτή είναι πολύ μεγαλύτερη των ροών στα κανάλια, ο περιορισμός της χωρητικότητας δε λαμβάνεται υπόψη.

Επίλυση του προβλήματος

Βήμα 1: Βρες τον ενδιάμεσο κόμβο του δικτύου

1(α): Υπολόγισε ένα βάρος (weight) για τον κάθε κόμβο i, χρησιμοποιώντας την (12)

1(β): Υπολόγισε το βαθμό αξίας (Figure of merit) του κάθε κόμβου, i, χρησιμοποιώντας την (13)

1(γ): Ταξινόμησε τις αξίες από τις χαμηλότερες στις υψηλότερες. Βλέπε πίνακα 3.2

1(δ): Επέλεξε τον κόμβο με τη μικρότερη αξία ως τον κεντρικό σου κόμβο και ονόμασέ τον c. Βλέπε πίνακα 3.3, στον οποίο φαίνεται ότι ο κόμβος 1 θα πρέπει να επιλεχθεί ως κεντρικός κόμβος

Βήμα 2: Ανάθεσε κανάλια επικοινωνίας

2(α): Δεδομένων όλων των ζεύξεων (i,j), με i μέσα στο δέντρο και με j έξω από το δέντρο, υπολόγισε L’(i,j). Θέσε την παράμετρο σχεδίασης α=1. Βλέπε πίνακα 3.4 για τους υπολογισμούς της πρώτης επανάληψης.

2(β): Ταξινόμησε τις τιμές L’(i,j) από τη χαμηλότερη προς την υψηλότερη. Βασιζόμενοι στον πίνακα 3.4 αυτή αντιστοιχεί στις τιμές 80, 1074 και 1307.

2(γ): Έλεγξε να δεις αν όλοι οι κόμβοι έχουν συνδεθεί στο δίκτυο. Μόνο ο κεντρικός κόμβος είναι στο δίκτυο αυτή τη στιγμή.

2(δ): Επέλεξε τη μικρότερη τιμή L’(i,j) και αφαίρεσέ την από την ταξινομημένη λίστα. Πρόσθεσε τον κόμβο j και το κανάλι (i,j) στο δίκτυο. Έλεγξε να δεις αν έχουν παραβιαστεί κανόνες χωρητικότητας ή κύκλων. Αν έχουν παραβιαστεί, τότε αφαίρεσε τον κόμβο j και το κανάλι (i,j) από το δίκτυο και επέστρεψε στο βήμα 2(α). Η μικρότερη τιμή για το L’(i,j) είναι 80 και αντιστοιχεί στο σύνδεσμο (1,2), ο οποίος δεν παραβιάζει κανένα περιορισμό

2(ε): Ενημέρωσε L’(i,j), ώστε να αντικατοπτρίζει την πρόσθεση ενός νέου κόμβου στο δίκτυο. Υπολόγισε το κόστος της εισαγωγής των υπολοίπων κόμβων στο δίκτυο, είτε διαμέσου του κεντρικού κόμβου, είτε με προσάρτηση στο τέλος του δένδρου που έχει έως τώρα δημιουργηθεί από το κέντρο. Βλέπε πίνακα 3.5

2(στ):Ταξινόμησε τις τιμές L’(i,j) από τη χαμηλότερη προς την υψηλότερη. Βασιζόμενοι στον πίνακα 3.5 αυτή αντιστοιχεί στις τιμές 1074, 1234, 1307 και 1467.

2(ζ): Έλεγξε να δεις αν όλοι οι κόμβοι έχουν συνδεθεί στο δίκτυο. Οι κόμβοι 1 και 2 έχουν συνδεθεί, ενώ οι 3 και 4 βρίσκονται ακόμη έξω. Ο αλγόριθμος προχωρεί στο επόμενο βήμα.

2(η): Επέλεξε τη μικρότερη τιμή L’(i,j) και αφαίρεσέ την από την ταξινομημένη λίστα. Πρόσθεσε τον κόμβο j και το κανάλι (i,j) στο δίκτυο. Η μικρότερη τιμή είναι η 1074 που αντιστοιχεί στο σύνδεσμο (1,4). Η L’(i,j) που υπολογίστηκε για τη σύνδεση του κόμβου 3 στον κόμβο 2 είναι 1467, και η τιμή που υπολογίστηκε για τη σύνδεση του κόμβου 4 στον κόμβο 2 είναι 1237. Από τη στιγμή που αυτές οι τιμές είναι υψηλότερες απ’ ότι το κόστος της σύνδεσης του κόμβου 4 απευθείας στον κεντρικό κόμβο, οι σύνδεσμοι που σχετίζονται με αυτούς δεν επιλέγονται.

2(θ): Ενημέρωσε L’(i,j), ώστε να αντικατοπτρίζει την πρόσθεση ενός νέου κόμβου στο δίκτυο. Βλέπε πίνακα 3.6

2(ι):Ταξινόμησε τις τιμές L’(i,j) από τη χαμηλότερη προς την υψηλότερη. Βασιζόμενοι στον πίνακα 3.6 αυτή αντιστοιχεί στις τιμές 1307, 1234, και 1467.

2(κ): Έλεγξε να δεις αν όλοι οι κόμβοι έχουν συνδεθεί στο δίκτυο. Οι κόμβοι 1, 2 και 4 έχουν συνδεθεί, ενώ ο 3 βρίσκεται ακόμη έξω. Ο αλγόριθμος προχωρεί στο επόμενο βήμα.

2(λ): Επέλεξε τη μικρότερη τιμή L’(i,j) και αφαίρεσέ την από την ταξινομημένη λίστα. Πρόσθεσε τον κόμβο j και το κανάλι (i,j) στο δίκτυο. Η μικρότερη τιμή είναι η 1307 που αντιστοιχεί στο σύνδεσμο (1,3).

2(μ): Έλεγξε να δεις αν όλοι οι κόμβοι έχουν συνδεθεί στο δίκτυο. Όλοι οι κόμβοι έχουν συνδεθεί. Ο αλγόριθμος τερματίζεται.

Στο παρακάτω σχήμα απεικονίζονται και με τη βοήθεια γραφημάτων οι τέσσερις επαναλήψεις του αλγορίθμου.