Επίλυση προβλημάτων δυναμικού προγραμματισμού με χρήση του Matlab
Παπαδόπουλος, Νικόλαος
Η πτυχιακή αυτή εργασία πραγματεύεται την ανάλυση του δυναμικού προγραμματισμού. Μια πολύ γνωστή τεχνική σχεδίασης αλγορίθμων είναι ο δυναμικός προγραμματισμός, ο οποίος στηρίζεται στη φιλοσοφία της ιεραρχικής σχεδίασης, δηλαδή της ανάλυσης ενός προβλήματος από κάτω προς τα επάνω (bottom- up). Πιο συγκεκριμένα, η φιλοσοφία των προβλημάτων αυτών είναι από την αρχή να επιλύονται τα μικρότερα προβλήματα και σταδιακά να επιλύονται τα μεγαλύτερα ως σύνθεση των απλούστερων. Δηλαδή ένας τυπικός αλγόριθμος αυτής της τεχνικής ξεκινά με τα επιμέρους μικρότερου μεγέθους υποπροβλήματα, που επιλύονται με τη χρήση κάποιου κανόνα ή τύπου. Μάλιστα συνήθως τα προσωρινά αποτελέσματα αποθηκεύονται σε ένα πίνακα ώστε να χρησιμοποιηθούν αργότερα χωρίς να απαιτείται να υπολογιστούν ξανά για δεύτερη ή τρίτη φορά. Στη συνέχεια οι επιμέρους αυτές λύσεις συνθέτουν την κατάληξη της τελικής λύσης του αρχικού προβλήματος.
Αυτή η μέθοδος σχεδίασης αλγορίθμων χρησιμοποιείται κυρίως για την επίλυση προβλημάτων βελτιστοποίησης, δηλαδή όταν χρειάζεται να βρεθεί το ελάχιστο ή το μέγιστο κάποιου μεγέθους. Στην προσέγγιση αυτού του τύπου δεν υπάρχει η λογική των επαναληπτικών εκτελέσεων που συναντάτε σε άλλες τεχνικές σχεδίασης αλγορίθμων, όπως η μέθοδος διαίρει και βασίλευε και η άπληστη μέθοδος, αλλά στα προβλήματα αυτά υπάρχει μια συνάρτηση μιας μεταβλητής ή πολλών μεταβλητών που πρέπει να μεγιστοποιηθεί ή να ελαχιστοποιηθεί. Στην ελαχιστοποίηση ή μεγιστοποίηση συναρτήσεων μιας μεταβλητής μπορούν να χρησιμοποιηθούν αναλυτικές και αλγεβρικές μέθοδοι για τον ακριβή ορισμό ελαχίστων ή μεγίστων, ενώ στη μελέτη πολλών μεταβλητών χρησιμοποιούνται αριθμητικές μέθοδοι για έναν προσεγγιστικό ορισμό ελάχιστων (ή μέγιστων) σημείων. Ένα άλλο πρόβλημα δυναμικού προγραμματισμού είναι η βελτιστοποίηση με περιορισμούς, όπου η συνάρτηση ονομάζεται αντικειμενική συνάρτηση.
Σε αυτήν την πτυχιακή εργασία αναλύεται η μέθοδος του Δυναμικού Προγραμματισμού και τα χαρακτηριστικά του. Πιο συγκεκριμένα, στο 1ο κεφάλαιο, αναλύονται τα στοιχειώδη προβλήματα του Δυναμικού Προγραμματισμού καθώς και τα χαρακτηριστικά του. Στο 2ο κεφάλαιο γίνεται μια μικρή αναφορά στα στοιχειώδη προβλήματα διαδρομής, αντικατάστασης εργαλείων και τα προβλήματα ελάχιστης διαδρομής. Στο 3ο κεφάλαιο, παρουσιάζονται πιο αναλυτικά τα προβλήματα διαδρομής. Στο 4ο κεφάλαιο αναλύεται το πρόβλημα της αντικατάστασης εργαλείων καθώς και οι εφαρμογές του. Στο 5ο κεφάλαιο γίνεται αναφορά στο πρόβλημα της κατανομής ενός υλικού και οι εφαρμογές του. Στο 6ο κεφάλαιο γίνεται αναφορά στο πρόβλημα του βέλτιστου φορτίου καθώς και οι εφαρμογές του και τέλος στο 7ο κεφάλαιο, έχουμε τα συμπεράσματα.
