Αποδοτικοί αλγόριθμοι ισχυρής συνέπειας και προσαρμοστικές τεχνικές για προβλήματα ικανοποίησης περιορισμών

Περίληψη

Ο Προγραμματισμός με Περιορισμούς (Constraint Programming - CP) είναι μια επιτυχημένητεχνολογία για την επίλυση πολλών προβλημάτων από το χώρο των επιχειρήσεων και τηςβιομηχανίας, που απαιτούν την ικανοποίηση μιας σειράς πολύπλοκων περιορισμών.Παραδείγματα τέτοιων προβλημάτων είναι η διαμόρφωση προϊόντος, η κατανομή πόρων, ταπροβλήματα μεταφοράς και χρονοπρογραμματισμού. Επειδή η ταυτόχρονη ικανοποίηση τωνδιαφόρων περιορισμών είναι γενικά δυσεπίλυτη, τα προβλήματα μπορεί να γίνουν ακόμηδυσκολότερα καθώς αυξάνει το μέγεθός τους. Ο Προγραμματισμός με Περιορισμούς έχειαναπτύξει διάφορες τεχνικές για να αντιμετωπίσει αυτό το εγγενές πρόβλημα. Μια από τις πιοσημαντικές τέτοιες τεχνικές είναι η εφαρμογή τοπικής συνέπειας.Οι τοπικές συνέπειες που έχουν ευρέως μελετηθεί και χρησιμοποιηθεί από συστήματαεπίλυσης είναι η συνέπεια ορίων (Bounds Consistency - BC) και η συνέπεια τόξου (ArcConsistency - AC). Παρότι έχουν προταθεί και ισχυρότερες τοπικές συνέπειες, η χρήση τους είναιπεριορισμένη λόγω ...
περισσότερα

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

Constraint Programming (CP) is a successful technology for solving a wide range of problemsin business and industry which require the satisfaction of a set of complex constraints.Examples include product configuration, resource allocation, transportation, andscheduling. As the simultaneous satisfaction of different constraints is intractable in general,problems can become very difficult to solve as their size increases. CP has thusdeveloped various techniques to tackle this inherent problem. Enforcing a local consistencyproperty is one of the most important such techniques.Bounds Consistency (BC) and Generalised Arc Consistency (GAC) are the two mostwidely studied and used local consistencies in CP solvers. While there exist strongerlocal consistency (SLC) properties, their usage is limited due to their prohibitive cost.Examples are max Restricted Path Consistency (maxRPC) and max Restricted PairWiseConsistency (maxRPWC).In our research, we propose efficient filtering algorithms for en ...
περισσότερα

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

DOI
10.12681/eadd/31791
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/31791
ND
31791
Εναλλακτικός τίτλος
Efficient algorithms for strong local consistencies and adaptive techniques in constraint satisfaction problems
Συγγραφέας
Παπαρρίζου, Αναστασία του Κωνσταντίνος
Ημερομηνία
2013
Ίδρυμα
Πανεπιστήμιο Δυτικής Μακεδονίας. Σχολή Πολυτεχνική. Τμήμα Μηχανικών Πληροφορικής και Τηλεπικοινωνιών
Εξεταστική επιτροπή
Στεργίου Κωνσταντίνος
Κουμπαράκης Εμμανουήλ
Σαμαράς Νικόλαος
Bessiere Christian
Δασυγένης Μηνάς
Ρεφανίδης Ιωάννης
Βασιλειάδης Νικόλαος
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
Επιστήμες Μηχανικού και Τεχνολογία
Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
Λέξεις-κλειδιά
Ισχυρές τοπικές συνέπειες; Προσαρμοστικές τεχνικές; Ισχυρή συνέπεια ορίων; Τεχνικές διάδοσης περιορισμών; Αλγόριθμοι φιλτραρίσματος; Προβλήματα ικανοποίησης περιορισμών
Χώρα
Ελλάδα
Γλώσσα
Αγγλικά
Άλλα στοιχεία
217 σ., πιν., σχημ., ευρ.
Στατιστικά χρήσης
ΠΡΟΒΟΛΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Google Analytics.
ΞΕΦΥΛΛΙΣΜΑΤΑ
Αφορά στο άνοιγμα του online αναγνώστη.
Πηγή: Google Analytics.
ΜΕΤΑΦΟΡΤΩΣΕΙΣ
Αφορά στο σύνολο των μεταφορτώσων του αρχείου της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
ΧΡΗΣΤΕΣ
Αφορά στις μοναδικές επισκέψεις της διδακτορικής διατριβής.
Πηγή: Εθνικό Αρχείο Διδακτορικών Διατριβών.
Σχετικές εγγραφές (με βάση τις επισκέψεις των χρηστών)