Newsgroup: it.comp.lang.c++
Titolo: Moltiplicazione di matrici.

Salve a tutti, ecco il mio problema:
devo moltiplicare n matrici A1, A2,...An. Ora la moltiplicazione fra matrici
può avvenire solo se, date due matrici A e B, il numero di colonne di A è
uguale al numero di righe di B per cui se A è p*q e B q*r il risultato sarà
C=p*r e le operazioni effettuate saranno p*q*r.
Se sono solo due le matrici non ci sono problemi ma se le matrici sono n
bisognerà trovare la parentesizzazione giusta perchè:
consideriamo 3 matrici A1, A2, A3 che sono 10*100, 100*5, 5*50. Se voglio
fare ((A1,A2)A3) per calcolare la matrice 10*5 si faranno 10*100*5
moltiplicazioni e cioè 5000 op. Moltiplichiamo per l'altra matrice ed
otteniamo 10*5*50=2500 e quindi in totale avrò 7500 operazioni. Se eseguo
invece (A1(A2,A3)) ottengo 100*5*50=25000 più 10*100*50=50000 con un ovvio
costo in più in termini di operazioni.
Ora per quanto ne so è un problema di ottimizzazione e mi è stato detto di
risolverlo con qualcosa tipo la programmazione dinamica (di cui io non so
minimamente che cosa sia)...non è che c'è qualche anima pia che saprebbe
dirmi di che cosa si tratta e come implementarla in C++? La moltiplicazione
fra matrici la so fare ma è il resto che mi preoccupa.
Grazie in anticipo.
---Seek and Destroy---

risolverlo con qualcosa tipo la programmazione dinamica (di cui io non so
Non so cosa sia , però è un problema che (se il numero di matrici è
grande) si presta ad essere velocemente risolto con gli algoritmi
genetici.
Enzo.


La programmazione dinamica è una tecnica di programmazione che consiste nel
risolvere un problema di ottimizzazione risolvendo e memorizzando i
risultati di opportuni sottoproblemi (senza ricalcolarli ogni volta). Questa
cosa si può fare quando la soluzione ottimale è decomponibile in
sottoproblemi a loro volta globalmente ottimali.
Nel caso della moltiplicazione a catena di matrici questa proprietà è vera;
intuitivamente: se devo moltiplicare n matrici A(1)..A(n) e ho trovato una
parentesizzazione per B=A(1)..A(k) e C=A(k+1)..A(n) allora se riduco il
numero di op. per calcolare B anche il risultato finale BC avrà meno
operazioni.
Per cui l'algoritmo consiste nel trovare tutti i possibili modi di
moltiplicare le n matrici e scegliere quello migliore, ma ricordandomi
(cache) i valori migliori trovati per i sottoproblemi.
Poiché sono buono, non ti lascio da scrivere il programma per esercizio :)
Eccoti l'url che lo contiene:
http://www.cs.fiu.edu/~weiss/dsaa_c++/code/Fig10_46.cpp
Fa parte del codice sorgente di "Data Structures and Algorithm Analysis in
C++" di M. A. Weiss (
http://www.cs.fiu.edu/~weiss/
), ed è talmente piccolo
che avrei potuto incollarlo qui.
Ciao!
    Raffaele (RDA)


Per fare un'ottimizzazione perfetta bisognerebbe o lavorare di forza bruta
(passarsi tutte le possibilita' e calcolare quella con meno operazioni tipo
scacchi) o farci sopra uno studio piu' approfondito o usare uno studio gia'
fatto (quella "programmazione dinamica" di cui anch'io non so niente).
Se no ho pensato ad un metodo di questo tipo che sicuramente diminuisce il
numero di calcoli.
Nell'esempio che tu hai fatto si vede come moltiplicando due matrici del
tipo 10*100, 100*5 si hanno 10*100*5 moltpilicazioni e si ottiene una
matrice 10*5.
Quindi se moltiplichi due matrici la dimensione centrale "scompare" dopo una
moltiplicazione.
Se quel numero 100 tu lo avessi usato come numero esterno (come nel tuo
secondo esempio) non "scompariva" e te lo tiravi dietro per un'altra
moltiplicazione.
Insomma dovresti passarti la tua fila di n matrici e andare a vedere quale
e' la dimensione
maggiore tra quelle "affacciate" e farle per prime, in questo modo sei
sicuro che i numeri grossi te li calcoli in quelle moltiplicazione a tre
solo una volta.
Questo escluso le due dimensioni alle estremita' ( intendo la prima matrice
della serie e l'ultima) che se sono
grosse andrebbero lasciate per ultime in quanto le due dimensioni alle
estremita' te le porti dietro fino alla fine.
Quindi: ti fai un giro: vedi qual'e' la dimensione piu' grossa che non sia
ne' la prima ne' l'ultima e moltiplichi quelle due matrici.
E poi ricominci da capo fino a che noi hai finito
Giacomo