Back to search

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 × 2

Rights

Language dc:language
Ελληνικά, Greek

Identifiers

dc:identifier.*
Identifier
uoadl:1722725

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Γιαχούδης Νικόλαος; Giachoudis Nikolaos. Προσεγγιστικοί Αλγόριθμοι για το Πρόβλημα του Δάσους Steiner. 2017. https://pergamos.lib.uoa.gr/uoa/dl/object/1722725