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

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

Η ουσία της μεθόδου

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

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

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

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

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

Κατασκευή του αλγορίθμου του προβλήματος

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

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

Εφαρμογή της μεθόδου

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

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

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

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

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