National and Kapodistrian University of Athens
Extension and evaluation of the global cardinality constraints functionality of the Gecode open source toolkit
Abstract
dc:descriptionΟ Προγραμματισμός με Περιορισμούς είναι μια μεθοδολογία της Τεχνητής Νοημοσύνης που αποσκοπεί να επιλύσει πραγματικά προβλήματα με αποτελεσματικό τρόπο. Σε αυ- τή την διπλωματική εργασία, επεκτείνουμε τον επιλυτή προβλημάτων ικανοποίησης περιορισμών ανοιχτού κώδικα Gecode, συνεισφέροντας στις δυνατότητές του σχετικά με Καθολικούς Περιορισμούς, συγκεκριμένα περιορισμούς Global Cardinality. Ένας Global Cardinality περιορισμός περιορίζει τον αριθμό εμφάνισης τιμών μέσα σε μια συλλογή μεταβλητών, ώστε να βρίσκεται μεταξύ συγκεκριμένων ορίων. Αναπτύσσουμε τον περιορισμό Global Cardinality With Costs, ο οποίος είναι παρόμοιος του Global Cardinality και επιπλέον συσχετίζει ένα κόστος με κάθε ανάθεση τιμής σε μεταβλητή, ενώ ταυτόχρονα απαιτεί το άθροισμα των κοστών να μην ξεπερνάει ένα όριο. Στη συνέχεια προσθέτουμε τον περιορισμό Symmetric Global Cardinality, ο οποίος ορίζεται πάνω σε μεταβλητές που αφορούν σύνολα, δίνοντας επιπλέον περιορισμούς γύρω από τον πληθικό αριθμό του κάθε συνόλου, πέραν των περιορισμών που αφορούν τις τιμές. Ερευνούμε τη βελτιστοποίηση της επίδοσής τους, πειραματιζόμενοι με διάφορες εναλλακτικές επιλογές υλοποίησης, και τελικά τους συγκρίνουμε ώστε να ανακαλύψουμε κάτω από ποιές συνθήκες είναι ωφέλιμοι, σε σχέση με την αποσύνθεσή τους σε περισσότερους απλούστερους περιορισμούς.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Παπατσώρης Ιωάννης
- Papatsoris Ioannis
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:3232625