Παρακαλώ χρησιμοποιήστε αυτό το αναγνωριστικό για να παραπέμψετε ή να δημιουργήσετε σύνδεσμο προς αυτό το τεκμήριο:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14548
Τίτλος: | Προσεγγιστικοί Αλγόριθμοι Και Προσεγγιστικά Σχήματα Για Ειδικές Περιπτώσεις Του Προβλήματος Του Πλανόδιου Πωλητή (traveling Salesman Problem) |
Συγγραφείς: | Ιωάννης Γιαννακάκης Αφράτη Φώτω |
Λέξεις κλειδιά: | πρόβλημα του πλανόδιου πωλητή tsp πολυπλοκότητα προσεγγιστικοί αλγόριθμοι προσεγγιστικά σχήματα ptas fptas metric tsp ευκλείδιο tsp (1 2)-tsp |
Ημερομηνία έκδοσης: | 5-Ιου-2006 |
Περίληψη: | Ο σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη προσεγγιστικών αλγορίθμων και προσεγγιστικών σχημάτων που επιλύουν σε πολυωνυμικό χρόνο κάποιες ειδικές περιπτώσεις του NP-coplete Προβλήματος του πλανόδιου πωλητή (Traveling Salesman Problem, TSP). Η εργασία ξεκινά με μια εισαγωγή στη θεωρία της πολυπλοκότητας, τη θεωρία γράφων και τους προσεγγιστικούς αλγορίθμους. Ορίζεται στη συνέχεια το πρόβλημα στη γενική του μορφή (general TSP), και ακολουθεί ο ορισμός του Metric TSP (MTSP), με παρουσίαση και ανάλυση προσεγγιστικών αλγορίθμων που το επιλύουν σε πολυωνυμικό χρόνο. Ακολουθεί η περίπτωση του Ευκλείδιου TSP (Euclidean TSP), για το οποίο δίνεται ένα πολυωνυμικό προσεγγιστικό σχήμα (PTAS). Η τελευταία περίπτωση που μελετάται είναι το (1,2)-TSP, για το οποίο δίνονται οι πιο σημαντικοί προσεγγιστικοί αλγόριθμοι, μεταξύ των οποίων και ένας πολύ πρόσφατος (2005). Η εργασία ολοκληρώνεται με την παράθεση κάποιων σημαντικών πρακτικών εφαρμογών του TSP. |
URI: | http://artemis-new.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14548 |
Εμφανίζεται στις συλλογές: | Διπλωματικές Εργασίες - Theses |
Αρχεία σε αυτό το τεκμήριο:
Αρχείο | Μέγεθος | Μορφότυπος | |
---|---|---|---|
DT2006-0065.pdf | 4.84 MB | Adobe PDF | Εμφάνιση/Άνοιγμα |
Όλα τα τεκμήρια του δικτυακού τόπου προστατεύονται από πνευματικά δικαιώματα.