Αλγόριθμοι εύρεσης διαδρομής
| Κύριος συγγραφέας: | |
|---|---|
| Μορφή: | Πτυχιακή εργασία |
| Γλώσσα: | Greek |
| Έκδοση: |
Α.Ε.Ι. Πειραιά Τ.Τ.
2017
|
| Θέματα: | |
| Διαθέσιμο Online: | http://okeanis.lib2.uniwa.gr/xmlui/handle/123456789/3488 |
| _version_ | 1780524867372711936 |
|---|---|
| abstract | Η πτυχιακή αυτή εργασία πραγματεύεται αλγορίθμους εύρεσης διαδρομής. Σκοπός της εργασίας αυτής είναι η μελέτη των αλγορίθμων αυτών. Η εφαρμογή των αλγορίθμων γίνεται σε διάφορες εφαρμογές όπως δίκτυα ή ρομποτικά συστήματα. Οι αλγόριθμοι αναζήτησης αφορούν το σχεδιασμό κατάλληλων ενεργειών με στόχο την άφιξη ενός ελέγξιμου συστήματος σε μία αποδεκτή τελική κατάσταση, εκκινώντας από κάποια προκαθορισμένη αρχική κατάσταση. Υπάρχει ποικιλία αλγορίθμων που χρησιμοποιούνται σήμερα για τέτοιες εφαρμογές αλλά στην συγκεκριμένη εργασία θα αναλυθούν μόνο τέσσερις. Οι αλγόριθμοι που επιλέχθηκαν να αναλυθούν είναι ο Α* (Α-άστρο), Dijkstra, Particle Filters και οι Bug Algorithms, στους οποίους ανήκει ένα εύρος αλγορίθμων. Καθένας από αυτούς τους αλγορίθμους έχει πλεονεκτήματα και μειονεκτήματα και όλα αυτά παρουσιάζονται στην εργασία αυτή. Στην αρχή της παρούσας εργασίας παρουσιάζεται η έννοια και η χρήση του αλγορίθμου. Αναλύεται επίσης ο ορισμός των γράφων καθώς είναι απαραίτητοι για την εκτέλεση του Dijkstra αλγορίθμου. Στο υπόλοιπο τμήμα της εργασίας παρουσιάζονται οι επιλεγμένοι αλγόριθμοι και αφιερώνεται ένα κεφάλαιο για τον καθένα. Σε κάθε κεφάλαιο από αυτά υπάρχει υλοποίηση και επεξήγηση των αλγορίθμων μέσω απλών παραδειγμάτων μέσα από εικόνες και πίνακες. Σε κάποια σημεία των κεφαλαίων που περιγράφουν τους αλγορίθμους υπάρχει σύγκριση μεταξύ ορισμένων και εξηγείται για πιο λόγο προτιμάται ο καθένας. |
| abstracttranslated | 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. |
| advisor | |
| author | Γκαβογιάννης, Λάμπρος |
| author_facet | Γκαβογιάννης, Λάμπρος |
| author_sort | Γκαβογιάννης, Λάμπρος |
| collection | Okeanis Institutional Repository |
| facultydepartment | Τμήμα Μηχανικών Αυτοματισμού Τ.Ε. |
| format | Πτυχιακή εργασία |
| id | okeanis-123456789-3488 |
| institution | University of West Attica Campus II |
| keyword | Αλγόριθμοι Αλγόριθμος Α* Bug algorithms Particle Filter Αλγόριθμος Dijkstra |
| language | Greek |
| physical | 98 |
| publishDate | 2017 |
| publisher | Α.Ε.Ι. Πειραιά Τ.Τ. |
| record_format | dspace |
| spelling | okeanis-123456789-34882018-12-14T11:43:28Z Αλγόριθμοι εύρεσης διαδρομής Path finding algorithms Γκαβογιάννης, Λάμπρος Νικολάου, Γρηγόριος Τμήμα Μηχανικών Αυτοματισμού Τ.Ε. TPSH::Επιστήμη Υπολογιστών TPSH::Φυσικές Επιστήμες::Μαθηματικά::Αλγόριθμοι Αλγόριθμοι Αλγόριθμος Α* Bug algorithms Particle Filter Αλγόριθμος Dijkstra Η πτυχιακή αυτή εργασία πραγματεύεται αλγορίθμους εύρεσης διαδρομής. Σκοπός της εργασίας αυτής είναι η μελέτη των αλγορίθμων αυτών. Η εφαρμογή των αλγορίθμων γίνεται σε διάφορες εφαρμογές όπως δίκτυα ή ρομποτικά συστήματα. Οι αλγόριθμοι αναζήτησης αφορούν το σχεδιασμό κατάλληλων ενεργειών με στόχο την άφιξη ενός ελέγξιμου συστήματος σε μία αποδεκτή τελική κατάσταση, εκκινώντας από κάποια προκαθορισμένη αρχική κατάσταση. Υπάρχει ποικιλία αλγορίθμων που χρησιμοποιούνται σήμερα για τέτοιες εφαρμογές αλλά στην συγκεκριμένη εργασία θα αναλυθούν μόνο τέσσερις. Οι αλγόριθμοι που επιλέχθηκαν να αναλυθούν είναι ο Α* (Α-άστρο), Dijkstra, Particle Filters και οι Bug Algorithms, στους οποίους ανήκει ένα εύρος αλγορίθμων. Καθένας από αυτούς τους αλγορίθμους έχει πλεονεκτήματα και μειονεκτήματα και όλα αυτά παρουσιάζονται στην εργασία αυτή. Στην αρχή της παρούσας εργασίας παρουσιάζεται η έννοια και η χρήση του αλγορίθμου. Αναλύεται επίσης ο ορισμός των γράφων καθώς είναι απαραίτητοι για την εκτέλεση του Dijkstra αλγορίθμου. Στο υπόλοιπο τμήμα της εργασίας παρουσιάζονται οι επιλεγμένοι αλγόριθμοι και αφιερώνεται ένα κεφάλαιο για τον καθένα. Σε κάθε κεφάλαιο από αυτά υπάρχει υλοποίηση και επεξήγηση των αλγορίθμων μέσω απλών παραδειγμάτων μέσα από εικόνες και πίνακες. Σε κάποια σημεία των κεφαλαίων που περιγράφουν τους αλγορίθμους υπάρχει σύγκριση μεταξύ ορισμένων και εξηγείται για πιο λόγο προτιμάται ο καθένας. 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. 2017-05-16 Πτυχιακή εργασία http://okeanis.lib2.uniwa.gr/xmlui/handle/123456789/3488 el http://creativecommons.org/licenses/by-nc-nd/3.0/gr/ Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα Α.Ε.Ι. Πειραιά Τ.Τ. 98 http://okeanis.lib2.uniwa.gr/xmlui/bitstream/123456789/3488/7/auto_39777.pdf.jpg |
| spellingShingle | TPSH::Επιστήμη Υπολογιστών TPSH::Φυσικές Επιστήμες::Μαθηματικά::Αλγόριθμοι Γκαβογιάννης, Λάμπρος Αλγόριθμοι εύρεσης διαδρομής |
| title | Αλγόριθμοι εύρεσης διαδρομής |
| title_full | Αλγόριθμοι εύρεσης διαδρομής |
| title_fullStr | Αλγόριθμοι εύρεσης διαδρομής |
| title_full_unstemmed | Αλγόριθμοι εύρεσης διαδρομής |
| title_short | Αλγόριθμοι εύρεσης διαδρομής |
| title_sort | αλγόριθμοι εύρεσης διαδρομής |
| title_translated | Path finding algorithms |
| topic | TPSH::Επιστήμη Υπολογιστών TPSH::Φυσικές Επιστήμες::Μαθηματικά::Αλγόριθμοι |
| url | http://okeanis.lib2.uniwa.gr/xmlui/handle/123456789/3488 |