Η εύρεση γεννητικών δέντρων ελάχιστου-κόστους αποτελεί ένα κλασικό επιστημονικό πρόβλημα με σημαντικές εφαρμογές στη σχεδίαση δικτύων. Δοθέντος ενός γραφήματος, όπου κάθε πλευρά σχετίζεται με ένα βάρος (κριτήριο) το πρόβλημα της εύρεσης ενός Ελάχιστου Γεννητικού Δέντρου ανέρχεται στο πρόβλημα της εύρεσης ενός γεννητικού δέντρου με το ελάχιστο συνολικό κόστος. Το πρόβλημα ΕΓΔ έχει αποτελέσει αντικείμενο ενδιαφέροντος πολλών μελετητών με αποτέλεσμα την ανάπτυξη αλγορίθμων πολυωνυμικού-χρόνου, όπως είναι ο αλγόριθμος του Prim, του Sollin και του Kruskal. Στον πραγματικό κόσμο όμως υπάρχουν περιπτώσεις όπου πρέπει να λάβουμε ταυτόχρονα υπόψη πολλά κριτήρια προκειμένου να καθορίσουμε ένα ΕΓΔ. Αυτό συμβαίνει γιατί κάθε πλευρά του γραφήματος σχετίζεται με παραπάνω από ένα κόστη. Για παράδειγμα, στη σχεδίαση ενός τηλεπικοινωνιακού δικτύου, πέρα από το κόστος κατασκευής των συνδέσεων μεταξύ των πόλεων ή των τερματικών μας ενδιαφέρουν και άλλοι παράγοντες. Ο χρόνος που απαιτείται για την κατασκευή, η δυσκολία και πολυπλοκότητα της κατασκευής, η καθυστέρηση μετάδοσης της πληροφορίας αλλά και η αξιοπιστία του συστήματος αποτελούν σημαντικούς παράγοντες που πρέπει να ληφθούν υπόψη στην σχεδίαση του δικτύου. Αλλά και στην καθημερινή ζωή, πολλές φορές χρειάζεται να ληφθούν σημαντικές αποφάσεις οι οποίες εξαρτώνται από περισσότερα από ένα κριτήρια. Παραδείγματος χάριν, άνθρωποι που ταξιδεύουν θέλουν να βελτιστοποιήσουν τη διανυόμενη απόσταση, το κόστος, και το χρόνο μετακίνησης. Το ζητούμενο είναι πως μπορεί να οδηγηθεί κανείς στη λήψη μιας βέλτιστης για αυτόν απόφασης, που κάτω από δεδομένες συνθήκες μπορεί να είναι περισσότερες από μία. Δηλαδή, δεν οδηγούμαστε σε μία μοναδική βέλτιστη λύση αλλά σε ένα σύνολο από «βέλτιστες» λύσεις και ο ενδιαφερόμενος, ανάλογα με τα ιδιαίτερα χαρακτηριστικά του προβλήματος, κάνει την τελική επιλογή. Το πρόβλημα ΕΓΔ, στο οποίο ζητείται η ελαχιστοποίηση περισσοτέρων του ενός κριτηρίων είναι γνωστό ως το πρόβλημα ΕΓΔ πολλαπλών κριτηρίων (multi-criteria minimum spanning tree problem). Η συνεισφορά της παρούσας διπλωματικής λοιπόν αποτελείται από δύο μέρη: Το πρώτο, εστιάζεται στην κριτική επισκόπηση και περιγραφή των υπαρχόντων μεθόδων επίλυσης του προβλήματος ΕΓΔ δύο κριτηρίων. Το δεύτερο, αφορά την υλοποίηση και πειραματική αξιολόγηση δύο βασικών αλγορίθμων για την επίλυση του εν λόγω προβλήματος. Συγκεκριμένα, υλοποιήθηκε η τροποποιημένη εκδοχή (για το πρόβλημα ΕΓΔ πολλαπλών κριτηρίων) του αλγορίθμου του Prim καθώς και μία προσεγγιστική μέθοδος επίλυσης του προβλήματος ΕΓΔ πολλαπλών κριτηρίων. / The minimum spanning tree problem (MST) is of high importance in network optimization. Given a connected graph G where each edge has a weight, the goal is to find the spanning tree with the least cost among all spanning trees of G. Due to its many practical applications, the MST problem has been studied in depth and many efficient polynomial-time algorithms have been developed by Sollin, Kruskal, Prim etc. But in real life, there cases where one has to take simultaneously into consideration many criteria in order to determine a MST because there are multiple weights defined on each edge of the graph. For example, when designing the layout of a telecommunication network, besides the cost for connections between cities or terminals we are interested in other factors too. The time for communication and construction, the difficulty of the construction or the reliability of the system are also important factors and need to be taken into consideration. But also in everyday life, in many cases we need to take decisions that depend on multiple criteria. For instance, people who travel want to minimize simultaneously the cost, the distance and the time. The problem is that in these cases there is not only one optimal solution but rather a set of optimal solutions and the decision maker depending on the characteristics of each case will make the final call. The MST problem in which we want to minimize more than one criteria is known as the multi-criteria minimum spanning tree problem. The contribution of this thesis is composed of two parts. The first part focuses on the critical survey and description of various methods for solving the bi-criteria case of the MST problem. The other part focuses on the implementation and the experimental evaluation of two known and important algorithms. More precisely, we have implemented the modified version of the Prim’s algorithm (for the multi-criteria MST problem) and one approximate algorithm as proposed by Hamacher & Ruhe.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/133 |
| Date | 16 May 2007 |
| Creators | Σταθοπούλου, Ευθυμία |
| Contributors | Ζαρολιάγκης, Χρήστος, Stathopoulou, Efthimia, Ζαρολιάγκης, Χρήστος, Γαλλόπουλος, Ευστράτιος, Κακλαμάνης, Χρήστος |
| Source Sets | University of Patras |
| Detected Language | Greek |
| Relation | Η ΒΥΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0031 seconds