ΘΕΜΑ Ι Πακετοποίηση - Packing

Γενικά Βασικές έννοιες

Κατασκευαστικοί Αλγόριθμοι

Τα προβλήματα διακριτής αριστοποίησης τα αντιμετωπίζουμε γενικά με επαναληπτικές διαδικασίες που τις καλούμε 'Κατασκευαστικούς αλγορίθμους'. Οι Κατασκευαστικοί αλγόριθμοι παίρνουν το όνομα τους από τη διαδικασία επίλυσης που ορίζουν, όπου ξεκινούν από το κενό σύνολο και σταδιακά σε κάθε κύκλο επίλυσης το εμπλουτίζουν, δηλαδή το κατασκευάζουν.

Η εκκίνηση της διαδικασίας ενός Κατασκευαστικού αλγορίθμου γίνεται έχοντας δυο σύνολα, το κενό σύνολο και το σύνολο των αντικειμένων/ δεδομένων του προβλήματος που θα το καλούμε 'Υπόδειγμα'. Έτσι σε κάθε επανάληψη ενός Κατασκευαστικού αλγορίθμου επιλέγουμε από το υπόδειγμα ένα αντικείμενο και το τοποθετούμε στο υπόδειγμα της λύσης. Κάθε κίνηση προχωρά στην επόμενη αφόσον γίνεται αξιολόγηση κατά πόσο βελτιώνεται το 'κόστος' της διαδικασίας.

Κατά τη διάρκεια της επαναληπτικής διαδικασίας το κενό σύνολο εμπλουτίζεται και δημιουργεί αυτό που καλείται 'μερική λύση'. Η μερική λύση κατά τη λήξη του αλγορίθμου οριστικοποιείται ως τελική.

Οι Κατασκευαστικοί αλγόριθμοι γενικά χαρακτηρίζονται από την διαδικασία επιλογής αντικειμένων για την κατασκευή της μερικής λύσης και εν συνεχεία της οριστικής. Διακρίνουμε δυο βασικές κατηγορίες:

• - Τυχαίους
• - Αιτιοκρατικούς, π.χ. Πλεονεξία(Greedy)

Πρόβλημα Πακετοποίησης

Ορισμός

Το πρόβλημα της Πακετοποίησης ορίζεται ως το πρόβλημα τοποθέτησης αντικειμένων σε έναν μεγάλο χώρο. Εξαιτίας της πολυπλοκότητας του παραπάνω εγχειρήματος από την ύπαρξη πολυάριθμων παραμέτρων το πρόβλημα ανήκει στην κατηγορία των NP-hard προβλημάτων, δηλαδή σε προβλήματα που ο χρόνος επίλυσης διέπεται από κάποια πολυωνυμική σχέση βαθμού n η οποία ορίζει το βαθμό πολυπλοκότητας του συστήματος, και η πολυωνυμική αυτή σχέση που ορίζει το χρονο επίλυσης δεν μπορεί να οριστεί σαφώς (Non-deterministic Polynomial-time hard). Έτσι τα προβλήματα αυτής της κατηγορίας έχουν το χαρακτηριστικό ότι η εξεύρεση της Παγκόσμιας (Global) βέλτιστης λύσης είναι μια πολύ δύσκολη υπόθεση.

Στόχοι του προβλήματος

• • Οργάνωση Χώρου αποθήκης
• • Γρήγορη Εύρεση αντικειμένου
•
• • Εξοικονόμηση Χώρου (όγκος)
• • Εξοικονόμηση Ενέργειας (για παράδειγμα κόστος ψύξης, φωτισμού, κλπ)

Πρόβληματα Πακετοποίησης

• • Μονοδιάστατης Πακετοποίησης
• • Διδιάστατης Πακετοποίησης
• • Τριδιάστατης Πακετοποίησης