National and Kapodistrian University of Athens
Προσεγγιστικοί Αλγόριθμοι για το Πρόβλημα του Δάσους Steiner
Abstract
dc:descriptionΤο πρόβλημα Δάσους Steiner είναι μία γενίκευση του προβλήματος Δέντρου Steiner και κατ’ επέκταση του Ελάχιστου Επικαλύπτοντος Δέντρου. Αυτά τα προβλήματα είναι ευρέως γνωστά προβλήματα συνδυαστικής βελτιστοποίησης. Επίσης, βρίσκουν πολλές εφαρμογές όπως, η σχεδίαση VLSI κυκλωμάτων, η σχεδίαση τηλεφωνικών δικτύων και η ανακατασκευή φυλογενετικών δέντρων. Επομένως, η μελέτη αυτών των προβλημάτων και η σχεδίαση αλγορίθμων, που τα επιλύουν, είναι σημαντική. Επιλύοντας τα γενικά προβλήματα επιλύουμε και όλα τα σχετικά πρακτικά προβλήματα. Έχει αποδειχθεί από τον Karp ότι το αντίστοιχο πρόβλημα απόφασης του Δέντρου Steiner, και κατ’ επέκταση του Δάσους Steiner, είναι NP-Πλήρες. Επομένως, το να βρούμε σε πωλυωνυμικό χρόνο τη βέλτιστη λύση είναι NP-Δύσκολο, το οποίο σημαίνει ότι θα πρέπει να σχεδιάσουμε προσεγγιστικούς αλγόριθμους. Για αρκετό χρονικό διάστημα οι καλύτεροι αλγόριθμοι συνδυαστικής φύσεως δεν είχαν κάποια σταθερή προσέγγιση, η μόνη 2-προσεγγιστική μέθοδος που είχαμε ήταν μια μέθοδος αρχικού - δυϊκού από την περιοχή του Γραμμικού Προγραμματισμού. Πρόσφατα, όμως, οι Gupta και Kumar μας έδωσαν έναν 96-προσεγγιστικό αλγόριθμο συνδυαστικής φύσεως. Καλούμαστε, λοιπόν, να βελτιώσουμε την ανάλυση αυτού του αλγόριθμου καθώς και να τον συγκρίνουμε με τον Άπληστο Αλγόριθμο, ο οποίος δεν έχει σταθερή προσέγγιση. Στην παρούσα διπλωματική εργασία δείξαμε ότι ο ”Αδηφάγος” Αλγόριθμος είναι 2-προσεγγιστικός στην κατηγορία των Δέντρων. Επίσης, πραγματοποιήθηκε μία υλοποίηση των δύο αλγορίθμων με σκοπό την πειραματική τους σύγκριση. Είδαμε ότι, οι δύο αλγόριθμοι βρίσκουν λύσεις πολύ κοντά στη βέλτιστη όσον αφορά τα Δέντρα, στην κατηγορία των Πλήρη γραφημάτων είδαμε ότι ο Άπληστος Αλγόριθμος έχει καλύτερη επίδοση και στην κατηγορία των Ψευδοτυχαίων γραφημάτων η επίδοση των αλγορίθμων είναι παρόμοια.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Γιαχούδης Νικόλαος
- Giachoudis Nikolaos
Subjects
dc:subject × 2Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1722725