Παραλλαγές του ευρετικού αλγορίθμου Α* για κατασκευή συντομότερων διαδρομών υπό περιορισμούς πόρων
Loading...
Date
2025-10-27
Authors
Καμπέρος, Βύρων
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Η παρούσα διπλωματική εργασία επικεντρώνεται στη μελέτη και υλοποίηση δύο ευρετικών αλγορίθμων που είναι παραλλαγές της πολύ γνωστής ευρετικής A* για εύρεση βέλτιστων διαδρομών υπό πολλαπλά κριτήρια και περιορισμούς πόρων: του WC-A* και του WC-EBBA*par. Στόχος είναι η αναλυτική παρουσίαση, υλοποίηση και πειραματική αξιολόγηση της απόδοσής τους, και ιδιαίτερα η αξιολόγηση της αποτελεσματικότητας του παράλληλου WC-EBBA*par σε σύγκριση με τον κλασικό WC-A*.
Στο πλαίσιο της εργασίας, πραγματοποιήθηκε εις βάθος μελέτη της σχετικής βιβλιογραφίας και των θεωρητικών εννοιών που εμπλέκονται, όπως η κατά Pareto βετλιτστότητα (Pareto optimality) και το πρόβλημα εύρεσης συντομότερων διαδρομών υπό περιορισμούς πόρων (Resource Constrained Shortest Path Problem -- RCSPP). Οι αλγόριθμοι υλοποιήθηκαν ακολουθώντας πιστά τις περιγραφές που παρέχονται σε υπάρχουσες επιστημονικές δημοσιεύσεις, και δοκιμάστηκαν σε πραγματικά σύνολα δεδομένων μεγάλης κλίμακας.
Τα αποτελέσματα των πειραμάτων επιβεβαίωσαν τα ευρήματα της σχετικής βιβλιογραφίας: ο παράλληλος WC-EBBA*par επιτυγχάνει βελτίωση του χρόνου εκτέλεσης σε σχέση με τον WC-A*, διατηρώντας την ακρίβεια και την ορθότητα των λύσεων. Η εργασία καταλήγει σε συμπεράσματα που αφορούν την πρακτική αξιοποίηση των αλγορίθμων σε εφαρμογές δρομολόγησης και αναδεικνύει πεδία για μελλοντική έρευνα και βελτιστοποίηση.
Description
Keywords
Θεωρητικό υπόβαθρο, Περιορισμοί πόρων, Πολυκριτηριακή βελτιστοποίηση, Ευρετικοί αλγόριθμοι