Αυτή η σελίδα στα Αγγλικά

Δυναμικος Προγραμματισμος

         

Αυτές οι σελίδες παρουσιάζουν τα βασικά στοιχεία του Δυναμικού Προγραμματισμού μέσω αντιπροσωπευτικών παραδειγμάτων.
Αν δεν έρχεστε εδώ για πρώτη φορά, μπορείτε να παραλείψετε την ενότητα των Ερωταπαντήσεων και να μεταβείτε κατευθείαν στην ενότητα των Προβλημάτων.

Ερωτήσεις και απαντήσεις

Τι είναι ο Δυναμικός Προγραμματισμός;

Τι είναι η αρχή της βελτιστότητας (βέλτιστης υπο-δομής);
Λέμε ότι ένα πρόβλημα διέπεται από την αρχή της βελτιστότητας (optimality) ή βέλτιστης υπο-δομής (optimal substructure) όταν μπορεί να αναλυθεί σε υποπροβλήματα κατά τέτοιον τρόπο ώστε η βέλτιστη λύση να περιέχει επίσης τις βέλτιστες λύσεις των υποπροβλημάτων.
Για παράδειγμα, έστω το παρακάτω οδικό δίκτυο που συνδέει τις πόλεις c1 έως c9. Το di,j δηλώνει την απόσταση μεταξύ των πόλεων ci και cj.

Έστω ότι το συντομότερη μονοπάτι από το c1 στο c9 είναι το c1-c2-c4-c7-c9.
Αυτό το συντομότερο μονοπάτι περιέχει επίσης ένα συντομότερο μονοπάτι ανάμεσα σε οποιοδήποτε ζευγάρι πόλεων από τις c1, c2, c4, c7, c9.
Για παράδειγμα, ένα συντομότερο μονοπάτι από το c2 στο c7 είναι το c2-c4-c7.
Για να το αποδείξουμε, μπορούμε να χρησιμοποιήσουμε το επιχείρημα copy-paste: αν υπήρχε ένα άλλο μονοπάτι από το c2 στο c7 που να είναι συντομότερο από το c2-c4-c7, τότε θα μπορούσαμε να χρησιμοποιήσουμε αυτό αντί για το c2-c4-c7 ως μέρος του συντομότερου μονοπατιού από το c1 στο c9, έτσι ώστε να έχουμε ένα μονοπάτι συντομότερο από το c1-c2-c4-c7-c9. Τότε όμως θα είχαμε αντίφαση, αφού το c1-c2-c4-c7-c9 δε θα ήταν ένα συντομότερο μονοπάτι από το c1 στο c9, όπως αρχικά υποθέσαμε.
Γι΄αυτό λέμε ότι το πρόβλημα του συντομότερου μονοπατιού διέπεται από την αρχή της βελτιστότητας: ένα συντομότερο μονοπάτι ανάμεσα σε δυο κόμβους περιέχει (και αποτελείται αποκλειστικά από) τα συντομότερα μονοπάτια ανάμεσα σε οποιουσδήποτε δύο από τους κόμβους που το αποτελούν.

Προφανώς, όταν η λύση ενός προβλήματος μπορεί να περιγραφεί με μια αναδρομική σχέση, το πρόβλημα διέπεται από την αρχή της βελτιστότητας.

Η αρχή της βελτιστότητας όπως περιγράφηκε αρχικά από τον Bellman υπάρχει εδώ.

Τι είναι η αρχή των επικαλυπτόμενων υποπροβλημάτων;
Λέμε ότι ένα πρόβλημα διέπεται από την αρχή των επικαλυπτόμενων υποπροβλημάτων (overlapping subproblems) όταν μπορεί να αναλυθεί σε υποπροβλήματα κατά τέτοιον τρόπο ώστε τα υποπροβλήματα δεν είναι ανεξάρτητα αλλά ένας μέρος των υπολογισμών που απαιτούνται για την επίλυσή τους είναι κοινό.
Αυτό σημαίνει ότι τα αποτελέσματα αυτών των υπολογισμών χρειάζονται περισσότερες από μία φορές. Κι αν δεν τα αποθηκεύσουμε κάπου για αν τα χρησιμοποιήσουμε αργότερα, θα πρέπει να κάνουμε τους ίδιους υπολογισμούς ξανά και ξανά.
Αυτό επίσης σημαίνει ότι αν και το πλήθος των μοναδικών (διαφορετικών) υπολογισμών που πρέπει να γίνουν είναι μικρό, η επαναλαμβανόμενη εκτέλεση των ιδιων υπολογισμών ξανά και ξανά έχει ως αποτέλεσμα ένα συνολικό πλήθος υπολογισμώνμ (μη μοναδικών) που αυξάνεται εκθετικά ως προς την είσοδο του προβλήματος.

Ας δούμε ένα παράδειγμα.
Όπως ίσωε ξέρεις, οι αριθμοί Fibonacci είναι η ακολουθία
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Εκτός από τους δυο πρώτους όρους που εξ ορισμού είναι 0 και 1, κάθε επόμενος όρος της ακολουθίας είναι το άθροισμα των δύο προηγούμενών του.
Ο n-οστός αριθμός Fibonacci δίνεται από την εξής αναδρομική σχέση:
Fn = Fn-1 + Fn-2, όπου F0 = 1 και F1 = 1.

Το πρόβλημα του υπολογισμού του n-οστού αριθμού Fibonacci διέπεται από την αρχή των επικαλυπτόμενων προβλημάτων.
Γιατί;
Έστω ότι θέλουμε να υπολογίσουμε το 9ο αριθμό Fibonacci, δηλ. το F9
Από την παραπάνω αναδρομική σχέση έχουμε ότι
F9 = F8 + F7
Από την ίδια αναδρομική σχέση έχουμε επίσης ότι
F8 = F7 + F6
Για να δούμε τα παραπάνω ως μέρος του παρακάτω γράφου εξαρτήσεων.

Παρατηρούμε ότι η τιμή του F7 είναι προαπαιτούμενι για τον υπολογισμό και του F9 και του F8.
Έτσι, ο υπολογισμός των F9 και F8 είναι επικαλυπτόμενα υποπροβλήματα, αφού μέρος των υπολογισμών που απαιτούνται για την επίλυσή τους είναι κοινό, δηλ. και για τα δύο απαιτείται ο υπολογισμός του F7. Και θα πραγματοποιηθούν περισσότερες από μία αναδρομικές κλήσεις με την ίδια παράμετρο για τον υπολογισμό του F7.

Βλέποντας παρακάτω τον πλήρη γράφο εξάρτησης για τον υπολογισμό του F9, παρατηρούμε ότι κάθε όρος (εκτός από τον F8) είναι προαπαιτούμενο για τον υπολογισμό δύο άλλων.

Το γεγονός ότι έχουμε επικαλυπτόμενα υποπροβλήματα συνεπάγεται ότι αν υπολογίσουμε το F9 με απλή "χαζή" αναδρομή, οι ίδιοι υπολογισμοί θα πραγματοποιηθούν πολλές φορές. Θα πραγματοποιηθούν πολλές αναδρομικές κλήσεις με την ίδια παράμετρο για να υπολογιστούν ξανά οι λύσεις στα ίδια υποπροβλήματα.
Κάποιος θα μπορούσε να πει "Εντάξει, από τα παραπάνω φαίνεται ότι κάθε υπολογισμός θα πραγματοποιηθεί δυο φορές, δε χάλασε κι ο κόσμος".
Δυστυχώς, λόγω της αναδρομικής φύσης του αλγορίθμου, το πλήθος των υπολογισμών αυξάνεται εκθετικά με το n.
Και παρόλο που για τον υπολογισμό του Fn ο τιμή κάθε προηγούμενου όρου απαιτείται δυο φορές (εκτός από του Fn-1 που απαιτείται μόνο μία), μια απλή "χαζή" αναδρομική υλοποίηση θα είχε ως αποτέλεσμα ένα πλήθος υπολογισμών που θα αυξανόταν εκθετικά με το n. Για αν είμαστε ακριβείς, το πλήθος των υπολογισμών είναι ανάλογο του (1.6)n.
Τα καλά νεά είναι ότι αν την πρώτη φορά που υπολογίζουμε κάθε τιμή την αποθηκεύουμε, είτε χρησιμοποιώντας αναδρομή με μνήμη (memoization) είτε υπολογίζοντας τους όρους επαναληπτικά από το μικρότερο προς το μεγαλύτερο με τη σειρά που προκύπτει από το γράφο εξάρτησης (που θα πρέπει να είναι ένα Κατευθυνόμενο Ακυκλικό Γράφημα (Directed Acyclic Graph - DAG), θα κάνουμε μόνο όσους υπολογισμούς είναι απαραίτητο. Και αυτή είναι η ουσία του Δυναμικού Προγραμματισμού.

Όλα τα παραπάνω θα γίνουν απολύτως κατανοητά στην αναλυτική περιγραφή του προβλήματος των αριθμών Fibonacci στο τμήμα προβλημάτων παρακάτω.

Ερώτηση: μπορείς να διακρίνεις την αρχή των επικαλυπτόμενων υποπροβλημάτων στο πρόβλημα του συντομότερου μονοπατιού στο παραπάνω οδικό δίκτυο;

Ο Δυναμικός Προγραμματισμός μου μοιάζει με το Διαίρει και Βασίλευε (Divide and Conquer). Κάνω λάθος;
Και ναι και όχι.
Ο Δυναμικός Προγραμματισμός είναι μια τεχνική Διαίρει και Βασίλευε αφού λύνει τα προβλήματα αναλύοντάς τα σε άλλα μικρότερα -και συνεπώς απλούστερα- υποπροβλήματα.
Αλλά υπάρχουν δυο βασικές διαφορές ανάμεσα στο Δυναμικό Προγραμματισμό και το Διαίρει και Βασίλευε όπως εφαρμόζεται συνήθωως σε κλασσικούς αλγορίθμους του είδους (όπως οι merge sort, quicksort, ο αλγόριθμος του Karatsuba για τον πολλαπλασιαμό πινάκων, κτλ):
Μπορεί κάποια προβλήματα να λύνονται και με αλγόριθμους Δυναμικού Προγραμματισμού και με αλγόριθμους Διαίρει και Βασίλευε;
Ναι. Για παράδειγμα, το Maximum Subarray Problem λύνεται και με αλγόριθμο Δυναμικού Προγραμματισμού και με αλγόριθμο Διαίρει και Βασίλευε. Η λύση του μπορεί να εκφραστεί είτε με όρους επικαλυπτόμενων υποπροβλημάτων είτε με όρους ανεξάρτητων υποπροβλημάτων.

Πώς ξεκίνησε ο Δυναμικός Προγραμματισμός;
Ο όρος Dynamic Programming επινοήθηκε από τον Richard Bellman το '50 για να περιγράψει διαδικασίες λήψης αποφάσεων πολλαπλών σταδίων.
Η λέξη programming δεν είχε καμιά σχέση με τον προγραμματισμό υπολογιστών: χρησιμοποιήθηκε για να υποδηλώσει την κατάστρωση σχεδίου (planning).
και η λέξη dynamic χρησιμοποιήθηκε για να υποδηλώσει τη χρονικά μεταβαλλόμενη φύση της διαδικασίας, αφού συμβαίνει σε πολλαπλά διαδοχικά στάδια.
Στην αυτοβιογραφία του Eye of the Hurricane: An Autobiography όπου ο Bellman αιτιολογεί τη χρήση του όρου Dynamic Programming, αναφέρεται επίσης και σε κάποιους άλλους λόγους που επέδρασαν στην χρήση του συγκεκριμένου όρου. Μπορείς να διαβάσεις το σχετικό απόσπασμα.


Εκτός από εδώ, πού αλλού μπορώ να βρω περισσότερα για το Δυναμικό Προγραμματισμό;
Εκτός από την πληθώρα του υλικού που υπάρχει στο web, δες και τις προτάσεις στο τμήμα Περαιτέρω μελέτη στο τέλος της σελίδας.

Προβλήματα

Ακολουθούν κάποια αντιπροσωπευτικά προβλήματα τα οποία μπορούν να λυθούν αποδοτικά με αλγορίθμους Δυναμικού Προγραμματισμού
Οι αλγόριθμοι Δυναμικού Προγραμματισμού γι' αυτά τα προβλήματα θα παρουσιαστούν κι εδώ κάποια στιγμή μέσα στο 2014.

Fibonacci numbers

Minimum Coin Change

Integer Knapsack (unbounded)

Integer Knapsack with repetitions

Subset sum

Cutting stock

Maximum subarray

Longest Increasing Subsequence

Longest Common Subsequence

Longest Common Substring

Edit distance

Sequence alignment

Single-source shortest path

All-pairs shortest path


Περαιτέρω μελέτη για το Δυναμικό Προγραμματισμό

J. Kleinberg, E. Tardos: "Algorithm Design", Addison-Wesley, 2005
Chapter 6 Dynamic Programming

Thomas Cormen, Charles Leiserson, Ronald Rivest and Cliff Stein: "Introduction to Algorithms", 3rd edition, MIT Press, 2009
Chapter 15 Dynamic Programming

S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani: "Algorithms", MacGraw-Hill, 2006
(a draft is available
here)
Chapter 6 Dynamic Programming

Jeff Edmonds, "How to Think About Algorithms", Cambridge University Press, 2008
Chapter 18 Dynamic Programming Algorithms

Bradley, Hax, and Magnanti, "Applied Mathematical Programming", Addison-Wesley, 1977
(available here)
Chapter 11 Dynamic Programming

Δες επίσης στο web

Dynamic Programming (διάλεξη του John Guttag στο MIT)

Dynamic Programming: overlapping subproblems, optimal substructure (διάλεξη του John Guttag στο MIT)


Dynamic Programming, Longest Common Subsequence (διάλεξη του Charles Leiserson στο MIT)


Dynamic Programming I: Fibonacci, Shortest Paths (διάλεξη του Erik Demaine στο MIT)

Dynamic Programming II: Text Justification, Blackjack (διάλεξη του Erik Demaine στο MIT)

Dynamic Programming III: Parenthesization, Edit Distance, Knapsack (διάλεξη του Erik Demaine στο MIT)

Dynamic Programming IV: Guitar Fingering, Tetris, Super Mario Bros. (διάλεξη του Erik Demaine στο MIT)


Dynamic Programming Practice Problems (από τον Brian Dean)


Introduction to programming contests: Dynamic Programming (από τον Jaehyun Park)


Dynamic Programming: Memoization (σημειώσεις από το πανεπιστήμιο Cornell)

Dynamic Programming:Iterative DP, LCS, LIS (σημειώσεις από το πανεπιστήμιο Cornell)

Dynamic Programming: Partition (σημειώσεις από το πανεπιστήμιο Cornell)



Τελευταία ενημέρωση στις 13/05/2013 από τον Β. Παπαδημητρίου (bpapa at otenet dot gr)