Ο δυναμικός προγραμματισμός αποτελεί μία υπολογιστική μέθοδο η οποία εφαρμόζεται σε προβλήματα που δεν είναι δυνατόν να λυθούν με "άπληστες μεθόδους" (βλ. Greedy algorithm) ή τη μέθοδο "διαίρει και βασίλευε". Θεμέλιο του δυναμικού προγραμματισμού αποτελεί η αρχή βελτιστοποίησης. Είναι μία μέθοδος που είναι εφαρμόσιμη όταν τα υποπροβλήματα που υπάρχουν δεν είναι ανεξάρτητα μεταξύ τους. Ένας αλγόριθμος που είναι προϊόν του δυναμικού προγραμματισμού, επιλύει μία φορά κάθε υποπρόβλημα και αποθηκεύει αυτή τη λύση σε έναν πίνακα, στον οποίον θα καταφεύγει κάθε φορά που συναντά το συγκεκριμένο πρόβλημα. Αποτελεί μία πολύ ισχυρή τεχνική για αλγοριθμική επίλυση προβλημάτων.
Ιστορικά Στοιχεία
Ο όρος δυναμικός προγραμματισμός, θεμελιώθηκε το 1953 από τον Richard Bellman (1920 – 1984) με στόχο να περιγράψει τη διαδικασία επίλυσης προβλημάτων που διασπώνται σε μία αλληλουχία διαδοχικών αποφάσεων. Ο όρος αυτός αναφέρεται στην εξίσωση Bellman, η οποία επαναδιατυπώνει ένα πρόβλημα βελτιστοποίησης με επαναλαμβανόμενη μορφή και αποτελεί κεντρικό αποτέλεσμα του δυναμικού προγραμματισμού. Επομένως η λέξη "προγραμματισμός" χρησιμοποιήθηκε για να δηλώσει την κατάστρωση ενός σχεδίου και δεν έχει καμία σχέση με τον προγραμματισμό υπολογιστών. Χρησιμοποιείται ως συνώνυμο της βελτιστοποίησης και προέρχεται από τον όρο μαθηματικός προγραμματισμός. Η λέξη "δυναμικός", υποδηλώνει την χρονικά μεταβαλλόμενη φύση της διαδικασίας του δυναμικού προγραμματισμού, καθώς συμβαίνει σε πολλαπλά διαδοχικά στάδια. Έτσι καταλήγουμε ότι ο δυναμικός προγραμματισμός είναι μία σχεδιαστική τεχνική που λύνει με αποτελεσματικότερο τρόπο πολύπλοκα προβλήματα βελτιστοποίησης με τη βοήθεια ενός προγράμματος που εφαρμόζει έναν δυναμικό αλγόριθμο προγραμματισμού στον υπολογιστή.
Τύποι Δυναμικού Προγραμματισμού
Υπάρχουν δύο τύποι δυναμικού προγραμματισμού ως προς τον τρόπο που υπολογίζουν τις τιμές ενός προβλήματος. Ο "σύνθετος" και ο "αναλυτικός" δυναμικός προγραμματισμός.
Ο "σύνθετος δυναμικός προγραμματισμός" (bottom-up dynamic programming), υπολογίζει και αποθηκεύει όλες τις τιμές μίας συνάρτησης με τη σειρά, υπολογίζοντας από την μικρότερη τιμή του ορίσματος.
Ο "αναλυτικός δυναμικός προγραμματισμός" (top-down dynamic programming), αποθηκεύει αρχικά τις τιμές που υπολογίζει αποφεύγοντας έτσι τον υπολογισμό των ήδη αποθηκευμένων. Είναι προτιμότερος διότι για την λύση ενός προβλήματος παρέχει μηχανικό τρόπο σχηματισμού και ρυθμίζει αυτόματα τη σειρά υπολογισμού των υποπροβλημάτων του προβλήματος. Το πιο σημαντικό, είναι ότι αποφεύγει την επίλυση υποπροβλημάτων που δεν είναι απαραίτητα και για αυτό αποτελεί αποδοτικότερη μέθοδο.
Παραδείγματα Εφαρμογής
Κάποια δημοφιλή παραδείγματα εφαρμογής του δυναμικού προγραμματισμού είναι:
Προβλήματα δικτύων (π.χ. εύρεση συντομότερων μονοπατιών)
Προβλήματα κατανομής πόρων σε ανταγωνιστικές δραστηριότητες (π.χ. το πρόβλημα του σάκου και η συμπίεση εικόνας)
Προβλήματα πολλαπλών χρονικών περιόδων (π.χ. η αλυσίδα πολλαπλασιασμού μητρών, επενδύσεις, διαχείριση αποθεμάτων και χρηματοοικονομικός προγραμματισμός)
Ανάπτυξη Αλγορίθμου
Η ανάπτυξη ενός αλγορίθμου δυναμικού προγραμματισμού μπορεί να αναλυθεί σε μία σειρά από τέσσερα βήματα:
Χαρακτηρίζουμε τη δομή μιας βέλτιστης λύσης.
Ορίζουμε αναδρομικά την τιμή μιας βέλτιστης λύσης.
Υπολογίζουμε την τιμή μιας βέλτιστης λύσης δουλεύοντας "αναβιβαστικά" (δηλαδή από "κάτω προς τα πάνω" ή από τα "μερικά στα γενικά").
Κατασκευάζουμε μία βέλτιστη λύση από τα δεδομένα που υπολογίστηκαν.
Τα τρία πρώτα βήματα είναι απαραίτητα για την επίλυση ενός προβλήματος χρησιμοποιώντας τη μέθοδο του δυναμικού προγραμματισμού. Εάν επιθυμούμε μπορούμε να συμπεριλάβουμε το 4ο βήμα και συγκεκριμένα την περίπτωση που αναζητούμε μία βέλτιστη λύση. Για να πραγματοποιηθεί αυτό, στο 3ο βήμα, οφείλουμε να κρατήσουμε παραπάνω πληροφορίες ώστε να περάσουμε στο τελευταίο βήμα, που θα επιφέρει τη βέλτιστη λύση.
Αρχή της Βελτιστότητας
Μιλώντας για βέλτιστη υποδομή αναφερόμαστε στο ότι οι βέλτιστες λύσεις των υποπροβλημάτων αποτελούν το κλειδί για την βέλτιστη λύση του γενικότερου προβλήματος. Ο δυναμικός προγραμματισμός δεν μπορεί να εφαρμοστεί αν δε διατηρείται η αρχή της βελτιστότητας. Η πρώτη κίνηση όταν χρησιμοποιούμε τον δυναμικό προγραμματισμό, είναι η δημιουργία της αναδρομικής εξίσωσης για την εύρεση της βέλτιστης λύσης με τη χρήση της αρχής της βελτιστότητας. Αυτή δηλώνει ότι ανεξάρτητα ποια θα είναι η πρώτη απόφαση, όλες οι υπόλοιπες θα πρέπει να προσαρμοστούν και να είναι βέλτιστες σε σχέση με την κατάσταση που θα προκύψει από την πρώτη απόφαση. Αφού λυθεί η αναδρομική εξίσωση - για την τιμή της βέλτιστης λύσης - εκτελείται ένα βήμα αναγωγής όπου κατασκευάζεται η λύση.
Η αναδρομική εξίσωση του δυναμικού προγραμματισμού μπορεί ακόμα να λυθεί με επαναληπτικό κώδικα που αποφεύγει βέβαια τον επανυπολογισμό των ήδη υπολογισμένων τιμών. Ο επαναληπτικός κώδικας έχει τη ίδια χρονική πολυπλοκότητα με τον αναδρομικό κώδικα. Ο πρώτος όμως "κερδίζει" στο γεγονός ότι δεν απαιτεί επιπρόσθετο χώρο για τη στοίβα της αναδρομής. Εν κατακλείδι, ο επαναληπτικός κώδικας έχει ταχύτερη εκτέλεση σε σχέση με τον αναδρομικό κώδικα.
Πλεονεκτήματα και Μειονεκτήματα
Πλεονέκτημα Έχει εφαρμογές σε πάρα πολλά προβλήματα βελτιστοποίησης, ακόμα και σε προβλήματα στοχαστικού βέλτιστου ελέγχου.
Πλεονέκτημα Είναι ιδανική για προγραμματισμό με υπολογιστή.
Πλεονέκτημα Είναι πιο απλοποιημένη μέθοδος αφού χειρίζεται περιορισμούς γενικής φύσης.
Πλεονέκτημα Εγγυάται για το ολικό ελάχιστο.
Πλεονέκτημα Σε σχέση με την μέθοδο της άμεσης απαρίθμησης έχει πιο μειωμένο υπολογιστικό κόστος.
Μειονέκτημα Ο παράγοντας που περιορίζει την εξάπλωση αυτής της μεθόδου είναι η "κατάρα της διαστατικότητας" καθώς υπάρχουν υπερβολικές απαιτήσεις ακόμα και για μικρής τάξης συστήματα.
Μειονέκτημα Δεν είναι πάντα δυνατόν να βρεθεί μία αναλυτική λύση.
Κόστος
Το κύριο υπολογιστικό κόστος του δυναμικού προγραμματισμού προέρχεται από την παραμετρική λύση των υποπροβλημάτων το οποίο είναι παρ'όλα αυτά πολύ μικρότερο από το κόστος που θα είχε η πλήρης απαρίθμηση και αξιολόγηση των συνολικών δυνατών λύσεων. Επειδή όμως το κόστος του δυναμικού προγραμματισμού είναι αρκετά μεγάλο, τον χρησιμοποιούμε μόνο για να λύσουμε προβλήματα που δεν είναι εφικτό να λυθούν με Γραμμικό ή Ακέραιο προγραμματισμό. Ο δυναμικός προγραμματισμός επί της ουσίας είναι πιο ευέλικτος σε σχέση με άλλες μεθόδους, αλλά έχει αρκετά αυξημένο και υψηλό υπολογιστικό κόστος.
Πηγές
Datseris 2010 Αρχειοθετήθηκε 2013-09-03 στο Wayback Machine.
Ch10 slides[νεκρός σύνδεσμος]
4b-Dynamic-Programming
Otenet: Dynamic-Programming Αρχειοθετήθηκε 2015-03-21 στο Wayback Machine.
Auth: Dynamic-Programming
Βιβλιογραφία
Sartaj Sahni (2004). Δομές Δεδομένων: Αλγόριθμοι και εφαρμογές στη C++. εκδόσεις Τζιόλα.
Thomas H. Cormen· Charles E. Leiserson· Ronald L. Rivest· Clifford Stein (2012). Εισαγωγή στους αλγορίθμους. Πανεπιστημιακές Εκδόσεις Κρήτης..
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
