Δυναμικός Προγραμματισμός — Επεξήγηση των Memoization και Tabulation

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

Τα δύο βασικά στυλ είναι το memoization και το tabulation. Το memoization αποθηκεύει απαντήσεις κατά τη διάρκεια μιας αναδρομικής λύσης. Το tabulation συμπληρώνει τις απαντήσεις με σειρά από κάτω προς τα πάνω, συνήθως με έναν πίνακα ή array.

Πότε λειτουργεί ο δυναμικός προγραμματισμός

Ο δυναμικός προγραμματισμός είναι χρήσιμος όταν ισχύουν δύο συνθήκες.

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

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

Memoization vs. tabulation

Memoization: αποθήκευση από πάνω προς τα κάτω

Το memoization ξεκινά από την αναδρομική ιδέα. Όταν ο αλγόριθμος λύνει ένα υποπρόβλημα για πρώτη φορά, αποθηκεύει το αποτέλεσμα. Οι επόμενες κλήσεις επαναχρησιμοποιούν την αποθηκευμένη τιμή αντί να την υπολογίζουν ξανά.

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

Tabulation: κατασκευή από κάτω προς τα πάνω

Το tabulation ξεκινά από τις βασικές περιπτώσεις και συμπληρώνει τις καταστάσεις με μια σειρά που καθιστά διαθέσιμες τις εξαρτήσεις όταν χρειάζονται.

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

Παράδειγμα δυναμικού προγραμματισμού: Fibonacci

Η ακολουθία Fibonacci ορίζεται από

$$F(0) = 0, \quad F(1) = 1$$

και, για $n \ge 2$,

$$F(n) = F(n-1) + F(n-2)$$

Μια απλή αναδρομική λύση επαναλαμβάνει δουλειά. Για παράδειγμα, ο υπολογισμός του $F(5)$ χρειάζεται τα $F(4)$ και $F(3)$, και έπειτα ο υπολογισμός του $F(4)$ χρειάζεται ξανά το $F(3)$. Αυτή η επαναλαμβανόμενη κλήση του $F(3)$ είναι το είδος σπατάλης που αφαιρεί ο δυναμικός προγραμματισμός.

Memoization στο Fibonacci

Με το memoization, η σχέση αναδρομής παραμένει η ίδια, αλλά κάθε τιμή αποθηκεύεται αφού υπολογιστεί για πρώτη φορά.

Για το $F(5)$, η χρήσιμη ακολουθία είναι:

• υπολόγισε και αποθήκευσε το $F(0)=0$
• υπολόγισε και αποθήκευσε το $F(1)=1$
• υπολόγισε και αποθήκευσε το $F(2)=1$
• υπολόγισε και αποθήκευσε το $F(3)=2$
• υπολόγισε και αποθήκευσε το $F(4)=3$
• υπολόγισε και αποθήκευσε το $F(5)=5$

Το βασικό σημείο είναι ότι κάθε κατάσταση υπολογίζεται μία φορά. Τα επόμενα αιτήματα διαβάζουν την αποθηκευμένη τιμή.

Tabulation στο Fibonacci

Με το tabulation, χτίζεις από τις βασικές περιπτώσεις προς τα πάνω:

$$\begin{aligned} F(0) &= 0 \\ F(1) &= 1 \\ F(2) &= F(1) + F(0) = 1 \\ F(3) &= F(2) + F(1) = 2 \\ F(4) &= F(3) + F(2) = 3 \\ F(5) &= F(4) + F(3) = 5 \end{aligned}$$

Αυτή η εκδοχή κάνει προφανή τη σειρά εξαρτήσεων: κάθε νέα τιμή χρησιμοποιεί εγγραφές που είναι ήδη γνωστές.

Γιατί ο δυναμικός προγραμματισμός μπορεί να είναι ταχύτερος

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

Η ακριβής επιτάχυνση εξαρτάται από το πρόβλημα. Ο δυναμικός προγραμματισμός δεν είναι αυτόματα γρήγορος. Βοηθά όταν η επαναλαμβανόμενη δουλειά είναι πραγματικό μέρος της αρχικής λύσης.

Συνηθισμένα λάθη στον δυναμικό προγραμματισμό

Χρήση του όταν τα υποπροβλήματα δεν αλληλεπικαλύπτονται

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

Λανθασμένος ορισμός της κατάστασης

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

Λάθος βασικές περιπτώσεις

Οι βασικές περιπτώσεις στηρίζουν όλη τη μέθοδο. Αν οι αρχικές τιμές είναι λάθος, τότε και κάθε επόμενη κατάσταση που χτίζεται από αυτές θα είναι επίσης λάθος.

Συμπλήρωση του πίνακα με λάθος σειρά

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

Η υπόθεση ότι ο δυναμικός προγραμματισμός σημαίνει πάντα βελτιστοποίηση

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

Πού χρησιμοποιείται ο δυναμικός προγραμματισμός

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

Όταν αποφασίζεις αν αξίζει να τον δοκιμάσεις, κάνε δύο ερωτήσεις:

• επαναλαμβάνονται τα μικρότερα υποπροβλήματα;
• μπορεί η μεγαλύτερη απάντηση να κατασκευαστεί από αυτές τις μικρότερες απαντήσεις;

Αν και οι δύο απαντήσεις είναι ναι, ο δυναμικός προγραμματισμός είναι πολύ καλή επιλογή.

Δοκίμασε ένα παρόμοιο πρόβλημα

Δοκίμασε τη δική σου εκδοχή με τον αριθμό των τρόπων να ανέβεις $n$ σκαλιά, αν κάθε κίνηση είναι είτε $1$ σκαλί είτε $2$ σκαλιά. Η σχέση αναδρομής είναι απλή, τα επαναλαμβανόμενα υποπροβλήματα εντοπίζονται εύκολα και είναι ένα καλό επόμενο παράδειγμα μετά το Fibonacci.