Τι είναι ο δυναμικός προγραμματισμός;

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

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

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