Δ9.pdf

Οι διαφάνειες βασίζονται σε αυτές του ακόλουθου μαθήματος: Introduction to Algorithms (6-046J), MIT https://ocw.mit.edu/courses/electrical- engineering-and-computer-science/6-046j- introduction-to-algorithms-sma-5503-fall-2005/ Οι διαφάνειες του ανωτέρω μαθήματος δίνονται υπό την άδεια «Creative...

Οι διαφάνειες βασίζονται σε αυτές του ακόλουθου μαθήματος: Introduction to Algorithms (6-046J), MIT https://ocw.mit.edu/courses/electrical- engineering-and-computer-science/6-046j- introduction-to-algorithms-sma-5503-fall-2005/ Οι διαφάνειες του ανωτέρω μαθήματος δίνονται υπό την άδεια «Creative Commons Attribution-NonCommercial-ShareAlike 3.0»  Δυναμικός Προγραμματισμός Τεχνική Σχεδιασμού, όπως η διαίρει και βασίλευε. Το πρόβλημα της κοπής ράβδου Το πρόβληµα της κοπής ράβδου: Είσοδος: ράβδος µήκους n ιντσών και ένας πίνακας τιµών pi για i = 1, 2,... , n Ζητείται να προσδιορίσουµε το µέγιστο έσοδο rn αν κόψουμε τη ράβδο και πουλήσουμε τα διάϕορα κοµµάτια Το πρόβλημα της κοπής ράβδου Γενικότερα, µπορούµε να εκϕράσουµε τις τιµές rn για n ≥ 1 συναρτήσει βέλτιστων εσόδων από µικρότερες ράβδους: rn = max (pn, r1 + rn−1, r2 + rn−2,... , rn−1 + r1). Ισοδύναμα: rn = max (pi + rn-i) 1≤i≤n Αναδροµική καταβιβαστική υλοποίηση T (n) = 2n Δένδρο αναδρομής Βέλτιστη κοπή ράβδου µέσω δυναµικού προγραµµατισµού Βέλτιστη κοπή ράβδου µέσω δυναµικού προγραµµατισµού Το γράϕηµα υποπροβληµάτων για το πρόβληµα της κοπής ράβδου µε n=4  Ανακατασκευή λύσης Η βέλτιστη κοπή και κέρδος για το αρχικό παράδειγμα:  Δυναμικός Προγραμματισμός Τεχνική Σχεδιασμού, όπως η διαίρει και βασίλευε. Παράδειγμα: Μακρύτερη Κοινή Υπακολουθία (ΜΚΥ) Δοθεισών δύο ακολουθιών x[1.. m] και y[1.. n], βρες μία μακρύτερη υπακολουθία κοινή και στις δύο ακολουθίες.  Δυναμικός Προγραμματισμός Τεχνική Σχεδιασμού, όπως η διαίρει και βασίλευε. Παράδειγμα: Μακρύτερη Κοινή Υπακολουθία (ΜΚΥ) Δοθεισών δύο ακολουθιών x[1.. m] και y[1.. n], βρες μία μακρύτερη υπακολουθία κοινή και στις δύο ακολουθίες. “μία” και όχι “τη” x: A B C B D A B y: B D C A B A  Δυναμικός Προγραμματισμός Τεχνική Σχεδιασμού, όπως η διαίρει και βασίλευε. Παράδειγμα: Μακρύτερη Κοινή Υπακολουθία (ΜΚΥ) Δοθεισών δύο ακολουθιών x[1.. m] και y[1.. n], βρες μία μακρύτερη υπακολουθία κοινή και στις δύο ακολουθίες. “μία” και όχι “τη” x: A B C B D A B BCBA = ΜΚΥ(x, y) y: B D C A B A  Ο ΜΚΥ αλγόριθμος – Προφανής αλγόριθμος Έλεγξε κάθε υποακολουθία της x[1.. m] για να δεις αν είναι επίσης υπακολουθία της y[1.. n]. Ανάλυση 2m υπακολουθίες της x (κάθε διάνυσμα διφύων μήκους m προσδιορίζει μία διαφορετική υπακολουθία της x). Άρα εκθετικός ο χρόνος εκτέλεσης.  Προς ένα καλύτερο αλγόριθμο Απλοποίηση: 1. Εστιάζουμε στον υπολογισμό του μήκους της μακρύτερης κοινής υπακολουθίας. 2. Επεκτείνουμε τον αλγόριθμο για να βρούμε την ΜΚΥ. Συμβολισμός: Συμβολίζουμε το μήκος της ακολουθίας s με | s |. Στρατηγική: Θεωρούμε τα προθέματα των x και y. Ορίζουμε c[i, j] = | ΜΚΥ(x[1.. i], y[1.. j]) |. Τότε, c[m, n] = | ΜΚΥ(x, y) |.  Αναδρομική διατύπωση Θεώρημα. c[i–1, j–1] + 1 αν x[i] = y[j], c[i, j] = max{c[i–1, j], c[i, j–1]} αλλιώς. Proof. Περίπτωση x[i] = y[ j]: 1 2 i m x: 1 2 = j n y: Αν z[1.. k] = ΜΚΥ(x[1.. i], y[1.. j]), όπου c[i, j] = k. Τότε, z[k] = x[i]=y[j], αλλιώς το z μπορεί να επεκταθεί. Έτσι, η z[1.. k–1] είναι ΚΥ των x[1.. i–1] and y[1.. j–1].  Απόδειξη (συν.) Ισχυρισμός: z[1.. k–1] = ΜΚΥ(x[1.. i–1], y[1.. j– 1]). Υποθέτουμε ότι η w είναι μακρύτερη κοινή υπακολουθία των x[1.. i–1] και y[1.. j–1], δηλ., | w | > k–1. Τότε, αποκοπή και επικόλληση : w || z[k] (w ακολουθούμενη από τη z[k]) είναι μία κοινή υπακολουθία των x[1.. i] και y[1.. j] με | w || z[k] | > k. Άτοπο, αποδεικνύοντας τον ισχυρισμό.  Απόδειξη (συν.) Ισχυρισμός: z[1.. k–1] = LCS(x[1.. i–1], y[1.. j–1]). Υποθέτουμε ότι η w είναι μακρύτερη κοινή υπακολουθία των x[1.. i–1] και y[1.. j–1], δηλ., | w | > k–1. Τότε, αποκοπή και επικόλληση : w || z[k] (w ακολουθούμενη από τη z[k]) είναι μία κοινή υπακολουθία των x[1.. i] και y[1.. j] με | w || z[k] | > k. Άτοπο, αποδεικνύοντας τον ισχυρισμό. Έτσι, c[i–1, j–1] = k–1 που σημαίνει ότι c[i, j] = c[i–1, j–1] + 1. Οι άλλες περιπτώσεις είναι παρόμοιες. 1η Βασική Προϋπόθεση για την Εφαρμογή του Δυναμικού Προγραμματισμού Βέλτιστη Υποδομή Μία βέλτιστη λύση σε ένα πρόβλημα (στιγμιότυπο) περιέχει βέλτιστες λύσεις σε υποπροβλήματα.  1η Βασική Προϋπόθεση εφαρμογής Δυναμικού Προγραμματισμού Βέλτιστη Υποδομή Μία βέλτιστη λύση σε ένα πρόβλημα (στιγμιότυπο) περιέχει βέλτιστες λύσεις σε υποπροβλήματα. Αν z = ΜΚΥ(x, y), τότε οποιοδήποτε πρόθεμα της z είναι μία ΜΚΥ ενός προθέματος της x και ενός προθέματος της y.  Αναδρομικός αλγόριθμος για ΜΚΥ ΜΚΥ(x, y, i, j) if x[i] = y[ j] then c[i, j]  ΜΚΥ(x, y, i–1, j–1) + 1 else c[i, j]  max{ΜΚΥ(x, y, i–1, j), ΜΚΥ(x, y, i, j–1)} Χειρότερη περίπτωση: x[i]  y[ j]. Σε αυτή την περίπτωση, ο αλγόριθμος εκτελείται σε δύο υποπροβλήματα στα οποία μόνο μία παράμετρος ελαττώνεται.  Δένδρο Αναδρομής m = 3, n = 4: 3,4 2,4 3,3 1,4 2,3 2,3 3,2 1,3 2,2 1,3 2,2  Δένδρο Αναδρομής m = 3, n = 4: 3,4 2,4 3,3 1,4 2,3 2,3 3,2 m+n 1,3 2,2 1,3 2,2 Ύψος = m + n  Εκθετικός χρόνος δυνητικά  Δένδρο Αναδρομής m = 3, n = 4: 3,4 2,,4 Ίδιο 3,3 υποπρόβλημα 1,4, 2,3 2,3 3,2 m+n 1,3 2,,2 1,3 2,2 Ύψος = m + n  ο χρόνος δυνητικά εκθετικός. Αλλά, επιλύουμε συχνά υποπροβλήματα που ήδη έχουν λυθεί.  2η Βασική Προϋπόθεση για την Εφαρμογή του Δυναμικού Προγραμματισμού Επικαλυπτόμενα Προβλήματα Μία αναδρομική λύση περιέχει ένα “μικρό” αριθμό διαφορετικών υποπροβλημάτων που επαναλαμβάνονται πολλές φορές. Το πλήθος των διαφορετικών υποπροβλημάτων στο πρόβλημα ΜΚΥ για δύο συμβολοσειρές μήκους m και n είναι μόνο mn.  Αλγόριθμος με Υπομνηματισμό Υπομνηματισμός: Μετά από τον υπολογισμό μίας λύσης σε ένα υποπρόβλημα, αποθήκευσε την στο πίνακα. Στις επόμενες κλήσεις, έλεγξε το πίνακα για να αποφύγεις να επιλύσεις το ίδιο υποπρόβλημα. LCS(x, y, i, j) if c[i, j] = NIL then if x[i] = y[j] Ίδιο then c[i, j]  LCS(x, y, i–1, j–1) + 1 όπως else c[i, j]  max{LCS(x, y, i–1, j), πριν LCS(x, y, i, j–1)} else return c[i, j] Χρόνος = (mn) = σταθερό έργο ανά στοιχείο πίνακα. Χώρος = (mn).  Αλγόριθμος με Υπομνηματισμό Ιδέα: Υπολόγισε τον πίνακα από πάνω προς τα κάτω. Χρόνος = (mn). Ανακατασκεύασε την ΜΚΥ με ανίχνευση προς τα πίσω. Χώρος= (mn). Βέλτιστος Πολλαπλασιασμός Πινάκων Δίνεται μία ακολουθία πινάκων: Α0,Α1,...,Αn-1, να βρεθεί ο πιο γρήγορος τρόπος υπολογισμού τοy γινομένου: Α0·Α1· · ·Αn-1. Εάν ο Αi είναι di di+1, οπότε το κόστος του γινομένου Αi·Αi+1 είναι di·di+1·di+2 γιατί: d i2  di     d i 1 d i 1 Π.χ., για τρεις πίνακες διαστάσεων 54, 46, 62 έχουμε δύο διαφορετικούς τρόπους τοποθετήσεως των παρενθέσεων: Α0·(Α1· Α2 ) κόστους 4 ·6 ·2+ 5 ·4 ·2=88 (Α0·Α1)· Α2 κόστους 5 ·4 ·6+ 5 ·6 ·2=180  Αλγόριθμος brute force: – Θα εξετάσουμε όλες τις δυνατές τοποθετήσεις – Υπάρχουν n-1 θέσεις για να τοποθετήσουμε τις παρενθέσεις: (Α0·Α1· · ·Αk-1)·(ΑkΑk+1· · ·Αn-1) – Το πλήθος των πιθανών τρόπων πολλαπλασιασμού: Π(n)=Σ1kn Π(k)·Π(n-k) Λύση: C(n-1)=Ω(4n/n1.5) 1  2n  C ( n)    n 1  n   Η σωστή αντιμετώπιση: Έστω Αi,j= Αi·Αi+1· · ·Αj, με κόστος Μi,j. Τότε: Α0,n-1 = Α0,k-1·Αk,n-1 και: Μ0,n-1 = Μ0,k-1 + Mk,n-1+ d0·dk·dn Γενικό βήμα: Εύρεση του βέλτιστου k, αναδρομικά, αποθηκεύοντας τα ενδιάμεσα αποτελέσματα. Επίλυση του Αi,j με κόστος mini