Please use this identifier to cite or link to this item:
http://artemis.cslab.ece.ntua.gr:8080/jspui/handle/123456789/14548
Title: | Προσεγγιστικοί Αλγόριθμοι Και Προσεγγιστικά Σχήματα Για Ειδικές Περιπτώσεις Του Προβλήματος Του Πλανόδιου Πωλητή (traveling Salesman Problem) |
Authors: | Ιωάννης Γιαννακάκης Αφράτη Φώτω |
Keywords: | πρόβλημα του πλανόδιου πωλητή tsp πολυπλοκότητα προσεγγιστικοί αλγόριθμοι προσεγγιστικά σχήματα ptas fptas metric tsp ευκλείδιο tsp (1 2)-tsp |
Issue Date: | 5-Jul-2006 |
Abstract: | Ο σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη προσεγγιστικών αλγορίθμων και προσεγγιστικών σχημάτων που επιλύουν σε πολυωνυμικό χρόνο κάποιες ειδικές περιπτώσεις του 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 |
Appears in Collections: | Διπλωματικές Εργασίες - Theses |
Files in This Item:
File | Size | Format | |
---|---|---|---|
DT2006-0065.pdf | 4.84 MB | Adobe PDF | View/Open |
Items in Artemis are protected by copyright, with all rights reserved, unless otherwise indicated.