Στην διπλωματική εργασία παρουσιάζεται μια νέα δομή δεδομένων ειδικά σχεδιασμένη για δίκτυα μεταφορών ευρείας κλίμακας τα οποία αλλάζουν δυναμικά. Η νέα δομή δεδομένων γραφημάτων μας παρέχει ταυτόχρονα τρία μοναδικά χαρακτηρισ τικά:
1. Σύμπτυξη(Compactness): ικανότητα να προσπελάσει αποδοτικά διαδοχικές κορυφές και ακμές, μια απαίτηση όλων των αλγορίθμων γραφημάτων).
2. Ευκινησία (Agility): ικανότητα να αλλάξει και να ρυθμίσει εξαρχής την εσωτερική της διάταξη με σκοπό να βελτιώσει την τοπικότητα των αναφορών των στοιχείων, σύμφωνα με έναν δεδομένο αλγόριθμο.
3. Δυναμικότητα (Dynamicity): ικανότητα να ενθέσει ή να διαγράψει αποδοτικά κορυφές και ακμές.
Όλες οι προηγούμενες γνωστές δομές γραφημάτων δεν υποστήριζαν τουλάχιστον ένα από τα προηγούμενα χαρακτηριστικά ή/και δεν μπορούσαν να εφαρμοστούν σε δυναμικά δίκτυα μεταφορών ευρείας κλίμακας.
Σε αυτή τη διπλωματική εργασία, παρουσιάζεται η πρακτικότητα της νέας δομής γραφημάτων εκτελώντας μια εκτενή πειραματική μελέτη για δρομολόγηση συντομότερων διαδρομών σε Ευρωπαϊκά οδικά δίκτυα ευρείας κλίμακας με μερικές δεκάδες εκατομμύρια κορυφές και ακμές. Χρησιμοποιώντας κλασικούς αλγόριθμους εύρεσης συντομότερων διαδρομών, επιτυγχάνονται εύκολα χρόνοι ερωτημάτων από μια αρχική κορυφή σε μια τελική κορυφή της τάξης των milliseconds, ενώ η νέα δομή γραφημάτων μας μπορεί να ενημερωθεί σε μόλις μερικά microseconds μετά από μια ένθεση ή διαγραφή μιας κορυφής ή ακμής. / We present a new graph data structure specifically suited for large scale transportation networks in dynamic scenario. Our graph data structure provides tree unique characteristics, namely compactness, agility and dynamicity. All previous data structures were lacking support in at least one of the aforementioned characteristics. We demonstrate the practicality of the new graph data structure by conducting experiments on large scale European road networks, achieving query times of classical routing algorithms in the order of milliseconds and update times in the order of a few microseconds.
| Identifer | oai:union.ndltd.org:upatras.gr/oai:nemertes:10889/5825 |
| Date | 01 February 2013 |
| Creators | Μιχαήλ, Παναγιώτης |
| Contributors | Ζαρολιάγκης, Χρήστος, MIchail, Panagiotis, Ζαρολιάγκης, Χρήστος, Νικολετσέας, Σωτήρης, Τσίχλας, Κωνσταντίνος |
| Source Sets | University of Patras |
| Language | gr |
| Detected Language | Greek |
| Type | Thesis |
| Rights | 0 |
| Relation | Η ΒΚΠ διαθέτει αντίτυπο της διατριβής σε έντυπη μορφή στο βιβλιοστάσιο διδακτορικών διατριβών που βρίσκεται στο ισόγειο του κτιρίου της. |
Page generated in 0.0019 seconds