Δυναμικός προγραμματισμός, οι βασικές αρχές

Για να επιλέξετε τη βέλτιστη λύση κατά την εκτέλεση των καθηκόντων προγραμματισμού μερικές φορές απαιτείται για να ταξινομήσετε τα μεγάλα ποσά των συνδυασμών στοιχείων που φορτώνει τη μνήμη του προσωπικού υπολογιστή. Αυτές οι μέθοδοι περιλαμβάνουν, για παράδειγμα, η μέθοδος προγραμματισμού του «διαίρει και βασίλευε». Σε αυτή την περίπτωση ο αλγόριθμος παρέχει πρόβλημα διαχωρισμό σε ξεχωριστές μικρότερες δευτερεύουσες εργασίες. Η μέθοδος αυτή εφαρμόζεται μόνο σε εκείνες τις περιπτώσεις όπου μικρές δευτερεύουσες εργασίες είναι ανεξάρτητες μεταξύ τους. Για να αποφευχθεί η εκτέλεση περιττή εργασία αν αλληλοεξαρτώμενες επιμέρους εργασίες, χρησιμοποιεί δυναμική μέθοδος προγραμματισμού που προτείνονται αμερικανική R.Bellmanom στη δεκαετία του '50.

η μέθοδος

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

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

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

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

Η μέθοδος βελτιώνει την απόδοση των καθηκόντων επιλύεται μέσω των παραλλαγών, ή αναδρομή.

αλγόριθμο έργο Κτίριο

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

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

τρόπος εφαρμογής

Δυναμικός προγραμματισμός εφαρμόζεται όταν υπάρχουν δύο χαρακτηριστικά:

• βέλτιστη για δευτερεύουσες εργασίες?
• παρουσία στο πρόβλημα των επικαλυπτόμενων υποπροβλήματα.

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

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

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