Βασικά δυναμικά προγραμματισμού


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις Infosys MAQ
Δυναμικός προγραμματισμός Θεωρία

Στα βασικά στοιχεία του Δυναμικού Προγραμματισμού, θα καλύψουμε τα βασικά του DP και τις διαφορές του από την Άπληστη μέθοδο, Διαίρεση και Κατακράτηση και Επανάληψη.

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

Χρησιμοποιείται για τη βελτιστοποίηση προγραμμάτων. Καθώς χρησιμοποιεί τα προηγούμενα υπολογισμένα αποτελέσματα, η χρήση της εκθετικής πολυπλοκότητας του χρόνου μπορεί να μειωθεί σε πολυώνυμο. Για παράδειγμα - Η χρονική πολυπλοκότητα της αναδρομικής λύσης των Ugly Numbers είναι εκθετική και της λύσης DP είναι γραμμική.

Μερικά βασικά προβλήματα της DP

  • Άσχημο πρόβλημα αριθμών
  • Αλλαγή νομισμάτων
  • Αριθμοί Fibonacci
  • Πρόβλημα αριθμών κουδουνιών
  • Πύργος του Ανόι
  • Αριθμοί κουδουνιών
  • Πρόβλημα σακιδίων

Δυναμικός προγραμματισμός (DP) έναντι άπληστης μεθόδου

Στο DP κάθε βήμα αξιολογεί τη λύση λαμβάνοντας υπόψη τις τρέχουσες καθώς και τις προηγούμενες λύσεις για να αποκτήσει τη βέλτιστη λύση. Ωστόσο, στον άπληστο αλγόριθμο, επιλέγουμε την καλύτερη επιλογή λαμβάνοντας υπόψη μόνο την τρέχουσα κατάσταση.

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

Δυναμικός προγραμματισμός (DP) έναντι μεθόδου Divide & Conquer

Διαιρώντας και κατακτώντας χωρίζουμε ένα πρόβλημα σε υποπροβλήματα και επιλύουμε κάθε υποπρόβλημα ανεξάρτητα. Ωστόσο, στο DP αντί να επιλύουμε προβλήματα ανεξάρτητα, χρησιμοποιούμε τα αποτελέσματα που αποκτήθηκαν προηγουμένως για νέους υπολογισμούς. Με άλλα λόγια, μπορούμε να πούμε Divide and Conquer + Memoization = δυναμική προσέγγιση από πάνω προς τα κάτω.

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

Δυναμικός προγραμματισμός (DP) έναντι μεθόδου αναδρομής

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

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

Σε αυτό το άρθρο, καλύψαμε περίπου Δυναμικός προγραμματισμός βασικά. Στα επόμενα άρθρα, θα καλύψουμε ορισμένα βασικά προβλήματα στο DP.

Αναφορά συνέντευξη ερωτήσεις