Dynamic programming — Δυναμικός Προγραμματισμός

Δυναμικός Προγραμματισμός (ΔΠ· αγγλ. dynamic programming, DP) — είναι μέθοδος επίλυσης σύνθετων προβλημάτων βελτιστοποίησης, που βασίζεται στη διάσπαση του αρχικού προβλήματος σε μια ακολουθία απλούστερων υποπροβλημάτων. Η μέθοδος εφαρμόζεται σε πολυβηματικές διαδικασίες λήψης αποφάσεων, όπου η βέλτιστη λύση ολόκληρου του προβλήματος μπορεί να κατασκευαστεί από τις βέλτιστες λύσεις των υποπροβλημάτων του.

Ο όρος εισήχθη από τον Αμερικανό μαθηματικό Ρίτσαρντ Μπέλλμαν τη δεκαετία του 1950. Στο πλαίσιο αυτό, η λέξη «προγραμματισμός» χρησιμοποιείται με την έννοια του «σχεδιασμού» ή της «κατάρτισης βέλτιστου σχεδίου δράσης», και όχι με την έννοια της συγγραφής κώδικα υπολογιστή.

Βασικές ιδιότητες και θεωρήματα

Η εφαρμοσιμότητα του δυναμικού προγραμματισμού σε ένα πρόβλημα καθορίζεται από την ύπαρξη δύο θεμελιωδών ιδιοτήτων.

Αρχή βελτιστότητας του Μπέλλμαν

Κεντρική έννοια της μεθόδου είναι η αρχή βελτιστότητας του Μπέλλμαν (αγγλ. Bellman's principle of optimality). Αυτή ορίζει: ανεξάρτητα από την αρχική κατάσταση και την αρχική απόφαση, οι επακόλουθες αποφάσεις πρέπει να αποτελούν βέλτιστη στρατηγική ως προς την κατάσταση που προέκυψε από την πρώτη απόφαση.

Με άλλα λόγια, οποιοδήποτε τμήμα μιας βέλτιστης τροχιάς είναι από μόνο του βέλτιστο. Αυτή η ιδιότητα επιτρέπει τη διάσπαση του συνολικού προβλήματος σε μια ακολουθία απλούστερων υποπροβλημάτων και την αναδρομική επίλυσή τους.

Επικαλυπτόμενα υποπροβλήματα

Ενα πρόβλημα διαθέτει την ιδιότητα των επικαλυπτόμενων υποπροβλημάτων (αγγλ. overlapping subproblems) εάν κατά την αναδρομική επίλυσή του τα ίδια υποπροβλήματα εμφανίζονται επανειλημμένα. Ο ΔΠ επιτρέπει την αποφυγή επαναλαμβανόμενων υπολογισμών, αποθηκεύοντας τις λύσεις των ήδη συναντηθέντων υποπροβλημάτων (αυτή η τεχνική ονομάζεται memoization ή tabulation), γεγονός που αυξάνει σημαντικά την αποδοτικότητα σε σύγκριση με την αφελή αναδρομική εξάντληση.

Εξίσωση Μπέλλμαν

Από την αρχή βελτιστότητας απορρέει η βασική αναδρομική σχέση της μεθόδου — η εξίσωση Μπέλλμαν. Αυτή συνδέει την «αξία» (βέλτιστο κέρδος ή κόστος) της τρέχουσας κατάστασης με τις αξίες των επακόλουθων καταστάσεων. Στη γενική μορφή για ντετερμινιστική πολυβηματική διαδικασία με προσθετική αντικειμενική συνάρτηση έχει τη μορφή:

$V_{k-1}(x)=\underset{y\in U(x)}{\max }\{{\phi }_k(x,y)+V_k(f_k(x,y))\}$

όπου:

• $k$ — ο αριθμός βήματος (από $m$ έως 1)·
• $x$ — η κατάσταση του συστήματος στο βήμα $k-1$·
• $y$ — η ελεγχόμενη απόφαση που λαμβάνεται στο βήμα $k$·
• ${\phi }_k(x,y)$ — το κέρδος (ή το κόστος) στο k-οστό βήμα·
• $f_k(x,y)$ — η συνάρτηση που ορίζει τη νέα κατάσταση του συστήματος·
• $V_k(s)$ — η βέλτιστη τιμή της αντικειμενικής συνάρτησης για το υποπρόβλημα που ξεκινά στο βήμα $k$ στην κατάσταση $s$.

Η εξίσωση επιλύεται διαδοχικά, συνήθως «από το τέλος», κινούμενη από το τελευταίο βήμα προς το πρώτο.

Παραδείγματα εφαρμογής

• Πρόβλημα συντομότερης διαδρομής σε γράφο: Αυτό το πρόβλημα διαθέτει την ιδιότητα της βέλτιστης υποδομής, καθώς οποιοδήποτε τμήμα της συντομότερης διαδρομής είναι από μόνο του συντομότερο. Οι αλγόριθμοι Bellman-Ford και Floyd-Warshall αποτελούν κλασικά παραδείγματα εφαρμογής ΔΠ για την επίλυση αυτού του προβλήματος.
• Πρόβλημα σακιδίου (knapsack): Πρόβλημα βέλτιστης πλήρωσης σακιδίου περιορισμένης χωρητικότητας με αντικείμενα διαφορετικής αξίας και βάρους. Ο ΔΠ επιτρέπει την επίλυση αυτού του προβλήματος εξετάζοντας τα αντικείμενα διαδοχικά και υπολογίζοντας σε κάθε βήμα τη μέγιστη αξία για όλες τις πιθανές τιμές της εναπομένουσας χωρητικότητας.
• Πρόβλημα κατανομής πόρων: Κατανομή περιορισμένου πόρου (π.χ. επενδύσεων) μεταξύ πολλών έργων για τη μεγιστοποίηση του συνολικού αποτελέσματος.

Περιορισμοί

Ο κύριος περιορισμός της μεθόδου είναι η κατάρα της διαστασιμότητας (αγγλ. curse of dimensionality) — όρος που εισήγαγε ο Μπέλλμαν για να δηλώσει την εκθετική αύξηση του αριθμού καταστάσεων και, κατά συνέπεια, της υπολογιστικής πολυπλοκότητας, με την αύξηση του αριθμού των μεταβλητών που περιγράφουν την κατάσταση του συστήματος. Αυτό περιορίζει την πρακτική εφαρμογή του ακριβούς ΔΠ για προβλήματα πολύ μεγάλης διαστασιμότητας.

Συναφείς έννοιες

• Επιχειρησιακή έρευνα
• Θεωρία βέλτιστου ελέγχου
• Διαδικασία απόφασης Markov (στοχαστική γενίκευση)
• Εξίσωση Hamilton — Jacobi — Bellman (ανάλογο για συνεχή χρόνο)

Παραπομπές

</references>