Ο δυναμικός προγραμματισμός είναι μια έννοια που αναπτύχθηκε από τον Richard Bellman, έναν μαθηματικό και οικονομολόγο.
Εκείνη την εποχή, ο Bellman έψαχνε έναν τρόπο να λύσει πολύπλοκα προβλήματα βελτιστοποίησης. Τα προβλήματα βελτιστοποίησης απαιτούν από εσάς να επιλέξετε την καλύτερη λύση από ένα σύνολο επιλογών.
Ένα παράδειγμα προβλήματος βελτιστοποίησης είναι το πρόβλημα του Ταξιδιώτη πωλητή. Ο στόχος είναι να βρεθεί η συντομότερη διαδρομή που θα επιτρέψει στον πωλητή να επισκεφτεί κάθε πόλη ακριβώς μία φορά και να επιστρέψει στην πόλη που ξεκινά.
Η προσέγγιση του Bellman σε αυτά τα προβλήματα ήταν να τα σπάσει σε μικρότερα υποπροβλήματα και να λύσει τα υποπροβλήματα από το μικρότερο στο μεγαλύτερο. Στη συνέχεια αποθήκευσε τα αποτελέσματα των υποπροβλημάτων και τα ξαναχρησιμοποίησε για να λύσει μεγαλύτερα υποπροβλήματα. Αυτή είναι η κύρια ιδέα πίσω από τον δυναμικό προγραμματισμό.
Πίνακας περιεχομένων
Τι είναι ο Δυναμικός Προγραμματισμός;
Ο δυναμικός προγραμματισμός επιλύει προβλήματα βελτιστοποίησης αναλύοντάς τα σε μικρότερα υποπροβλήματα, λύνοντας κάθε υποπρόβλημα μία φορά και αποθηκεύοντας τις λύσεις τους έτσι ώστε να μπορούν να επαναχρησιμοποιηθούν και να συνδυαστούν για να λύσουν το μεγαλύτερο πρόβλημα. Τα προβλήματα επιλύονται από το μικρότερο έως το μεγαλύτερο, επιτρέποντας την επαναχρησιμοποίηση των λύσεων.
Πώς λειτουργεί ο Δυναμικός Προγραμματισμός;
Η επίλυση ενός προβλήματος χρησιμοποιώντας δυναμικό προγραμματισμό περιλαμβάνει τα ακόλουθα βήματα:
Για να το δούμε στην πράξη, υπολογίζουμε τον 6ο αριθμό Fibonacci, F(6), χρησιμοποιώντας αυτή τη διαδικασία.
Αρχικά, ορίστε τα υποπροβλήματα που πρέπει να επιλυθούν.
F(n) = F(n-1) + F(n-2) για n > 1
Επομένως: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
Το δεύτερο βήμα περιλαμβάνει την επίλυση κάθε υποπροβλήματος χρησιμοποιώντας μια αναδρομική συνάρτηση ή μια επαναληπτική διαδικασία. Επιλύουμε τα υποπροβλήματα από το μικρότερο στο μεγαλύτερο, επαναχρησιμοποιώντας αποτελέσματα από μικρότερα υποπροβλήματα. Αυτό μας δίνει τα εξής:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Καθώς επιλύουμε καθένα από τα υποπροβλήματα, αποθηκεύουμε τις λύσεις σε έναν πίνακα ή πίνακα έτσι ώστε να μπορούν να επαναχρησιμοποιηθούν για την επίλυση μεγαλύτερων υποπροβλημάτων όπως:
Μόλις λυθούν όλα τα υποπροβλήματα, χρησιμοποιούμε τις λύσεις για να κατασκευάσουμε τη λύση στο αρχικό πρόβλημα.
Σε αυτή την περίπτωση, η λύση στο αρχικό πρόβλημα είναι ο 6ος αριθμός Fibonacci, ο οποίος βρίσκεται αθροίζοντας τα αποτελέσματα των F(5) και F(4), υποπροβλήματα που προσδιορίζονται από το μεγαλύτερο πρόβλημα. Το αποτέλεσμα μας δίνει 8.
Πού και γιατί χρησιμοποιείται ο δυναμικός προγραμματισμός;
Ο δυναμικός προγραμματισμός χρησιμοποιείται σε περιοχές όπου έχουμε προβλήματα που μπορούν να χωριστούν σε μικρότερα υποπροβλήματα και οι λύσεις τους χρησιμοποιούνται για την επίλυση μεγαλύτερων προβλημάτων.
Αυτοί οι τομείς περιλαμβάνουν την επιστήμη των υπολογιστών, τα οικονομικά, τα μαθηματικά και τη μηχανική. Στην επιστήμη των υπολογιστών, χρησιμοποιείται για την επίλυση προβλημάτων που αφορούν ακολουθίες, γραφήματα και ακέραιες τιμές και σε ανταγωνιστικό προγραμματισμό.
Στα οικονομικά, χρησιμοποιείται για την επίλυση προβλημάτων βελτιστοποίησης στη χρηματοδότηση, την παραγωγή και την κατανομή πόρων. Στα μαθηματικά, ο δυναμικός προγραμματισμός χρησιμοποιείται στη θεωρία παιγνίων, τη στατιστική και τις πιθανότητες, όπου χρησιμοποιείται για την επίλυση προβλημάτων βελτιστοποίησης.
Στη μηχανική, χρησιμοποιείται για την επίλυση προβλημάτων κατανομής πόρων, προγραμματισμού, κατασκευής, επικοινωνίας και συστημάτων ελέγχου.
Υπάρχουν πολλά πλεονεκτήματα από τη χρήση δυναμικού προγραμματισμού για την επίλυση προβλημάτων βελτιστοποίησης:
Όταν πρόκειται για την επίλυση προβλημάτων βελτιστοποίησης, ο δυναμικός προγραμματισμός είναι ένα πολύ χρήσιμο εργαλείο για τη διασφάλιση της αποτελεσματικότητας στις λύσεις.
Προσεγγίσεις που χρησιμοποιούνται στον δυναμικό προγραμματισμό
Στον δυναμικό προγραμματισμό, χρησιμοποιούνται δύο προσεγγίσεις για την επίλυση προβλημάτων βελτιστοποίησης. Αυτές είναι η προσέγγιση από πάνω προς τα κάτω και η προσέγγιση από κάτω προς τα πάνω.
Προσέγγιση από πάνω προς τα κάτω
Αυτή η προσέγγιση είναι επίσης γνωστή ως απομνημόνευση. Η απομνημόνευση είναι μια τεχνική βελτιστοποίησης που χρησιμοποιείται κυρίως για να κάνει τα προγράμματα υπολογιστών πιο γρήγορα αποθηκεύοντας τα αποτελέσματα των κλήσεων συναρτήσεων στην κρυφή μνήμη και επιστρέφοντας τα αποθηκευμένα αποτελέσματα την επόμενη φορά που θα χρειαστούν αντί για τον υπολογισμό τους ξανά.
Η προσέγγιση από πάνω προς τα κάτω περιλαμβάνει αναδρομή και προσωρινή αποθήκευση. Η αναδρομή περιλαμβάνει μια συνάρτηση που καλεί τον εαυτό της με απλούστερες εκδόσεις του προβλήματος ως όρισμα. Η αναδρομή χρησιμοποιείται για να αναλύσει το πρόβλημα σε μικρότερα υποπροβλήματα και να λύσει τα υποπροβλήματα.
Μόλις λυθεί ένα υποπρόβλημα, το αποτέλεσμά του αποθηκεύεται στην κρυφή μνήμη και χρησιμοποιείται ξανά κάθε φορά που παρουσιάζεται παρόμοιο πρόβλημα. Το από πάνω προς τα κάτω είναι εύκολο να κατανοηθεί και να εφαρμοστεί και επιλύει ένα υποπρόβλημα μόνο μία φορά. Ένα μειονέκτημά του, ωστόσο, είναι ότι καταλαμβάνει πολλή μνήμη λόγω της αναδρομής. Αυτό μπορεί να οδηγήσει σε σφάλμα υπερχείλισης στοίβας.
Προσέγγιση από κάτω προς τα πάνω
Η προσέγγιση από κάτω προς τα πάνω, γνωστή και ως πίνακας, καταργεί την αναδρομή, αντικαθιστώντας την με επανάληψη, αποφεύγοντας έτσι τα σφάλματα υπερχείλισης στοίβας.
Σε αυτή την προσέγγιση, ένα μεγάλο πρόβλημα χωρίζεται σε μικρότερα υποπροβλήματα και οι λύσεις για τα υποπροβλήματα χρησιμοποιούνται για την επίλυση του μεγαλύτερου προβλήματος.
Τα μικρότερα υποπροβλήματα επιλύονται πρώτα από το μεγαλύτερο στο μικρότερο και τα αποτελέσματά τους αποθηκεύονται σε έναν πίνακα, έναν πίνακα ή έναν πίνακα, εξ ου και η ονομασία του πίνακα.
Τα αποθηκευμένα αποτελέσματα επιλύουν μεγαλύτερα προβλήματα που εξαρτώνται από τα υποπροβλήματα. Το αποτέλεσμα του αρχικού προβλήματος βρίσκεται στη συνέχεια λύνοντας το μεγαλύτερο υποπρόβλημα χρησιμοποιώντας προηγουμένως υπολογισμένες τιμές.
Αυτή η προσέγγιση έχει το πλεονέκτημα ότι είναι αποδοτική στη μνήμη και στον χρόνο, καταργώντας την αναδρομή.
Παραδείγματα προβλημάτων που μπορούν να λυθούν με δυναμικό προγραμματισμό
Ακολουθούν ορισμένα προβλήματα προγραμματισμού που μπορούν να λυθούν χρησιμοποιώντας δυναμικό προγραμματισμό:
#1. Πρόβλημα με σακίδιο
Πηγή: Wikipedia
Το σακίδιο είναι μια τσάντα φτιαγμένη από καμβά, νάιλον ή δέρμα που συνήθως δένεται στην πλάτη και χρησιμοποιείται από στρατιώτες και πεζοπόρους για να μεταφέρουν προμήθειες.
Στο πρόβλημα του σακιδίου, σας παρουσιάζεται ένα σακίδιο και δεδομένης της χωρητικότητας του, πρέπει να επιλέξετε αντικείμενα, το καθένα με την αξία του. Η επιλογή σας πρέπει να είναι τέτοια ώστε να λαμβάνετε τη μέγιστη συνολική αξία των αντικειμένων που έχουν διαλεχθεί και το βάρος των αντικειμένων να είναι μικρότερο ή ίσο με τη χωρητικότητα του σακιδίου.
Ένα παράδειγμα του προβλήματος του σακιδίου δίνεται παρακάτω:
Φανταστείτε ότι πηγαίνετε πεζοπορία και έχετε ένα σακίδιο χωρητικότητας 15 κιλών. Έχετε μια λίστα με αντικείμενα που μπορείτε να φέρετε μαζί σας, μαζί με τις αξίες και τα βάρη τους, όπως φαίνεται στον παρακάτω πίνακα:
ItemValueWeightTent2003Sleeping bag1502Sove501Food1002Μφιάλη νερού100.5Κιτ πρώτων βοηθειών251
Επιλέξτε ένα υποσύνολο των αντικειμένων που θα φέρετε έτσι ώστε η συνολική αξία των αντικειμένων να μεγιστοποιείται ενώ το συνολικό βάρος είναι μικρότερο ή ίσο με τη χωρητικότητα του σακιδίου, που είναι 15 κιλά.
Οι πραγματικές εφαρμογές του προβλήματος του σακιδίου περιλαμβάνουν την επιλογή τίτλων που θα προστεθούν σε ένα χαρτοφυλάκιο για να ελαχιστοποιηθεί ο κίνδυνος και να μεγιστοποιηθεί το κέρδος και να βρεθούν οι λιγότερο σπάταλοι τρόποι για την περικοπή πρώτων υλών.
#2. Πρόβλημα προγραμματισμού
Ένα πρόβλημα προγραμματισμού είναι ένα πρόβλημα βελτιστοποίησης στο οποίο ο στόχος είναι η βέλτιστη ανάθεση εργασιών σε ένα σύνολο πόρων. Οι πόροι μπορεί να είναι μηχανήματα, προσωπικό ή άλλοι πόροι που χρησιμοποιούνται για την ολοκλήρωση των εργασιών.
Ένα παράδειγμα προβλήματος προγραμματισμού δίνεται παρακάτω:
Φανταστείτε ότι είστε υπεύθυνος έργου υπεύθυνος για τον προγραμματισμό ενός συνόλου εργασιών που πρέπει να ολοκληρωθούν από μια ομάδα υπαλλήλων. Κάθε εργασία έχει μια ώρα έναρξης, μια ώρα λήξης και μια λίστα εργαζομένων που είναι ικανοί να την ολοκληρώσουν.
Ακολουθεί ένας πίνακας που περιγράφει τις εργασίες και τα χαρακτηριστικά τους:
Εργασία Ώρα έναρξης Χρόνος λήξης Πιστοποιημένοι υπάλληλοιT1911A, B, CT21012A, CT31113B, CT41214A, B
Αναθέστε κάθε εργασία σε έναν υπάλληλο για να ελαχιστοποιήσετε τον συνολικό χρόνο ολοκλήρωσης.
Το πρόβλημα του προγραμματισμού μπορεί να αντιμετωπιστεί στη μεταποιητική βιομηχανία όταν προσπαθεί να βελτιστοποιήσει την κατανομή πόρων όπως μηχανές, υλικά, εργαλεία και εργασία.
Μπορεί επίσης να συναντηθεί στην υγειονομική περίθαλψη κατά τη βελτιστοποίηση της χρήσης κρεβατιών, προσωπικού και ιατρικών προμηθειών. Άλλοι κλάδοι όπου μπορεί να παρουσιαστεί αυτό το πρόβλημα είναι η διαχείριση έργων, η διαχείριση της εφοδιαστικής αλυσίδας και η εκπαίδευση.
#3. Πρόβλημα ταξιδιώτη πωλητή
Πηγή: Wikipedia
Αυτό είναι ένα από τα πιο μελετημένα προβλήματα βελτιστοποίησης που μπορούν να λυθούν χρησιμοποιώντας δυναμικό προγραμματισμό.
Το πρόβλημα του ταξιδιώτη πωλητή παρέχει μια λίστα με τις πόλεις και τις αποστάσεις μεταξύ κάθε ζεύγους πόλεων. Απαιτείται να βρείτε τη συντομότερη δυνατή διαδρομή που επισκέπτεται κάθε πόλη ακριβώς μία φορά και επιστρέφει στην πόλη προέλευσης.
Ένα παράδειγμα προβλήματος ταξιδιωτικού πωλητή δίνεται παρακάτω:
Φανταστείτε ότι είστε πωλητής που πρέπει να επισκεφτεί ένα σύνολο πόλεων στο συντομότερο δυνατό χρόνο. Έχετε μια λίστα με τις πόλεις που πρέπει να επισκεφτείτε και τις αποστάσεις μεταξύ κάθε ζεύγους πόλεων, όπως φαίνεται στον παρακάτω πίνακα:
ΠόληABCDEA010152030B100352515C153503020D202530010E301520100
Το πρόβλημα του ταξιδιώτη πωλητή μπορεί να συναντηθεί στη βιομηχανία αναψυχής όταν προσπαθείτε να σχεδιάσετε διαδρομές για τουρίστες, στην εφοδιαστική κατά τον σχεδιασμό της αποστολής αγαθών, στις μεταφορές κατά τον σχεδιασμό δρομολογίων λεωφορείων και στη βιομηχανία πωλήσεων, μεταξύ άλλων.
Σαφώς, ο δυναμικός προγραμματισμός έχει πολλές εφαρμογές πραγματικού κόσμου, κάτι που βοηθάει να μάθετε περισσότερα για αυτόν.
Εξετάστε τους ακόλουθους πόρους για να αναπτύξετε τις γνώσεις σας σχετικά με τον δυναμικό προγραμματισμό.
Πόροι
Δυναμικός Προγραμματισμός από τον Richard Bellman
Ο Δυναμικός Προγραμματισμός είναι ένα βιβλίο του Richard Bellman, ο οποίος σκέφτηκε τον δυναμικό προγραμματισμό και τον ανέπτυξε στα αρχικά του στάδια.
Το βιβλίο είναι γραμμένο με ευκολονόητο τρόπο που απαιτεί μόνο βασικές γνώσεις μαθηματικών και λογισμό για την κατανόηση του κειμένου. Στο βιβλίο, ο Bellman εισάγει τη μαθηματική θεωρία μιας διαδικασίας λήψης αποφάσεων πολλαπλών σταδίων που είναι το κλειδί στον δυναμικό προγραμματισμό.
Στη συνέχεια, το βιβλίο εξετάζει προβλήματα συμφόρησης σε διαδικασίες παραγωγής πολλαπλών σταδίων, θεωρήματα ύπαρξης και μοναδικότητας και τη βέλτιστη εξίσωση αποθέματος.
Το καλύτερο πράγμα για το βιβλίο είναι ότι ο Bellman προσφέρει παραδείγματα πολλών πολύπλοκων προβλημάτων σε τομείς όπως η εφοδιαστική, η θεωρία προγραμματισμού, η θεωρία της επικοινωνίας, τα μαθηματικά οικονομικά και οι διαδικασίες ελέγχου και δείχνει πώς ο δυναμικός προγραμματισμός μπορεί να λύσει τα προβλήματα.
Το βιβλίο είναι διαθέσιμο σε εκδόσεις Kindle, σκληρό εξώφυλλο και χαρτόδετο.
Μεταπτυχιακό Πρόγραμμα Δυναμικού Προγραμματισμού Αλγόριθμοι
Αυτό το Μεταπτυχιακό Πρόγραμμα Δυναμικού Προγραμματισμού Αλγορίθμων από την Udemy προσφέρεται από τον Apaar Kamal, μηχανικό λογισμικού στην Google, και τον Prateek Narang, ο οποίος συνεργάστηκε επίσης με την Google.
Το μάθημα έχει βελτιστοποιηθεί για να βοηθά τους μαθητές να διαπρέψουν στον ανταγωνισμό προγραμματισμού που περιλαμβάνει πολλά προβλήματα που απαιτούν δυναμικό προγραμματισμό.
Εκτός από τους ανταγωνιστές προγραμματισμού, το μάθημα είναι ιδανικό για προγραμματιστές που θέλουν να βελτιώσουν την κατανόησή τους για τους αλγόριθμους και για άτομα που προετοιμάζονται για συνεντεύξεις προγραμματισμού και διαδικτυακούς γύρους κωδικοποίησης.
Το μάθημα, που διαρκεί πάνω από 40 ώρες, καλύπτει δυναμικό προγραμματισμό σε βάθος. Το μάθημα αρχικά προσφέρει μια ανανέωση σε έννοιες όπως η αναδρομή και η οπισθοδρόμηση.
Στη συνέχεια, καλύπτει τον δυναμικό προγραμματισμό στη θεωρία παιγνίων, τις χορδές, τα δέντρα και τα γραφήματα, την εκτίμηση πινάκων, τις μάσκες δυαδικών ψηφίων, τη συνδυαστική και τις δευτερεύουσες ακολουθίες, τα προβλήματα διαμερισμάτων και τον πολυδιάστατο δυναμικό προγραμματισμό, μεταξύ πολλών άλλων εννοιών.
Βασικά στοιχεία ανταγωνιστικού προγραμματισμού, κύριοι αλγόριθμοι
Η Udemy προσφέρει ένα μάθημα Competitive Programming Essentials από τους Prateek Narang και Amal Kamaar που καλύπτει δυναμικό προγραμματισμό, μαθηματικά, θεωρία αριθμών και προηγμένες δομές δεδομένων και αλγόριθμους με τρόπο που είναι χρήσιμος και σχετικός με ανταγωνιστικούς προγραμματιστές.
Το μάθημα προσφέρει μια ανανέωση σε δομές δεδομένων και αλγόριθμους προτού βουτήξετε σε πιο σύνθετους αλγόριθμους και τεχνικές που είναι χρήσιμες στον ανταγωνιστικό προγραμματισμό.
Το μάθημα καλύπτει δυναμικό προγραμματισμό, μαθηματικά, θεωρία παιγνίων, αντιστοίχιση προτύπων, Bitmasking και μια μυριάδα προηγμένων αλγορίθμων που χρησιμοποιούνται και δοκιμάζονται σε διαγωνισμούς προγραμματισμού.
Το μάθημα Udemy χωρίζεται σε 10 ενότητες και 42 ενότητες και παρέχει πολλές ερωτήσεις πρακτικής μετά από κάθε ενότητα. Αυτό το μάθημα μπεστ σέλερ είναι απαραίτητο για όποιον ενδιαφέρεται για ανταγωνιστικό προγραμματισμό.
Τελικές Λέξεις
Ο δυναμικός προγραμματισμός είναι μια ευεργετική ικανότητα για κάθε προγραμματιστή να μάθει να βελτιώνει την επίλυση προβλημάτων του πραγματικού κόσμου. Επομένως, οι προγραμματιστές θα πρέπει να εξετάσουν το ενδεχόμενο να περάσουν από τους προτεινόμενους πόρους για να προσθέσουν αυτό το κρίσιμο εργαλείο στην εργαλειοθήκη τους.
Στη συνέχεια, μπορείτε να ελέγξετε τις γλώσσες προγραμματισμού που θα χρησιμοποιήσετε στην επιστήμη δεδομένων.