Αλγόριθμοι εύρεσης βέλτιστων διαδρομών σε μη διασυνδεδεμένες κινητές συσκευές

Thumbnail Image
Date
2022-09-29
Authors
Λύρου, Δήμητρα
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Το πρόβλημα αναζήτησης συντομότερων διαδρομών περιλαμβάνει την εύρεση βέλτιστης διαδρομής μεταξύ της παρούσας θέσης και του προορισμού υπό δεδομένες συνθήκες. Επί του παρόντος, τέτοιου είδους προβλήματα εμφανίζονται σε δίκτυα όπως το τηλεπικοινωνιακό, το οδικό, το σιδηροδρομικό και άλλα καλύπτοντας ένα ευρύ φάσμα εφαρμογών. Ειδικά στα συστήματα πλοήγησης έχει σημειωθεί εκρηκτική πρόοδος χάρη στους αλγόριθμους εύρεσης συντομότερων διαδρομών. Στη παρούσα διπλωματική εργασία διερευνήθηκαν οι αλγόριθμοι Dijkstra και ΑLT ως προς την αποτελεσματικότητα τους σε οδικά δίκτυα σε συνδυασμό με τα γεωγραφικά πλάτη και μήκη. Σκοπός ήταν η μείωση του χρόνου εκτέλεσης των αλγορίθμων όσο το δυνατόν περισσότερο, δεδομένου ότι εφαρμόζονται σε μη διασυνδεδεμένη κινητή συσκευή. Η έρευνα βασίστηκε σε προηγμένο λειτουργικό σύστημα Android και για την δρομολόγηση επιλέχθηκε η βιβλιοθήκη OSMDroid. Σημειώνεται ότι παρακάτω θα λαμβάνονται υπόψιν ως έγκυρα αποτελέσματα, διαδρομές οι οποίες είναι όσον πιο κοντά γίνεται στην βέλτιστη. Η αποτελεσματικότητα των μεθόδων των παραπάνω αλγορίθμων αναλύθηκε με τη χρήση προσομοιώσεων οι οποίες υλοποιήθηκαν σε πηγαίο κώδικα JAVA.
Description
Keywords
Συντομότερες διαδρομές, "Dijkstra", Μη διασυνδεδεμένες κινητές συσκευές
Citation