Δυναμικός προγραμματισμός: Διαφορά μεταξύ των αναθεωρήσεων
Περιεχόμενο που διαγράφηκε Περιεχόμενο που προστέθηκε
Γραμμή 21:
==='''Ανάπτυξη Αλγορίθμου'''===
Η ανάπτυξη ενός αλγορίθμου δυναμικού προγραμματισμού μπορεί να αναλυθεί σε μία σειρά από
Τα
▲2. Ορίζουμε αναδρομικά την τιμή μιας βέλτιστης λύσης.
▲3. Υπολογίζουμε την τιμή μιας βέλτιστης λύσης δουλεύοντας "αναβιβαστικά" (δηλαδή από "κάτω προς τα πάνω" ή από τα "μερικά στα γενικά").
Μιλώντας για βέλτιστη υποδομή αναφερόμαστε στο ότι οι βέλτιστες λύσεις των υποπροβλημάτων αποτελούν το κλειδί για την βέλτιστη λύση του γενικότερου προβλήματος. Ο δυναμικός προγραμματισμός δεν μπορεί να εφαρμοστεί αν δε διατηρείται η αρχή της βελτιστότητας. Η πρώτη κίνηση όταν χρησιμοποιούμε τον δυναμικό προγραμματισμό, είναι η δημιουργία της αναδρομικής εξίσωσης για την εύρεση της βέλτιστης λύσης με τη χρήση της αρχής της βελτιστότητας. Αυτή δηλώνει ότι ανεξάρτητα ποια θα είναι η πρώτη απόφαση, όλες οι υπόλοιπες θα πρέπει να προσαρμοστούν και να είναι βέλτιστες σε σχέση με την κατάσταση που θα προκύψει από την πρώτη απόφαση. Αφού λυθεί η αναδρομική εξίσωση - για την τιμή της βέλτιστης λύσης -
▲4. Κατασκευάζουμε μία βέλτιστη λύση από τα δεδομένα που υπολογίστηκαν.
▲Τα 3 πρώτα βήματα είναι απαραίτητα για την επίλυση ενός προβλήματος χρησιμοποιώντας τη μέθοδο του δυναμικού προγραμματισμού. Εάν επιθυμούμε μπορούμε να συμπεριλάβουμε το 4ο βήμα και συγκεκριμένα την περίπτωση που αναζητούμε μία βέλτιστη λύση. Για να πραγματοποιηθεί αυτό, στο 3ο βήμα, οφείλουμε να κρατήσουμε παραπάνω πληροφορίες ώστε να περάσουμε στο τελευταίο βήμα, που θα επιφέρει τη βέλτιστη λύση.
▲'''Αρχή της Βελτιστότητας'''===
▲Μιλώντας για βέλτιστη υποδομή αναφερόμαστε στο ότι οι βέλτιστες λύσεις των υποπροβλημάτων αποτελούν το κλειδί για την βέλτιστη λύση του γενικότερου προβλήματος. Ο δυναμικός προγραμματισμός δεν μπορεί να εφαρμοστεί αν δε διατηρείται η αρχή της βελτιστότητας. Η πρώτη κίνηση όταν χρησιμοποιούμε τον δυναμικό προγραμματισμό, είναι η δημιουργία της αναδρομικής εξίσωσης για την εύρεση της βέλτιστης λύσης με τη χρήση της αρχής της βελτιστότητας. Αυτή δηλώνει ότι ανεξάρτητα ποια θα είναι η πρώτη απόφαση, όλες οι υπόλοιπες θα πρέπει να προσαρμοστούν και να είναι βέλτιστες σε σχέση με την κατάσταση που θα προκύψει από την πρώτη απόφαση. Αφού λυθεί η αναδρομική εξίσωση - για την τιμή της βέλτιστης λύσης - εκτελείται ένα βήμα αναγωγής όπου κατασκευάζεται η λύση.
Η αναδρομική εξίσωση του δυναμικού προγραμματισμού μπορεί ακόμα να λυθεί με επαναληπτικό κώδικα που αποφεύγει βέβαια τον επανυπολογισμό των ήδη υπολογισμένων τιμών. Ο επαναληπτικός κώδικας έχει τη ίδια χρονική πολυπλοκότητα με τον αναδρομικό κώδικα. Ο πρώτος όμως "κερδίζει" στο γεγονός ότι δεν απαιτεί επιπρόσθετο χώρο για τη στοίβα της αναδρομής. Εν κατακλείδι, ο επαναληπτικός κώδικας έχει ταχύτερη εκτέλεση σε σχέση με τον αναδρομικό κώδικα.
| |||