L14 · Δυναμικός Προγραμματισμός I — Memoization & Σταθμισμένος Χρονοπρογραμματισμός

Τι θα δούμε

Ξεκινά το τελευταίο μεγάλο κεφάλαιο: ο δυναμικός προγραμματισμός (dynamic programming, DP). Είναι το πιο εξεταζόμενο κομμάτι της ύλης — και αυτό που οι φοιτητές βρίσκουν πιο «μαγικό». Στόχος αυτής της διάλεξης: να πάψει να είναι μαγικό.

Θα δούμε την ιδέα μέσα από το απλούστερο παράδειγμα (Fibonacci), μετά το πρώτο «πραγματικό» πρόβλημα (σταθμισμένος χρονοπρογραμματισμός διαστημάτων), και θα κωδικοποιήσουμε μια συνταγή 4 βημάτων που εφαρμόζεται σε κάθε DP πρόβλημα.

Τα τρία αλγοριθμικά μοντέλα

Το παράδειγμα-εκκίνηση: Fibonacci

Η ακολουθία Fibonacci ορίζεται αναδρομικά:

$F(n)=F(n-1)+F(n-2),F(0)=0,F(1)=1.$

Η απευθείας μεταφορά σε κώδικα είναι κομψή — και καταστροφική:

Γιατί είναι τόσο αργό; Επικάλυψη υποπροβλημάτων

Ο κώδικας είναι σωστός — γιατί όμως είναι τόσο αργός; Αντί να το συμπεράνουμε, ας παρακολουθήσουμε τι κάνει στ' αλήθεια η fib. Κάθε κλήση fib(k) γεννά δύο νέες, τις fib(k−1) και fib(k−2)· αυτές γεννούν άλλες δύο η καθεμιά, και ούτω καθεξής. Όλες μαζί σχηματίζουν ένα δέντρο αναδρομής — κι εκεί κρύβεται το πρόβλημα.

Σύρε το n (κράτησέ το για τώρα στο «Αφελής») και πρόσεξε δύο πράγματα:

• Το δέντρο σχεδόν διπλασιάζεται σε κάθε επιπλέον επίπεδο. Ο μετρητής κλήσεων δεν ανεβαίνει γραμμικά — εκτοξεύεται, περίπου σαν $2^n$. Ο πίνακας στο τέλος δείχνει πού φτάνει αυτό: το fib(30) θέλει πάνω από δύο εκατομμύρια κλήσεις.
• Πάτησε σε έναν κόμβο — π.χ. σε ένα fib(2). Φωτίζονται όλες οι άλλες κλήσεις του ίδιου fib(2) στο δέντρο. Είναι πολλές· και η καθεμιά ξαναϋπολογίζει από την αρχή ακριβώς την ίδια τιμή.

Αυτό το δεύτερο είναι η ρίζα του κακού, και έχει όνομα: επικάλυψη υποπροβλημάτων (overlapping subproblems). Το ίδιο υποπρόβλημα — «πόσο κάνει το fib(2);» — ξαναεμφανίζεται αμέτρητες φορές μέσα στην αναδρομή. Ο αφελής αλγόριθμος δεν είναι αργός επειδή έχει δύσκολη δουλειά· είναι αργός επειδή κάνει την ίδια εύκολη δουλειά ξανά και ξανά.

Η λύση: memoization

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

Γύρνα τώρα στο interactive παραπάνω και πάτα το κουμπί «Memoized». Ίδιο n, ίδιο πρόβλημα — αλλά το δέντρο καταρρέει: κάθε fib(k) υπολογίζεται μία μόνο φορά, και κάθε επόμενη φορά που ζητείται επιστρέφεται έτοιμο από τον πίνακα (ο πράσινος κόμβος «cache hit», χωρίς υποδέντρο από κάτω). Ο μετρητής κλήσεων πέφτει από εκθετικός σε γραμμικό.

Στην πράξη το ίδιο αποτέλεσμα το πετυχαίνουμε ακόμα πιο καθαρά — χωρίς καθόλου αναδρομή. Γεμίζουμε έναν πίνακα από κάτω προς τα πάνω (bottom-up): πρώτα τις βασικές περιπτώσεις, και μετά κάθε επόμενο όρο από τους δύο προηγούμενους.

Κάθε $F(k)$ υπολογίζεται ακριβώς μία φορά. Η πολυπλοκότητα πέφτει από εκθετική $O(2^n)$ σε γραμμική $O(n)$ — αλλάζοντας μόνο πού αποθηκεύεις τα ενδιάμεσα αποτελέσματα.

Σταθμισμένος χρονοπρογραμματισμός διαστημάτων

Τώρα το πρώτο πραγματικό πρόβλημα. Είναι το πρόβλημα του L11 — με μία προσθήκη.

Είσοδος: $n$ αιτήματα. Το αίτημα $j$ ξεκινά τη στιγμή $s_j$, τελειώνει τη στιγμή $f_j$, και έχει βαρύτητα $v_j$. Δύο αιτήματα είναι συμβατά αν δεν επικαλύπτονται.

Στόχος: υποσύνολο $S$ ανά δύο συμβατών αιτημάτων με μέγιστο άθροισμα βαρυτήτων ${\sum }_{i\in S}{v}_i$.

Γιατί δεν αρκεί ο άπληστος

Στο L11, όταν όλες οι βαρύτητες ήταν ίσες με $1$, το άπληστο κριτήριο «μικρότερος χρόνος λήξης» έδινε αποδεδειγμένα βέλτιστη λύση. Το ένστικτο λέει πως κάποιο άπληστο κριτήριο θα δουλεύει και τώρα που οι εργασίες έχουν βαρύτητες. Δοκίμασε τα δύο πιο φυσικά — και δες τα να αποτυγχάνουν:

Στο πρώτο στιγμιότυπο, μια φθηνή εργασία που τυχαίνει να τελειώνει πρώτη μπλοκάρει μια εργασία που αξίζει $100$. Στο δεύτερο, μια ακριβή εργασία μπλοκάρει δύο φθηνότερες που μαζί την ξεπερνούν. Το πρόβλημα είναι βαθύ: η σωστή απόφαση για μια εργασία εξαρτάται από όλες τις υπόλοιπες, ενώ ο άπληστος κοιτάζει μόνο μία τη φορά.

Η προετοιμασία: ταξινόμηση και $p(j)$

Πριν στήσουμε την αναδρομή, χρειαζόμαστε δύο προετοιμασίες.

Πρώτη: ταξινόμηση. Διατάσσουμε τα αιτήματα κατά χρόνο λήξης, ώστε $f_1\le f_2\le \cdots \le f_n$. Από εδώ και πέρα, «αίτημα $j$» σημαίνει «το $j$-οστό αίτημα που τελειώνει».

Δεύτερη: η ποσότητα $p(j)$. Φαντάσου ότι αποφασίζεις να βάλεις το αίτημα $j$ στη λύση σου. Αμέσως αποκλείεις κάθε προηγούμενο αίτημα που επικαλύπτεται μαζί του. Το ερώτημα είναι: ποιο είναι το τελευταίο προηγούμενο αίτημα που σου μένει ακόμα διαθέσιμο; Αυτό ακριβώς ονομάζουμε $p(j)$.

Ένα χρήσιμο γεγονός: επειδή τα αιτήματα είναι ταξινομημένα κατά λήξη, τα συμβατά με το $j$ είναι πάντα ένα αρχικό κομμάτι $1,\dots ,p(j)$ — κι όλα τα ενδιάμεσα $p(j)+1,\dots ,j-1$ το επικαλύπτουν. Διάλεξε ένα αίτημα παρακάτω και δες ποιο είναι το $p(j)$ του και ποια αιτήματα αποκλείει:

Η αναδρομή — μια δυαδική επιλογή

Ορίζουμε $\text{OPT}(j)$ = η τιμή της βέλτιστης λύσης για τα αιτήματα $\{1,2,\dots ,j\}$. Κοιτάμε το αίτημα $j$ και ρωτάμε: μέσα ή έξω;

• Το $j$ είναι ΜΕΣΑ. Τότε αποκλείονται όλα τα ασύμβατα με το $j$ — τα $\{p(j)+1,\dots ,j-1\}$. Ό,τι μένει είναι η βέλτιστη λύση για τα $\{1,\dots ,p(j)\}$. Συνεισφορά: $v_j+\text{OPT}(p(j))$.
• Το $j$ είναι ΕΞΩ. Τότε η βέλτιστη λύση είναι ακριβώς η βέλτιστη για τα $\{1,\dots ,j-1\}$. Συνεισφορά: $\text{OPT}(j-1)$.

Δεν ξέρουμε ποια περίπτωση ισχύει — οπότε παίρνουμε τη μεγαλύτερη:

Δες την αναδρομή να γεμίζει τον πίνακα. Σε κάθε βήμα φαίνονται οι δύο υποψήφιες τιμές — «το $j$ μέσα» και «το $j$ έξω» — και ποια κερδίζει:

Ο αλγόριθμος

Η απευθείας αναδρομή είναι εκθετική — ακριβώς όπως ο αφελής Fibonacci, το πλήθος κλήσεων μεγαλώνει σαν $T(n)=T(n-1)+T(n-2)$. Η θεραπεία είναι η ίδια: απομνημόνευση.

Ισοδύναμα, top-down με memoization — η αναδρομή λύνει κάθε υποπρόβλημα, αλλά το αποθηκεύει:

Υπολογισμός των $p(j)$ σε $O(n)$

Είπαμε πως όλα τα $p(j)$ βγαίνουν σε $O(n)$. Δεν είναι προφανές: ο απλός τρόπος — για κάθε $j$, ψάξε προς τα πίσω για το τελευταίο συμβατό αίτημα — κάνει $O(n^2)$ δουλειά. Πώς πέφτουμε στο $O(n)$;

Το κόλπο: έχουμε δύο ταξινομημένες ακολουθίες — τους χρόνους λήξης και τους χρόνους έναρξης — και τις συγχωνεύουμε, ακριβώς όπως το merge της συγχωνευτικής ταξινόμησης (L03). Δύο δείκτες, ο $i$ πάνω στις λήξεις και ο $j$ πάνω στις ενάρξεις, σαρώνουν τις ακολουθίες από μία φορά:

• Αν η τρέχουσα λήξη $f_i$ είναι $\le$ από την τρέχουσα έναρξη $s_j$, τότε το αίτημα $i$ προλαβαίνει να τελειώσει — είναι έγκυρος προκάτοχος. Προχωράμε τον $i$.
• Αλλιώς, η λήξη $f_i$ έρχεται πολύ αργά. Άρα ο τελευταίος που πρόλαβε ήταν ο $i-1$: θέτουμε $p(j)=i-1$ και προχωράμε τον $j$.

Κάθε βήμα προχωρά έναν από τους δύο δείκτες κατά ένα, και κανένας δεν ξεπερνά το $n$ — άρα το πολύ $2n$ βήματα συνολικά. Δες τη σάρωση να τρέχει βήμα-βήμα — στο interactive κάθε έναρξη δείχνει σε ποιο αίτημα ανήκει, ώστε το $p$ να καταγράφεται στο σωστό:

Εύρεση της λύσης

Ο αλγόριθμος υπολογίζει τη μέγιστη τιμή. Για να βρούμε ποια αιτήματα την πετυχαίνουν, κάνουμε ένα πέρασμα προς τα πίσω — σε κάθε $j$ ρωτάμε «ποια από τις δύο περιπτώσεις κέρδισε;»

Η συνταγή του δυναμικού προγραμματισμού

Κάθε πρόβλημα DP — όσα θα δούμε στα L15–L17 — λύνεται με τα ίδια 4 βήματα:

Κλείδωσε τη γνώση

Βάλε στη σειρά τα βήματα του DP για τον σταθμισμένο χρονοπρογραμματισμό:

Και συμπλήρωσε τα κενά:

Μοτίβο σκέψης