Δυναμικός προγραμματισμός ονομάζεται η τεχνική στον προγραμματισμό όπου για να λύσει κανείς ένα πρόβλημα λύνει προηγουμένως πολλά μικρότερα υποπροβλήματα, των οποίων τα αποτελέσματα αποθηκεύει (ώστε να μη χρειαστεί να τα ξαναυπολογίσει) και τα χρησιμοποιεί συνήθως πολλές φορές το καθένα.
Μια πρώτη γεύση αυτής της τεχνικής πήραμε όταν μετατρέψαμε την αναδρομική συνάρτηση για τον υπολογισμό της ακολουθίας Fibonacci (η οποία είχαμε παρατηρήσει ότι υπολογίζει ξανά και ξανά τους ίδιους αριθμούς Fibonacci) ώστε (α) να αποθηκεύει κάθε αριθμό Fibonacci που μόλις έχει υπολογίσει και (β) πριν πάει να υπολογίσει ένα αριθμό Fibonacci να ελέγχει αν υπάρχει ήδη κάπου υπολογισμένος και να τον χρησιμοποιεί αν υπάρχει. Δείτε εδώ, <<Αποθήκευση ενδιάμεσων αποτελεσμάτων αντί για επανυπολογισμό>>.
Αν είναι \(A,B\) δύο πίνακες διαστάσεων \(m \times n\) και \(n \times k\) αντίστοιχα τότε ορίζεται, όπως ξέρουμε, το γινόμενό τους \[ C = A B, \] είναι ένας πίνακας διαστάσεων \(m \times k\) και τα στοιχεία του πίνακα αυτού υπολογίζονται από τον τύπο \[ C_{ij} = \sum_{r=1}^n A_{ir} B_{rj},\ \ \ \ i=1,2,\ldots,m,\ j=1,2,\ldots,k. \] Εύκολα φαίνεται ότι το παραπάνω άθροισμα θέλει χρόνο της τάξης του \(n\) για να υπολογιστεί (\(n\) πολλαπλασιασμοί και \(n-1\) προσθέσεις), και αφού το πλήθος των \(C_{ij}\) είναι \(m\cdot k\) ο συνολικός χρόνος υπολογισμού είναι \(m\cdot n\cdot k\).
Ο πολλαπλασιασμός πινάκων δεν είναι αντιμεταθετική πράξη (εν γένει \(AB \neq BA\)), είναι όμως προσεταιριστική. Αυτό σημαίνει ότι \[ A(BC) = (AB)C. \] (Δοκιμάστε να το αποδείξετε αυτό, δεν είναι δύσκολο.) Συνέπεια της προσεταιριστικότητας της πράξης είναι ότι μπορούμε να μιλάμε για το γινόμενο τριων πινάκων \(ABC\) χωρίς να προσδιορίζουμε το με ποιον από τους παραπάνω δύο τρόπους το εννοούμε. Ομοίως μπορούμε να μιλάμε για γινόμενο πολλών πινάκων, το οποίο είναι κι αυτό καλώς ορισμένο ακριβώς λόγωτης προσεταιριστικότητας της πράξης.
Ακόμη όμως και για μόνο τρεις πίνακες, ενώ έχουμε βεβαίως \(A(BC) = (AB)C\), και άρα είτε υπολογίσουμε πρώτα το γινόμενο \(AB\) και ό,τι βρούμε το πολλαπλασιάσουμε από δεξιά με το \(C\), είτε υπολογίσουμε πρώτα το γινόμενο \(BC\) και ό,τι βρούμε το πολλαπλασιάσουμε από τα αριστερά με το \(A\), το αποτέλεσμα θα είναι το ίδιο.
Δεν είναι όμως ο χρόνος υπολογισμού ο ίδιος.
Υποθέστε ότι οι διαστάσεις των πινάκων \(A, B, C\) είανι, αντίστοιχα, οι \(\mu \times \nu_0\), \(\nu_0 \times \nu_1\) και \(\nu_1 \times \nu_2\). Αν υπολογίσουμε το γινόμενο \(ABC\) με τον πρώτο τρόπο, \(A(BC)\), τότε χρειαζόμαστε χρόνο \(\nu_0\nu_1\nu_2\) (για τον υπολογισμό του \(BC\)) και ακόμη χρόνο \(\mu\nu_0\nu_2\) για τον υπολογισμό του \(A(BC)\) Αν υπολογίσουμε το γινόμενο με το δεύτερο τρόπο, \((AB)C\), τότε χρειαζόμαστε χρόνο \(\mu\nu_0\nu_1\) για τον υπολογισμό του \(AB\) και επιπλέον χρόνο \(\mu\nu_1\nu_2\) για τον υπολογισμό του \((AB)C\).
Αν ονομάσουμε \(T_1\) τον πρώτο χρόνο υπολογισμού και \(T_2\) το δεύτερο τότε έχουμε δηλ. \[ T_1 = \nu_0\nu_1\nu_2 + \mu\nu_0\nu_2,\ \ \ \ T_2 = \mu\nu_0\nu_1 + \mu\nu_1\nu_2. \] Αν για παράδειγμα έχουμε \[ \mu = 10, \nu_0 = 10, \nu_1 = 10, \nu_2 = 2 \] τότε προκύπτει \[ Τ_1 = 400,\ \ \ Τ_2=1200. \] Είναι δηλ. πολύ πιο γρήγορο να υπολογίσουμε το γινόμενο αυτό με τον πρώτο τρόπο.
Στην περίπτωση τώρα που έχουμε να υπολογίσουμε ένα γινόμενο από \(n\) πίνακες \[ A_0 A_1 \cdots A_{n-1}\ \ \ \ \ (P) \] με διαστάσεις \[ \mu\times\nu_0,\ \ \nu_0\times\nu_1,\ \ \nu_1\times\nu_2,\ \ \ldots,\ \ \nu_{n-2}\times\nu_{n-1},\ \ \ \ \ (D) \] σκοπός μας είναι και πάλι να υπολογίσουμε το γρηγορότερο τρόπο με τον οποίο μπορεί να υπολογιστεί αυτό το γινόμενο. Προφανώς η απάντηση εξαρτάται μόνο από τους αριθμούς \[ \mu, \nu_0, \nu_1, \ldots, \nu_{n-1}\ \ \ \ \ \ (DD) \] και όχι από τα περιεχόμενα των πινάκων \(A_j\).
Με όποιο τρόπο κι αν επιλέξουμε να κάνουμε τις πράξεις για τον υπολογισμό του γινομένου \(A_0 A_1 \cdots A_{n-1}\) ο τελευτ-2αίος πολλασιασμός που θα γίνει θα είναι ανάμεσα σε δύο πίνακες \(X\) και \(Y\) και, επειδή δεν αλλάζουμε τη σειρά των πινάκων, οι πίνακες \(X\) και \(Y\) αναγκαστικά θα είναι της μορφής \[ X = A_0 A_1 \cdots A_i,\ \ \ Y = A_{i+1} A_{i+2} \cdots A_{n-1},\ \ \ \ \ (XY) \] για κάποιο \(i=0,1,2,\ldots,n-2\) (αφού κανένα από τα γινόμενα για τα \(X\) και \(Y\) δεν πρέπει να είναι κενό).
Ας γράψουμε τώρα \[ T(\mu, \nu_0, \nu_1, \ldots, \nu_{n-1}) \] για τον ελάχιστο χρόνο υπολογισμού του παραπάνω γινομένου (P) με διαστάσεις (D).
Αν γνωρίζουμε τον ακέραιο \(i\) που εμφανίζεται στην (XY) τότε ισχύει \[ T(\mu, \nu_0, \nu_1, \ldots, \nu_{n-1}) = T(\mu, \nu_0, \nu_1, \ldots, \nu_i) + T(\nu_i, \nu_{i+1},\ldots,\nu_{n-1}) + \mu \nu_i \nu_{n-1},\ \ \ \ \ (R) \] Ο πρώτος προσθετέος στο δεξί μέλος προέρχεται από το ότι υπολογίζουμε τον πίνακα \(X\) με τον καλύτερο δυνατό τρόπο. Ομοίως ο δεύτερος προσθετέος προέρχεται από το ότι υπολογίζουμε τον πίνακα \(Y\) με τον καλύτερο δυνατό τρόπο. Ο τρίτος προσθετέος \(\mu \nu_i \nu_{n-1}\) είναι ο χρόνος που παίρνει να πολλαπλασιάσουμε τα \(X\) και \(Y\) μεταξύ τους.
Για να βρούμε λοιπόν το βέλτιστο χρόνο υπολογισμού του (P) θα πρέπει να βρούμε το ελάχιστο, για όλες τις δυνατές τιμές του \(i\), της ποσότητας (R) παραπάνω. Για κάθε \(i\) υπολογίζουμε το δεξί μέλος της (R) αναδρομικά.
Αυτό κάνουμε στη συνάρτηση findbest παρακάτω της οποίας τα ορίσματα είναι ακριβώς οι ακέραοι στη λίστα (DD)παραπάνω, οι οποίοι περνάνε ως μια λίστα με το όνομα dimension. Η συνάρτηση findbest δεν επιστρέφει όμως μόνο ένα ακέραιο, γιατί τότε θα μας έλεγε μόνο το ποιος είναι ο βέλτιστος χρόνος χωρίς να μας λέει το με ποιο τρόπο επιτυγχάνεται αυτός.
Γι' αυτό η findbest επιστρέφει τρία πράγματα σε μια λίστα. Το πρώτο στοιχείο της λίστας είναι ο βέλτιστος χρόνος, το δεύτερο είναι το \(i\) που αναφέρεται στην (XY) παραπάνω και το τρίτο είναι ένα string το οποίο μας λέει τον τρόπο υπολογισμού βάζοντας κατάλληλες παρενθέσεις στο γινόμενο (δείτε τα αποτελέσματα μετά το πρόγραμμα).
def findbest(dimension):
"""
Ποιος είναι ο βέλτιστος χρόνος πολλαπλασιασμού πινάκων με διαστάσεις
μ x ν0, ν0 x ν1, ν1 x ν2, ... , v(n-2) x v(ν-1), όπου η λίστα dimension περιέχει τα
μ, ν0, ν1, ν2, ..., ν(n-1)
"""
print "findbest({l})".format(l=dimension) # τυπώνουμε ενημερωτικό μήνυμα
n = len(dimension)-1 # πόσοι πίνακες είναι
# Στις παρακάτω δύο περιπτώσεις το μεσαίο στοιχείο της λίστας δεν έχει νόημα και περνάμε κάτι στην τύχη
if n==1: # μόνο ένας πίνακας
return [0, 0, "[{x}x{y}]".format(x=dimension[0],y=dimension[1])]
if n==2: # δύο πίνακες. μόνο ένας τρόπος υπάρχει
return [dimension[0]*dimension[1]*dimension[2], 1,
"([{x}x{y}] [{y}x{z}])".format(x=dimension[0],y=dimension[1],z=dimension[2])]
# Από εδώ και κάτω ψάχνουμε να βρούμε το βέλτιστο i
tm = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το δεξί μέλος της (R) παραπάνω
ll = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το αποτέλεσμα της 1ης κλήσης της findbest στην (R)
lr = [] # στη λίστα αυτή αποθηκεύουμε για όλα τα i το αποτέλεσμα της 2ης κλήσης της findbest στην (R)
for i in range(n-1):
l1 = findbest(dimension[:i+2]) # 1η κλήση της findbest όπως περιγράφεται στην (R)
ll.append(l1)
l2 = findbest(dimension[i+1:]) # 2η κλήση της findbest όπως περιγράφεται στην (R)
lr.append(l2)
s1 = l1[0] # Πρώτος όρος T(..) στην (R)
s2 = l2[0] # Δεύτερος όρος T(..) στην (R)
s3 = dimension[0]*dimension[i+1]*dimension[n] # τρίτος προσθετέος στην (R)
tm.append(s1+s2+s3)
mm = min(tm) # Αυτό υπολογίζει το βέλτιστο χρόνο
ind = tm.index(mm) # και αυτό το για ποιο i συμβαίνει αυτός ο βέλτιστος χρόνος
return [mm, ind, "({sl} {sr})".format(sl=ll[ind][2], sr=lr[ind][2])] # επιστρέφει τις τιμές που χρειάζεται
print findbest([2,3,4,10])