Σε αυτό το σεμινάριο, θα μάθετε τι είναι ο δυναμικός προγραμματισμός. Επίσης, θα βρείτε τη σύγκριση μεταξύ δυναμικού προγραμματισμού και άπληστων αλγορίθμων για την επίλυση προβλημάτων.
Ο δυναμικός προγραμματισμός είναι μια τεχνική στον προγραμματισμό υπολογιστών που βοηθά στην αποτελεσματική επίλυση μιας κατηγορίας προβλημάτων που έχουν επικαλυπτόμενα υποπρογράμματα και βέλτιστη ιδιότητα υποδομής.
Τέτοια προβλήματα περιλαμβάνουν τον επαναλαμβανόμενο υπολογισμό της αξίας των ίδιων υποπροβλημάτων για την εξεύρεση της βέλτιστης λύσης.
Παράδειγμα δυναμικού προγραμματισμού
Πάρτε την περίπτωση δημιουργίας της ακολουθίας ινών.
Εάν η ακολουθία είναι F (1) F (2) F (3)… F (50), ακολουθεί τον κανόνα F (n) = F (n-1) + F (n-2)
F (50) = F (49) + F (48) F (49) = F (48) + F (47) F (48) = F (47) + F (46)…
Παρατηρήστε πώς υπάρχουν επικαλυπτόμενα υποπροβλήματα, πρέπει να υπολογίσουμε το F (48) για να υπολογίσουμε και τα F (50) και F (49). Αυτό είναι ακριβώς το είδος του αλγορίθμου όπου ο δυναμικός προγραμματισμός λάμπει.
Πώς λειτουργεί ο Δυναμικός Προγραμματισμός
Ο δυναμικός προγραμματισμός λειτουργεί αποθηκεύοντας το αποτέλεσμα των υποπροβλημάτων έτσι ώστε όταν απαιτούνται οι λύσεις τους, να είναι κοντά και δεν χρειάζεται να τα υπολογίσουμε ξανά.
Αυτή η τεχνική αποθήκευσης της αξίας των υποπροβλημάτων ονομάζεται απομνημόνευση. Αποθηκεύοντας τις τιμές στον πίνακα, εξοικονομούμε χρόνο για υπολογισμούς των υπο-προβλημάτων που έχουμε ήδη συναντήσει.
var m = χάρτης (0 → 0, 1 → 1) συνάρτηση fib (n) εάν το κλειδί n δεν βρίσκεται στον χάρτη mm (n) = fib (n - 1) + fib (n - 2) επιστροφή m (n)
Ο δυναμικός προγραμματισμός με απομνημόνευση είναι μια προσέγγιση από πάνω προς τα κάτω στον δυναμικό προγραμματισμό. Αντιστρέφοντας την κατεύθυνση με την οποία λειτουργεί ο αλγόριθμος, δηλαδή ξεκινώντας από τη βασική θήκη και εργαζόμαστε προς τη λύση, μπορούμε επίσης να εφαρμόσουμε δυναμικό προγραμματισμό από κάτω προς τα πάνω.
συνάρτηση fib (n) εάν n = 0 επιστροφή 0 άλλο var prevFib = 0, currFib = 1 επανάληψη n - 1 φορές var newFib = prevFib + currFib prevFib = currFib currFib = newFib current currentFib
Επανάληψη έναντι Δυναμικού Προγραμματισμού
Ο δυναμικός προγραμματισμός εφαρμόζεται κυρίως σε αναδρομικούς αλγόριθμους. Αυτό δεν είναι σύμπτωση, τα περισσότερα προβλήματα βελτιστοποίησης απαιτούν επανάληψη και ο δυναμικός προγραμματισμός χρησιμοποιείται για βελτιστοποίηση.
Όμως δεν μπορούν όλα τα προβλήματα που χρησιμοποιούν αναδρομή να χρησιμοποιούν δυναμικό προγραμματισμό. Εκτός αν υπάρχει παρουσία επικαλυπτόμενων υποπροβλημάτων όπως στο πρόβλημα της αλληλουχίας fibonacci, μια αναδρομή μπορεί να φτάσει μόνο στη λύση χρησιμοποιώντας μια προσέγγιση διαίρεσης και κατάκτησης.
Αυτός είναι ο λόγος για τον οποίο ένας αναδρομικός αλγόριθμος όπως το Merge Sort δεν μπορεί να χρησιμοποιήσει τον Δυναμικό Προγραμματισμό, επειδή τα υποπροβλήματα δεν αλληλεπικαλύπτονται με κανέναν τρόπο.
Άπληστοι Αλγόριθμοι έναντι Δυναμικού Προγραμματισμού
Οι άπληστοι αλγόριθμοι είναι παρόμοιοι με τον δυναμικό προγραμματισμό με την έννοια ότι είναι και τα δύο εργαλεία βελτιστοποίησης.
Ωστόσο, οι άπληστοι αλγόριθμοι αναζητούν τοπικά βέλτιστες λύσεις ή με άλλα λόγια, μια άπληστη επιλογή, με την ελπίδα να βρουν ένα παγκόσμιο βέλτιστο. Ως εκ τούτου, οι άπληστοι αλγόριθμοι μπορούν να κάνουν μια εικασία που φαίνεται βέλτιστη εκείνη τη στιγμή, αλλά γίνεται δαπανηρή και δεν εγγυάται μια βέλτιστη παγκοσμίως.
Ο δυναμικός προγραμματισμός, από την άλλη πλευρά, βρίσκει τη βέλτιστη λύση σε υποπροβλήματα και στη συνέχεια κάνει μια ενημερωμένη επιλογή για να συνδυάσει τα αποτελέσματα αυτών των υποπροβλημάτων για να βρει την βέλτιστη λύση.
