Problema k-sottovettori usando la programmazione dinamica
Ho un problema con quest'esercizio:
Dato un vettore V di n interi ed un intero k, $ kleqn $ , si vuole un sottovettore (una sequenza di elementi consecutivi del vettore) di lunghezza massima contenente al più k elementi distinti.
Bisogna utilizzare la tecnica della programmazione dinamica per scrivere un algoritmo che risolva il problema in un tempo O(n*k).
Il mio problema fondamentale è quello di contare gli elementi distinti nell'array(logicamente nell'equazione di ricorrenza).
Voi come risolverte questo problema (in particolare l'equazione di ricorrenza) ?
Dato un vettore V di n interi ed un intero k, $ kleqn $ , si vuole un sottovettore (una sequenza di elementi consecutivi del vettore) di lunghezza massima contenente al più k elementi distinti.
Bisogna utilizzare la tecnica della programmazione dinamica per scrivere un algoritmo che risolva il problema in un tempo O(n*k).
Il mio problema fondamentale è quello di contare gli elementi distinti nell'array(logicamente nell'equazione di ricorrenza).
Voi come risolverte questo problema (in particolare l'equazione di ricorrenza) ?
Risposte
Prima cosa essendo programmazione dinamica, bisogna cercare la sottostruttura ottima e dimostrare che esiste per ogni sottoproblema. (la dimostrazione non la farò)
Sia \(\displaystyle D[i,j] \) l'insieme della lunghezza massima del k-vector di \(\displaystyle V[i...j] \). Se ipotizziamo che \(\displaystyle i0 \rightarrow \nexists j \) la lunghezza massima è 1.
Altrimenti si hanno due casi:
se \(\displaystyle v \neq v[j] \)
- se \(\displaystyle |i-j| < k \) allora \(\displaystyle D[i,j+1] \) perchè il sottovettore contiene elementi diversi (da dimostrare)
- se \(\displaystyle |i-j| \geq k \) allora \(\displaystyle D[i,j] \) è massimo
se \(\displaystyle v=v[j] \)
- se \(\displaystyle |i-(j-1)| \leq k \) allora \(\displaystyle D[i,j-1] \) è massimo
- se \(\displaystyle |i-(j-1)|<(n-j) \) allora \(\displaystyle D[j,j+1] \)
forse l'ultimo caso è da rivedere, ma più o meno ho scritto la mia idea.
E' da dimostrare la sottostruttua ottima, ma basta che lo fai per assurdo. Se la mia idea è corretta, che comunque è da vedere, prova a continuare te.
Sia \(\displaystyle D[i,j] \) l'insieme della lunghezza massima del k-vector di \(\displaystyle V[i...j] \). Se ipotizziamo che \(\displaystyle i
Altrimenti si hanno due casi:
se \(\displaystyle v \neq v[j] \)
- se \(\displaystyle |i-j| < k \) allora \(\displaystyle D[i,j+1] \) perchè il sottovettore contiene elementi diversi (da dimostrare)
- se \(\displaystyle |i-j| \geq k \) allora \(\displaystyle D[i,j] \) è massimo
se \(\displaystyle v=v[j] \)
- se \(\displaystyle |i-(j-1)| \leq k \) allora \(\displaystyle D[i,j-1] \) è massimo
- se \(\displaystyle |i-(j-1)|<(n-j) \) allora \(\displaystyle D[j,j+1] \)
forse l'ultimo caso è da rivedere, ma più o meno ho scritto la mia idea.
E' da dimostrare la sottostruttua ottima, ma basta che lo fai per assurdo. Se la mia idea è corretta, che comunque è da vedere, prova a continuare te.
Innanzitutto ti ringrazio per la risposta e come da te consigliato andrò a presentarmi nell'apposita sezione.
Riguardo l'esercizio ti volevo chiedere alcune cose:
Vedendo la tua soluzione ho notato che l'indice i non viene incrementato in nessun caso, e volevo chiederti il motivo. Poi volevo sapere da dove fai partire inizialmente gli indici i e j perchè non ho ben capito il confronto tra v e v[j].
Riguardo l'esercizio ti volevo chiedere alcune cose:
Vedendo la tua soluzione ho notato che l'indice i non viene incrementato in nessun caso, e volevo chiederti il motivo. Poi volevo sapere da dove fai partire inizialmente gli indici i e j perchè non ho ben capito il confronto tra v e v[j].
Sia $D(v, k, i)$ la lunghezza del sotto-vettore di lunghezza massima con al più k elementi in $v[1..i]$ (gli indici li faccio partire da 1). $L(v, k, i)$ è invece la lunghezza del più lungo vettore $v[j..i]$ con al più $k$ elementi. Noto che si deve avere:
$D(v, k, i+1) = max(D(v, k, i), L(v, k, i+1))$.
Per calcolare $L(v,k,i+1)$ si potrebbe ad esempio mantenere un array di lunghezza $k$ di indici in cui i $k$ elementi di questo sottovettore finale sono comparsi per l'ultima volta. Quando si aggiunge un elemento alla fine di questo vettore è sufficiente verificare se questo elemento è già presente nel sottovettore. Se l'elemento è già presente allora $L(v, k, i+1) = L(v, k, i) + 1$, altrimenti si cerca l'elemento che è da più tempo che non compare e si mette il nuovo elemento trovato al posto di quello vecchio. In questo caso $L(v,k,i+1) = i + 1 - oldest$ dove oldest è l'indice dell'elemento che è stato eliminato.
$D(v, k, i+1) = max(D(v, k, i), L(v, k, i+1))$.
Per calcolare $L(v,k,i+1)$ si potrebbe ad esempio mantenere un array di lunghezza $k$ di indici in cui i $k$ elementi di questo sottovettore finale sono comparsi per l'ultima volta. Quando si aggiunge un elemento alla fine di questo vettore è sufficiente verificare se questo elemento è già presente nel sottovettore. Se l'elemento è già presente allora $L(v, k, i+1) = L(v, k, i) + 1$, altrimenti si cerca l'elemento che è da più tempo che non compare e si mette il nuovo elemento trovato al posto di quello vecchio. In questo caso $L(v,k,i+1) = i + 1 - oldest$ dove oldest è l'indice dell'elemento che è stato eliminato.
@apatriarca: forse ho capito male io il problema, ma se dici "se questo elemento è già presente nel sottovettore" e "si cerca l'elemento che è da più tempo" vuol dire che gli elementi distinti non sono contigui.
Io mi sono immaginato che bisognasse cercare il sotto-vettore di dimensione massima $<=k$ e con al massimo k elementi distinti.
perciò: se abbiamo $k=4$ e $v=[1123346555]$ il massimo sotto-vettore è $3465$ posizione $(5,8)$ sono contigui e distinti. Se dici ricerca e sostituzione vuol dire che non sono contigui. Ho capito male?
Io mi sono immaginato che bisognasse cercare il sotto-vettore di dimensione massima $<=k$ e con al massimo k elementi distinti.
perciò: se abbiamo $k=4$ e $v=[1123346555]$ il massimo sotto-vettore è $3465$ posizione $(5,8)$ sono contigui e distinti. Se dici ricerca e sostituzione vuol dire che non sono contigui. Ho capito male?
Il parametro k riguarda solo gli elementi distinti del vettore , cioè il sottovettore deve avere al più k elementi distini, e non la dimensione del sottovettore
ah ma allora nel sotto-vettore ci possono essere elementi doppi...
perchè se sono tutti distinti la lunghezza massima sarà k.
perchè se sono tutti distinti la lunghezza massima sarà k.
si ci possono essere elementi doppi, il limite è solo sul numeri di elementi distinti del sottovettore
ah allora cambia tutto, il mio approccio è solo elementi distinti unici.
perciò: k=4 e v=[1123346555] max=[3346555] allora l'approccio di apatriarca è corretto, anche se non mi è chiara la funzione ricerca, ma sicuramente per queste cose è più esperto.
perciò: k=4 e v=[1123346555] max=[3346555] allora l'approccio di apatriarca è corretto, anche se non mi è chiara la funzione ricerca, ma sicuramente per queste cose è più esperto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo