Μια Android εφαρμογή για το «Ερώτημα Σχεδιασμού Ταξιδιού»
| dc.contributor.advisor | Πελέκης, Νικόλαος | |
| dc.contributor.author | Καββαλάκης, Κωνσταντίνος Σ. | |
| dc.date.accessioned | 2014-02-20T10:24:11Z | |
| dc.date.available | 2014-02-20T10:24:11Z | |
| dc.date.issued | 2014-02-20T10:24:11Z | |
| dc.identifier.uri | https://dione.lib.unipi.gr/xmlui/handle/unipi/5690 | |
| dc.description.abstract | Ο σκοπός της παρούσας μεταπτυχιακής διατριβής είναι η υλοποίηση μιας android εφαρμογής που θα ενσωματώνει τον αλγόριθμο «Επαναληπτικού Διπλασιασμού», κατάλληλο όπως προτείνεται να τρέχει αποδοτικά σε μια κινητή συσκευή με δεδομένους επεξεργαστικούς περιορισμούς. Η εφαρμογή που υλοποιήθηκε υπολογίζει την βέλτιστη διαδρομή, η οποία όπως απαιτεί ο χρήστης πρέπει να ξεκινάει από ένα σημείο αρχής, να περνάει ακολουθιακά από διαφορετικά σημεία ενδιαφέροντος και καταλήγει σε έναν επιθυμητό προορισμό. Αυτή η κατηγορία προβλημάτων είναι γνωστή σαν Trip Planning Queries (TPQ). Τα ερωτήματα που αφορούν το σχεδιασμό διαδρομών(TPQ) είναι μη ντετερμινιστικά πολυωνυμικού χρόνου προβλήματα(NP problems).Γενικά πολλοί προτεινόμενοι αλγόριθμοι παρουσιάζουν λύσεις είτε προσεγγιστικές είτε μεγάλης πολυπλοκότητας με αποτέλεσμα να μην είναι χρηστικοί στην υλοποίηση. Παρόλα αυτά η παρούσα εφαρμογή χαλαρώνει την πολυπλοκότητα του προβλήματος, καθορίζοντας την σειρά προσπέλασης των σημείων ενώ ψάχνει να βρει την διαδρομή με το ελάχιστο μήκος με το να επισκέπτεται ακολουθιακά τα σημεία από την μια κατηγορία στην επόμενη. Αυτά του τύπου τα ερωτήματα ονομάζονται «ερωτήματα διαδοχικής διαδρομής» (SRQ) και η απάντηση τους θα μπορούσε να είναι εφικτή και σε κινητές συσκευές όπως προτείνετε και υλοποιείται από την παρούσα εργασία. Ο αλγόριθμος «Επαναληπτικού Διπλασιασμού» (Iterative Doubling) είναι μια παραλλαγή του EDJ (Enhanced Dijkstra- ενότητα 2.2.3), και βασίζεται στο να αποφεύγει να εξερευνάει απομακρυσμένα σημεία. Με τον τρόπο αυτό μειώνει τον επεξεργαστικό όγκο και αποδίδει καλύτερα για τοπικά δεδομένα που αποτελούν και τις πιο συνηθισμένες περιπτώσεις σε τέτοιου είδους προβλήματα. Στην πράξη τέτοια προβλήματα εύρεσης βέλτιστης διαδρομής με ενδιάμεσους προορισμούς συνήθως συναντώνται σε τοπική ακτίνα. Τα δεδομένα αυτά συλλέχτηκαν από το OpenStreetMaps και αφορούν το λεκανοπέδιο Αττικής. Αναπαριστούν γεωγραφικά δεδομένα που ανήκουν σε συγκεκριμένες κατηγορίες ενδιαφέροντος. Αυτή η κατηγοριοποίηση μπορεί να θεωρηθεί σαν ένα σύνολο τέτοιων σημείων με παρόμοια χαρακτηριστικά όπως τράπεζες, εστιατόρια κτλ. Η βασική μονάδα δεδομένου κρατάει την πληροφορία των συντεταγμένων κάθε σημείου, τον τίτλο της εγκατάστασης και την κατηγορία που ανήκει. Η εφαρμογή φιλοξενεί αυτά τα δεδομένα σε στατικά με τη μορφή xml αρχείων. Ανάλογα με τις επιλογές του χρήστη τα κατάλληλα αρχεία διατρέχονται ώστε να δομήσουν δυναμικά τον ζητούμενο γράφο. Δεν είναι απαραίτητα η άμεση δημιουργία του.Tέλος η εφαρμογή καταφέρνει και αναπτύσσει την βέλτιστη διαδρομή που περνάει από ένα τουλάχιστον σημείο ανά κατηγορία ενδιαφέροντος. | |
| dc.language.iso | el | |
| dc.rights | Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 4.0 Διεθνές | |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/deed.el | |
| dc.subject | Application software -- Development | |
| dc.subject | Android (Electronic resource) | |
| dc.subject | Smartphones -- Programming | |
| dc.subject | Mobile computing | |
| dc.title | Μια Android εφαρμογή για το «Ερώτημα Σχεδιασμού Ταξιδιού» | |
| dc.title.alternative | An android application for the “Trip Planning Query” | en |
| dc.type | Master Thesis | |
| europeana.isShownAt | https://dione.lib.unipi.gr/xmlui/handle/unipi/5690 | |
| dc.identifier.call | 004.1 675 ΚΑΒ | |
| dc.description.abstractEN | The objective of the current master thesis is the implementation of an efficient android application that utilizes the Iterative Doubling algorithm. It runs in a mobile device with known computational processing limitations. Finally as the user of the application imposes, the optimal path should start from a specified source, pass through several points of interest (POIs) and reach specified destination. These problems are generally known as “Trip Planning Queries” (TPQ). Trip Planning Queries (TPQ) belong to NP-hard problems. In general there are many proposed algorithms which result in an approximate or inefficient in terms of complexity solution. The previously mentioned drawbacks prevent the use of those algorithms in many implementations. However the solution presented in this thesis reduces complexity by imposing the order of visiting locations. The algorithm which is used manages to find a route of minimum length by visiting points from each category sequentially before it steps to the next category. This type of queries are named “Sequenced Route Queries” (SRQ) and their implementation could be feasible even in a mobile device as it is proposed and utilized by an android application in the current thesis. The algorithm used is the Iterative Doubling, an alternative to the EDJ (Enhanced Dijkstra - section 2.3.3) layered approach. The current approach helps to avoid exploring facilities that are far away from the starting point. The algorithm manages to reduce the computational cost of exploring every possible facility and therefore it performs better in case that we have to process local data. Realistic sequenced route queries mainly refer to such local geographical data. The application manages to exclude such distant facilities by setting an initial threshold that defines a range in kilometers. Also the user has as an option to choose between some initial ranges, depending on the minimum trip distance that he is willing to cover. With this threshold nodes of POIs without range does not take part during Dijkstra computations and so this fastens the running time. If the initial range although could not resume to an optimal path then the threshold is doubled and the algorithm is executed again. The data for the needs of the application were collected from OpenStreetMaps project and mainly concern mainly Attica. They represent several geographical points and each of them belongs to a respective category of interest such as hotels, restaurants etc. The basic data element keeps information about its geographic coordinates, the label that identifies the facility and its category. They are initially formed as xml separated files (per category) and they are utilized as node objects. Another advantage of the implemented algorithm is that it does not require the explicit construction of the graph that is built during each Dijkstra’s computation. The final outcome is a route with the minimum distance that passes through a point from each category. |
Αρχεία σε αυτό το τεκμήριο
Αυτό το τεκμήριο εμφανίζεται στις ακόλουθες συλλογές
-
Τμήμα Πληροφορικής
Department of Informatics
Εκτός από όπου διευκρινίζεται διαφορετικά, το τεκμήριο διανέμεται με την ακόλουθη άδεια:
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 4.0 Διεθνές
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 4.0 Διεθνές