Πώς χρησιμοποιείται το υπόμνημα σε αλγόριθμους δυναμικού προγραμματισμού;

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

Δείτε πώς χρησιμοποιείται:

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

2. Αποθήκευση αποτελεσμάτων: Μια δομή δεδομένων, συνήθως ένας πίνακας κατακερματισμού (λεξικό στο Python) ή ένας πίνακας, χρησιμοποιείται για την αποθήκευση των αποτελεσμάτων των υποπροσωπικών. Η είσοδος στο υποπροσωπικό (π.χ. οι παράμετροι μιας αναδρομικής συνάρτησης) χρησιμεύει ως το κλειδί και το υπολογιζόμενο αποτέλεσμα είναι η τιμή.

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

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

Παράδειγμα (ακολουθία Fibonacci):

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

αφελής (αναποτελεσματική) αναδρομική λύση:

`` `Python

def fibonacci_naive (n):

Εάν n <=1:

επιστροφή n

επιστροφή fibonacci_naive (n-1) + fibonacci_naive (n-2)

`` `

Αναμετρημένη αναδρομική λύση:

`` `Python

memo ={} # Λεξικό για υπόμνημα

def fibonacci_memo (n):

Εάν n σε σημείωμα:

επιστροφή σημείωμα [n]

Εάν n <=1:

αποτέλεσμα =n

αλλού:

αποτέλεσμα =fibonacci_memo (n-1) + fibonacci_memo (n-2)

σημείωμα [n] =αποτέλεσμα

αποτέλεσμα επιστροφής

`` `

Στην αναμενόμενη έκδοση:

* `Memo` Αποθηκεύει προηγουμένως υπολογισμένα αριθμούς Fibonacci.

* Πριν κάνετε μια αναδρομική κλήση, `fibonacci_memo` ελέγχει αν το αποτέλεσμα για το` n` είναι ήδη σε `memo '.

* Εάν είναι, η αποθηκευμένη τιμή επιστρέφεται απευθείας. Διαφορετικά, το αποτέλεσμα υπολογίζεται, αποθηκεύεται σε `memo` και στη συνέχεια επιστρέφει.

Αυτή η αλλαγή μετατρέπει έναν αλγόριθμο εκθετικού χρόνου σε αλγόριθμο γραμμικού χρόνου. Το κλειδί είναι η αποφυγή των περιττών υπολογισμών των ίδιων αριθμών Fibonacci πολλές φορές.

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