evilspirit2000
31-05-2012, 14:50
Non riesco a risolvere alcuni problemi. ve ne descrivo uno:
ho in input una matrice binaria quadrata nxn. Devo ricercare in questa matrice la più grande sottomatrice quadrata formata da soli 0.
l'algoritmo deve essere sviluppato in programmazione dinamica utilizzando metodo top-down.
input soluzione
0001 1110
0000 1222
0100 1222
0010 1222
la mia idea è la seguente:
utilizzo una matrice T nxn nella quale T[i,j] = alla dimensione della più grande sottomatrice di 0 che posso ottenere se la matrice di imput avesse i righe e j colonne. per dimensione intendo la lunghezza di un lato.
nella cella T[1,n] ci sarà la dimensione della più grande sottomatrice di 0.
il tutto sta nel trovare la ricorsione:
T[i,j]=
1 se input[i,j]=0,
0 se input[i,j]=1
con i=1 or j=1
T[i,j]=1 + min [T[i,j-1], T[i-1,j], T[i-1,j-1]] con input[i,j]=0
T[i,j]=max [T[i,j-1], T[i-1,j]] con input[i,j]=1
tale ricorsione non è giusta. in alcuni casi restituisce la soluzione in altri no. ad esempio con l'input precedente sbaglia, restituendo:
1110
1221
1232
1233
potete darmi una mano per risolverlo?
grazie
ho in input una matrice binaria quadrata nxn. Devo ricercare in questa matrice la più grande sottomatrice quadrata formata da soli 0.
l'algoritmo deve essere sviluppato in programmazione dinamica utilizzando metodo top-down.
input soluzione
0001 1110
0000 1222
0100 1222
0010 1222
la mia idea è la seguente:
utilizzo una matrice T nxn nella quale T[i,j] = alla dimensione della più grande sottomatrice di 0 che posso ottenere se la matrice di imput avesse i righe e j colonne. per dimensione intendo la lunghezza di un lato.
nella cella T[1,n] ci sarà la dimensione della più grande sottomatrice di 0.
il tutto sta nel trovare la ricorsione:
T[i,j]=
1 se input[i,j]=0,
0 se input[i,j]=1
con i=1 or j=1
T[i,j]=1 + min [T[i,j-1], T[i-1,j], T[i-1,j-1]] con input[i,j]=0
T[i,j]=max [T[i,j-1], T[i-1,j]] con input[i,j]=1
tale ricorsione non è giusta. in alcuni casi restituisce la soluzione in altri no. ad esempio con l'input precedente sbaglia, restituendo:
1110
1221
1232
1233
potete darmi una mano per risolverlo?
grazie