Extension and evaluation of the global cardinality constraints functionality of the Gecode open source toolkit

Διπλωματική Εργασία uoadl:3232625 64 Αναγνώσεις

Μονάδα:
Κατεύθυνση Υπολογιστικά Συστήματα: Λογισμικό και Υλικό
Πληροφορική
Ημερομηνία κατάθεσης:
2022-10-05
Έτος εκπόνησης:
2022
Συγγραφέας:
Παπατσώρης Ιωάννης
Στοιχεία επιβλεπόντων καθηγητών:
Παναγιώτης Σταματόπουλος, Επίκουρος Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
Extension and evaluation of the global cardinality constraints functionality of the Gecode open source toolkit
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Επέκταση και αξιολόγηση των καθολικών περιορισμών πληθικότητας στην πλατφόρμα ανοιχτού κώδικα Gecode
Περίληψη:
Ο Προγραμματισμός με Περιορισμούς είναι μια μεθοδολογία της Τεχνητής Νοημοσύνης
που αποσκοπεί να επιλύσει πραγματικά προβλήματα με αποτελεσματικό τρόπο. Σε αυ-
τή την διπλωματική εργασία, επεκτείνουμε τον επιλυτή προβλημάτων ικανοποίησης περιορισμών ανοιχτού κώδικα Gecode, συνεισφέροντας στις δυνατότητές του σχετικά με Καθολικούς Περιορισμούς, συγκεκριμένα περιορισμούς Global Cardinality. Ένας Global Cardinality περιορισμός περιορίζει τον αριθμό εμφάνισης τιμών μέσα σε μια συλλογή μεταβλητών, ώστε να βρίσκεται μεταξύ συγκεκριμένων ορίων. Αναπτύσσουμε τον περιορισμό Global Cardinality With Costs, ο οποίος είναι παρόμοιος του Global Cardinality και επιπλέον συσχετίζει ένα κόστος με κάθε ανάθεση τιμής σε μεταβλητή, ενώ ταυτόχρονα απαιτεί το άθροισμα των κοστών να μην ξεπερνάει ένα όριο. Στη συνέχεια προσθέτουμε τον περιορισμό Symmetric Global Cardinality, ο οποίος ορίζεται πάνω σε μεταβλητές που αφορούν σύνολα, δίνοντας επιπλέον περιορισμούς γύρω από τον πληθικό αριθμό του κάθε συνόλου, πέραν των περιορισμών που αφορούν τις τιμές. Ερευνούμε τη βελτιστοποίηση της επίδοσής τους, πειραματιζόμενοι με διάφορες εναλλακτικές επιλογές υλοποίησης, και τελικά τους συγκρίνουμε ώστε να ανακαλύψουμε κάτω από ποιές συνθήκες είναι ωφέλιμοι, σε σχέση με την αποσύνθεσή τους σε περισσότερους απλούστερους περιορισμούς.
Κύρια θεματική κατηγορία:
Τεχνολογία – Πληροφορική
Λέξεις-κλειδιά:
επιλυτής προβλημάτων ικανοποίησης περιορισμών, ανοιχτός κώδικας, gecode, καθολικός περιορισμός, global cardinality
Ευρετήριο:
Ναι
Αρ. σελίδων ευρετηρίου:
4
Εικονογραφημένη:
Ναι
Αρ. βιβλιογραφικών αναφορών:
38
Αριθμός σελίδων:
79