Αλγόριθμοι εύρεσης διαδρομής
Path finding algorithms
Keywords
Αλγόριθμοι ; Αλγόριθμος Α* ; Bug algorithms ; Particle Filter ; Αλγόριθμος DijkstraAbstract
Η πτυχιακή αυτή εργασία πραγματεύεται αλγορίθμους εύρεσης διαδρομής. Σκοπός της εργασίας αυτής είναι η μελέτη των αλγορίθμων αυτών. Η εφαρμογή των αλγορίθμων γίνεται σε διάφορες εφαρμογές όπως δίκτυα ή ρομποτικά συστήματα. Οι αλγόριθμοι αναζήτησης αφορούν το σχεδιασμό κατάλληλων ενεργειών με στόχο την άφιξη ενός ελέγξιμου συστήματος σε μία αποδεκτή τελική κατάσταση, εκκινώντας από κάποια προκαθορισμένη αρχική κατάσταση. Υπάρχει ποικιλία αλγορίθμων που χρησιμοποιούνται σήμερα για τέτοιες εφαρμογές αλλά στην συγκεκριμένη εργασία θα αναλυθούν μόνο τέσσερις. Οι αλγόριθμοι που επιλέχθηκαν να αναλυθούν είναι ο Α* (Α-άστρο), Dijkstra, Particle Filters και οι Bug Algorithms, στους οποίους ανήκει ένα εύρος αλγορίθμων. Καθένας από αυτούς τους αλγορίθμους έχει πλεονεκτήματα και μειονεκτήματα και όλα αυτά παρουσιάζονται στην εργασία αυτή. Στην αρχή της παρούσας εργασίας παρουσιάζεται η έννοια και η χρήση του αλγορίθμου. Αναλύεται επίσης ο ορισμός των γράφων καθώς είναι απαραίτητοι για την εκτέλεση του Dijkstra αλγορίθμου. Στο υπόλοιπο τμήμα της εργασίας παρουσιάζονται οι επιλεγμένοι αλγόριθμοι και αφιερώνεται ένα κεφάλαιο για τον καθένα. Σε κάθε κεφάλαιο από αυτά υπάρχει υλοποίηση και επεξήγηση των αλγορίθμων μέσω απλών παραδειγμάτων μέσα από εικόνες και πίνακες. Σε κάποια σημεία των κεφαλαίων που περιγράφουν τους αλγορίθμους υπάρχει σύγκριση μεταξύ ορισμένων και εξηγείται για πιο λόγο προτιμάται ο καθένας.
Abstract
In the present thesis we discuss about path finding algorithms. The main focus here is to study those algorithms. Their implementation can be applied in a variety of applications such as networks or robotic systems. They are used to plan actions that will result in having a controllable system in the desired form whilst started in a predefined form. There is a huge variety of those algorithms, however we will be analyzing four of them. These four are A* (A star), Dijkstra, Particle Filters and Bug Algorithms. Bug Algorithms contain different types of algorithms. Every single one of those four has advantages and disadvantages that we are going to talk about. In the beginning of this thesis we are going to talk about the definition and the use of them. Furthermore, we will be defining the graphs as they are an important part of Dijkstra. Throughout the rest of the thesis a unique chapter will be used to analyze each one of those four. The implementation and definition are going to be explained by using examples with images and drawings. In some cases there are going to be comparisons between them.
Number of pages
98Faculty
Σχολή Τεχνολογικών ΕφαρμογώνAcademic Department
Τμήμα Μηχανικών Αυτοματισμού Τ.Ε.Language
GreekCollections
The following license files are associated with this item: