Αλγόριθμοι για την ακριβή λύση προβλημάτων συνδυαστικής βελτιστοποίησης

Περίληψη

Το Shortest Superstring Problem (SSP) είναι ένα πρόβλημα συνδυαστικής βελτιστοποίησης που έχει προσελκύσει το ενδιαφέρων πολλών ερευνητών, λόγω των εφαρμογών του. Μπορεί να χρησιμοποιηθεί σε προβλήματα Υπολογιστικής Μοριακής Βιολογίας όπως η αλληλούχιση του DNA και σε προβλήματα της επιστήμης υπολογιστών όπως η συμπίεση δεδομένων. Το SSP είναι ένα NP-hard πρόβλημα. Ένα άρθρο ανασκόπησης για το SSP παρουσιάζεται στο πρώτο κεφάλαιο της παρούσας διατριβής με έναν περιεκτικό και σαφή τρόπο, καλύπτοντας ολόκληρη τη σχετική βιβλιογραφία, αναδεικνύοντας την κατακτημένη γνώση και βοηθώντας στην μελλοντική έρευνα.Η μέθοδος GRASP (Greedy Randomized Adaptive Search Procedure) είναι μια επαναληπτική ευρετική μέθοδος για συνδυαστική βελτιστοποίηση. Η μέθοδος Path Relinking (PR) αποτελεί έναν τρόπο ενοποίησης των στρατηγικών εντατικοποίησης και διαφοροποίησης στην αναζήτηση για βέλτιστες λύσεις. Η PR στα πλαίσια του GRASP εισήχθη ως μηχανισμός μνήμης για την αξιοποίηση των δεδομένων από καλές λύσεις ...
περισσότερα

Περίληψη σε άλλη γλώσσα

The Shortest Superstring Problem (SSP) is a combinatorial optimization problem which has attracted the interest of many researchers due to its applications. It can be applied in computational molecular biology problems such as DNA sequencing, and in computer science problems such as string compression. A concise survey for the SSP is presented in the first chapter of this dissertation covering the whole relevant literature, revealing the knowledge that is already conquered, and paving the path for further development in the study of shortest superstrings.A Greedy Randomized Adaptive Search Procedure (GRASP) is an iterative meta-heuristic for combinatorial optimization. Path Relinking (PR) is an approach to integrate intensification and diversification strategies in search for optimal solutions. In this dissertation, an implementation of GRASP with PR for solving the SSP is presented. It solves large scale SSP instances and outperforms the natural greedy algorithm in the majority of the ...
περισσότερα

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/34605
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/34605
ND
34605
Εναλλακτικός τίτλος
Algorithms for exact solutions to combinatorial optimization problems
Συγγραφέας
Γκεβεζές, Θεόδωρος του Πασχάλης
Ημερομηνία
2013
Ίδρυμα
Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ). Σχολή Πολυτεχνική. Τμήμα Γενικό. Τομέας Υπολογιστικών Μεθόδων και Προγραμματισμού Η/Υ
Εξεταστική επιτροπή
Πιτσούλης Λεωνίδας
Παρδαλός Πάνος
Μυγδαλάς Αθανάσιος
Τσούρος Κωνσταντίνος-Κλαύδιος
Ζιούτας Γεώργιος
Καραμπετάκης Νικόλαος
Ραχώνης Γεώργιος
Επιστημονικό πεδίο
Φυσικές ΕπιστήμεςΕπιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Φυσικές ΕπιστήμεςΒιολογία
Λέξεις-κλειδιά
Συνδυαστική βελτιστοποίηση; Υπολογιστική μοριακή βιολογία; Πρόβλημα βραχύτερης υπερακολουθίας; Τετραγωνικό πρόβλημα ανάθεσης; Αλληλούχιση DNA; Συμπίεση δεδομένων; Γράφοι επικάλυψης; Άπληστος αλγόριθμος
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
xvii, 157 σ., πιν., σχημ., ευρ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Σχετικές εγγραφές (με βάση τις επισκέψεις των χρηστών)