Μια υλοποίηση του αλγόριθμου του Arora για το πρόβλημα k-TSP

Αλβέρτης, Μηνάς

dc.contributor.advisor	Κωνσταντόπουλος, Χαράλαμπος
dc.contributor.author	Αλβέρτης, Μηνάς
dc.date.accessioned	2026-10-15T07:24:16Z
dc.date.available	2026-10-15T07:24:16Z
dc.date.issued	2026-10
dc.identifier.uri	https://dione.lib.unipi.gr/xmlui/handle/unipi/19864
dc.description	Ο σχετικός κώδικας έχει αναρτηθεί στο https://github.com/lonerae/tsp-approximations	el
dc.description.abstract	Το Πρόβλημα του Πλανώδιου Πωλητή αποτελεί ένα από τα πρώτα γνωστά προβλήματα στην θεωρία των γραφημάτων, του οποίου η δημοφιλία εξηγείται από τις πρακτικές εφαρμογές στις οποίες μία αποδοτική υλοποίηση θα έδινε λύση. Ανά τα χρόνια έχει χρησιμοποιηθεί ως πρόβλημα σταθμός για την αξιολόγηση νέων αλγορίθμων και οι τεχνικές που έχουν εφαρμοστεί προσέφεραν στην Επιστήμη των Υπολογιστών με τις καινοτομίες τους στα θέματα των ευριστικών και προσεγγιστικών τεχνικών. Στην παρούσα έρευνα παρουσιάζεται, επεξηγείται και υλοποιείται ο προσεγγιστικός αλγόριθμος του Sanjeev Arora, ο οποίος μετέπειτα επεκτείνεται ώστε να μπορεί να αντιμετωπίσει και μία παραλλαγή του Προβλήματος του Πλανώδιου Πωλητή, στην οποία ο ζητούμενος αριθμός των κόμβων μίας λύσης διαφοροποιείται από τον ορισμό του αρχικού προβλήματος. Παραθέτονται με επεξηγήσεις κομμάτια ψευδοκώδικα καθώς και αποτελέσματα της εκτέλεσης των αλγορίθμων σε κάθε περίπτωση. Η παρούσα εργασία έχει ως στόχο να αποδείξει ότι αλγόριθμοι με αυστηρή μαθηματική θεμελίωση και μαθηματικά αποδεδειγμένη ακρίβεια είναι δυνατόν να έχουν την πρακτική αξία η οποία έχει πιο συχνά συνδεθεί με τους ευριστικούς αλγορίθμους στη σύγχρονη βιβλιογραφία. Σκοπεύει επίσης να δώσει κατευθυντήριες γραμμές για το πώς θα μπορούσαν να προσαρμοστούν τα τμήματα στα οποία η μεταφορά από τη θεωρία στην πράξη θα οδηγούσαν σε εξαντλητικούς υπολογισμούς.	el
dc.format.extent	80	el
dc.language.iso	el	el
dc.publisher	Πανεπιστήμιο Πειραιώς	el
dc.rights	Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα	*
dc.rights.uri	http://creativecommons.org/licenses/by-nc-nd/3.0/gr/	*
dc.title	Μια υλοποίηση του αλγόριθμου του Arora για το πρόβλημα k-TSP	el
dc.title.alternative	An implementation of Arora’s algorithm for the k-TSP problem	el
dc.type	Master Thesis	el
dc.contributor.department	Σχολή Τεχνολογιών Πληροφορικής και Επικοινωνιών. Τμήμα Πληροφορικής	el
dc.description.abstractEN	The Travelling Salesperson Problem is one of the first well-known problems of graph theory, which owes its popularity to the number of practical applications that its implementation can solve. Over the years it has been used as a benchmark for the evaluation of newer algorithms and its proposed solution methods have offered a great number of innovations concerning matters related to heuristics and approximation techniques in Computer Science. In this thesis, the approximation algorithm of Sanjeev Arora is presented, explained and implemented, and later expanded so that it can offer solution to a variation of the problem, where the needed number of nodes of a solution is differentiated. Code segments are presented in pseudocode, as well as the results of the algorithms’ executions in each case. The present work aims to prove that algorithms with strict mathematical foundation and mathematically proven accuracy also have the practicality that has lately been associated mainly with heuristic algorithms. It also aims to suggest adjustments to parts of the algorithms that appear to involve too many calculations when the theory is adapted for implementation.	el
dc.contributor.master	Πληροφορική	el
dc.subject.keyword	Πρόβλημα πλανώδιου πωλητή	el
dc.subject.keyword	Προσεγγιστικοί αλγόριθμοι	el
dc.subject.keyword	Πρόβλημα βελτιστοποίησης	el
dc.date.defense	2026-10-12

Files in this item

Name:
Size:: 7.950Mb
Format:: PDF
Description:: Μεταπτυχιακή διατριβή

View/Open

This item appears in the following Collection(s)

Τμήμα Πληροφορικής
Department of Informatics

Show simple item record

Except where otherwise noted, this item's license is described as
Αναφορά Δημιουργού-Μη Εμπορική Χρήση-Όχι Παράγωγα Έργα 3.0 Ελλάδα