Στην επιστήμη των υπολογιστών, ένα πρόβλημα λέγεται ότι έχει επικαλυπτόμενα υποπροβλήματα εάν το πρόβλημα μπορεί να αναλυθεί σε υποπροβλήματα που επαναχρησιμοποιούνται πολλές φορές ή ένας αναδρομικός αλγόριθμος για το πρόβλημα λύνει το ίδιο υποπρόβλημα ξανά και ξανά αντί να δημιουργεί πάντα νέο υποπροβλήματα.
Τι είναι η βέλτιστη υποδομή και τα επικαλυπτόμενα υποπροβλήματα στον δυναμικό προγραμματισμό;
Ένα πρόβλημα έχει μια ιδιότητα βέλτιστης υποδομής εάν μπορεί να επιτευχθεί μια βέλτιστη λύση του δεδομένου προβλήματος χρησιμοποιώντας τη βέλτιστη λύση των υποπροβλημάτων του. Ο Δυναμικός Προγραμματισμός εκμεταλλεύεται αυτήν την ιδιότητα για να βρει μια λύση.
Τι είναι το επικαλυπτόμενο υποπρόβλημα στον δυναμικό προγραμματισμό;
1) Επικαλυπτόμενα υποπροβλήματα:
Ο δυναμικός προγραμματισμός χρησιμοποιείται κυρίως όταν απαιτούνται λύσεις των ίδιων υποπροβλημάτων ξανά και ξανά. Στον δυναμικό προγραμματισμό, οι υπολογισμένες λύσεις σε υποπροβλήματα αποθηκεύονται σε έναν πίνακα, έτσι ώστε να μην χρειάζεται να υπολογιστούν εκ νέου.
Ποια είναι η διαφορά μεταξύ της βέλτιστης υποδομής και των επικαλυπτόμενων υποπροβλημάτων;
Καταλαβαίνω την προσέγγιση στόχου και για τις δύο μεθόδους όπου το Optimal Substructure υπολογίζει τη βέλτιστη λύση με βάση μια είσοδο n ενώ τα επικαλυπτόμενα υποπροβλήματα στοχεύουν όλες τις λύσεις για το εύρος εισόδου, ας πούμε από 1 έως n. Για ένα πρόβλημα όπως το πρόβλημα κοπής ράβδων.
Ποια από αυτές τις τεχνικές χρησιμοποιεί επικάλυψη υποπροβλημάτων;
Ο δυναμικός προγραμματισμός είναι μια τεχνική για την επίλυση προβλημάτων με επικαλυπτόμενα υποπροβλήματα. Σε αυτό, αποθηκεύουμε το αποτέλεσμα του υποπροβλήματος που επιλύεται μία φορά για μελλοντική επαναχρησιμοποίηση. Η τεχνική αποθήκευσης λύσεων υποπροβλήματος ονομάζεται απομνημόνευση.
