Παράλληλοι αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε χρονο-εξαρτώμενα δίκτυα
Η παρούσα διπλωματική εργασία αφορά την υλοποίηση και την πειραματική αξιολόγηση παράλληλων αλγορίθμων για τον υπολογισμό βέλτιστων διαδρομών σε δυναμικά δίκτυα δηλαδή σε δίκτυα που έχουν χρονικά μεταβαλλόμενα χαρακτηριστικά, όπως ο χρόνος διέλευσης ακμής και το κόστος, των οποίων οι τιμές είναι γνω...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2016
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/9583 |
| Περίληψη: | Η παρούσα διπλωματική εργασία αφορά την υλοποίηση και την πειραματική αξιολόγηση παράλληλων αλγορίθμων για τον υπολογισμό βέλτιστων διαδρομών σε δυναμικά δίκτυα δηλαδή σε δίκτυα που έχουν χρονικά μεταβαλλόμενα χαρακτηριστικά, όπως ο χρόνος διέλευσης ακμής και το κόστος, των οποίων οι τιμές είναι γνωστές για κάθε χρονική στιγμή.
Σε πρώτο στάδιο μελετήθηκαν διάφοροι αλγόριθμοι εύρεσης βέλτιστων διαδρομών. Επίσης προτείναμε αρχικά ένα σειριακό αλγόριθμο που βασίζεται στο Δ-stepping αλγόριθμο και ο οποίος μπορεί να βρίσκει βέλτιστες διαδρομές σε μικρότερο χρόνο από τον αντίστοιχο χρόνο που χρειάζεται ο χρονο-εξαρτώμενος αλγόριθμος του Dijksta . Στην συνέχεια χρησιμοποιώντας διάφορες τεχνικές έγινε η παραλλοποίηση του παραπάνω αλγορίθμου πετυχαίνοντας ακόμα καλύτερους χρόνους.
Τέλος η εργασία αυτή περιλαμβάνει μια λεπτομερή πειραματική μελέτη πάνω σε οδικά δίκτυα που περιλαμβάνουν μερικές εκατοντάδες χιλιάδες ακμές και κόμβους όπως τα οδικά δίκτυα της Γερμανίας και της Φλώριντας. |
|---|
