Κατεύθυνση / ειδίκευση Θεωρητική Πληροφορική (ΘΕΩ)
Πληροφορική

2017-07-17

2017

Γιαχούδης Νικόλαος

Βασίλης Ζησιμόπουλος, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών

Προσεγγιστικοί Αλγόριθμοι για το Πρόβλημα του Δάσους Steiner

Ελληνικά

Προσεγγιστικοί Αλγόριθμοι για το Πρόβλημα του Δάσους Steiner

Το πρόβλημα Δάσους Steiner είναι μία γενίκευση του προβλήματος Δέντρου Steiner και
κατ’ επέκταση του Ελάχιστου Επικαλύπτοντος Δέντρου. Αυτά τα προβλήματα είναι ευρέως γνωστά προβλήματα συνδυαστικής βελτιστοποίησης. Επίσης, βρίσκουν πολλές εφαρμογές όπως, η σχεδίαση VLSI κυκλωμάτων, η σχεδίαση τηλεφωνικών δικτύων και η ανακατασκευή φυλογενετικών δέντρων. Επομένως, η μελέτη αυτών των προβλημάτων και η σχεδίαση αλγορίθμων, που τα επιλύουν, είναι σημαντική. Επιλύοντας τα γενικά προβλήματα επιλύουμε και όλα τα σχετικά πρακτικά προβλήματα. Έχει αποδειχθεί από τον Karp ότι το αντίστοιχο πρόβλημα απόφασης του Δέντρου Steiner, και κατ’ επέκταση του Δάσους Steiner, είναι NP-Πλήρες. Επομένως, το να βρούμε σε πωλυωνυμικό χρόνο τη βέλτιστη λύση είναι NP-Δύσκολο, το οποίο σημαίνει ότι θα πρέπει να σχεδιάσουμε προσεγγιστικούς αλγόριθμους. Για αρκετό χρονικό διάστημα οι καλύτεροι αλγόριθμοι συνδυαστικής φύσεως δεν είχαν κάποια σταθερή προσέγγιση, η μόνη 2-προσεγγιστική μέθοδος που είχαμε ήταν μια μέθοδος αρχικού - δυϊκού από την περιοχή του Γραμμικού Προγραμματισμού.
Πρόσφατα, όμως, οι Gupta και Kumar μας έδωσαν έναν 96-προσεγγιστικό αλγόριθμο συνδυαστικής φύσεως. Καλούμαστε, λοιπόν, να βελτιώσουμε την ανάλυση αυτού του αλγόριθμου καθώς και να τον συγκρίνουμε με τον Άπληστο Αλγόριθμο, ο οποίος δεν έχει σταθερή προσέγγιση. Στην παρούσα διπλωματική εργασία δείξαμε ότι ο ”Αδηφάγος” Αλγόριθμος είναι 2-προσεγγιστικός στην κατηγορία των Δέντρων. Επίσης, πραγματοποιήθηκε μία υλοποίηση των δύο αλγορίθμων με σκοπό την πειραματική τους σύγκριση. Είδαμε ότι, οι δύο αλγόριθμοι βρίσκουν λύσεις πολύ κοντά στη βέλτιστη όσον αφορά τα Δέντρα, στην κατηγορία των Πλήρη γραφημάτων είδαμε ότι ο Άπληστος Αλγόριθμος έχει καλύτερη επίδοση και στην κατηγορία των Ψευδοτυχαίων γραφημάτων η επίδοση των αλγορίθμων είναι παρόμοια.

Πληροφορική

Προσεγγιστικοί Αλγόριθμοι, Δάσος Steiner, Δέντρο Steiner, Θεωρία Γραφημάτων, Συνδυαστική Βελτιστοποίηση

Ναι

6

Ναι

24

74

https://pergamos.lib.uoa.gr/uoa/dl/object/1722725/file.pdf

https://pergamos.lib.uoa.gr/uoa/dl/object/1722725