71104
28-05-2006, 14:57
tempo fa avevo postato su questo forum un algoritmo impressionante che spiegò un mio professore l'anno scorso al corso di Programmazione 2; quest'anno ha ripreso lo stesso algoritmo al corso di Algoritmi 2, solo che il problema aveva diverse soluzioni e quest'anno ci ha spiegato solo fino a quella di complessità O(Nlog(N)); l'anno scorso invece aveva spiegato questa soluzione impressionante che riusciva a risolvere il problema in tempo lineare!! :eek:
il problema era il seguente: dato un vettore di interi, anche negativi, trovare la finestra di peso massimo; per "finestra" si intende "sottovettore" (contiguo ovviamente), e per "peso" si intende semplicemente la somma di tutti gli elementi. quindi dato un vettore di N interi sia positivi che negativi, tra tutte le possibili finestre (di qualsiasi lunghezza) trovare quella che ha il peso massimo; se ce ne sono più d'una allora va bene una qualsiasi.
purtroppo non riesco più a trovare gli appunti dell'anno scorso, e quindi non riesco più a trovare la soluzione del professore (qella strafiga in tempo lineare); e così stavo cercando di ricostruirmela da solo, ma non riesco a fare il passo finale: la mia soluzione non funziona in rari casi di vettori contenenti esclusivamente interi negativi.
andiamo con ordine: la soluzione banale è N^2, anche se quella banalissima (di cui poco ci importa) sarebbe addirittura N^3; questa è quella banale:
#define ITEM_COUNT <numero di elementi>
int v[ITEM_COUNT];
int f() {
int max;
int i, j;
max = v[0];
for (i = 0; i < ITEM_COUNT; i++) {
int sum = 0;
for (j = i; j < ITEM_COUNT; j++) {
sum += v[j];
if (sum > max) {
max = sum;
}
}
}
return max;
}
a proposito, come vedete non è necessario restituire come risultato dell'algoritmo gli index dei due bounds della finestra, è sufficiente trovare il peso; lo scopo è trovare il massimo peso presente nell'array.
questa versione dell'algoritmo fa schifo perché fa una marea di lavoro inutile (ripete N volte sempre le stesse somme).
allora per ottimizzare dobbiamo analizzare la funzione della somma, ovvero la funzione che ad un dato index K dell'array associa la somma di tutti gli elementi dell'array dal primo al K-esimo. questa funzione va da N in N, quindi è una successione di naturali. noi altro non dobbiamo fare che trovare nel grafico di questa successione la tratta in salita più lunga di tutte, considerando che questa tratta può tranquillamente contenere anche dei pezzi in discesa; a noi interessa che "complessivamente" sia una salita, e che sia la più lunga di tutte. questa tratta corrisponde esattamente alla finestra di peso massimo che noi dobbiamo trovare.
come fare dunque per trovare questa salitona? innanzitutto è necessario trovare semplicemente il punto più alto di tutta la salita, ovvero il massimo della successione, il peso massimo di tutte le possibili finestre che partono dal'index 0. ci siete? la successione della somma altro non è che la successione dei pesi di tutte le finestre il cui bound di sinistra è l'index 0.
a questo punto una volta trovato il massimo della successione, dobbiamo verificare che esso non si possa addirittura alzare ancora di più: se per esempio nel grafico della successione a sinistra del massimo noi avessimo anche un minimo negativo, allora basterebbe stabilire il margine di sinistra della finestra proprio in corrispondenza dell'indice di tale minimo: così facendo la finestra escluderebbe tutti gli interi che nel vettore hanno portato a quel valore negativo, e la salita si alzerebbe di un bel gap.
ma che succede se invece che un minimo negativo, a sinistra del massimo troviamo solo valori positivi, e quindi un minimo positivo? succede che non dobbiamo assolutamente stabilire lì il margine di sinistra, perché il minimo, essendo positivo, altro non fa che contribuire ad alzare la finestra; quindi dovremo semplicemente lasciare il margine sinistro all'index 0.
una valida soluzione al problema sembrerebbe essersi formulata: analizzo la successione della somma, in essa cerco prima il massimo e poi il minimo a sinistra del massimo; se il minimo è negativo allora lo sottraggo al massimo e ottengo il peso finale, se invece è positivo allora il peso finale corrisponde proprio al massimo. iniziamo a tradurla in codice; per creare i valori della successione della somma posso usare un solo for, e man mano che li creo li posso analizzare per trovare il massimo e il minimo, quindi ottengo un algoritmo di complessità asintotica N:
int i, sum, min, max;
sum = v[0];
min = v[0];
max = v[0];
/*
* sum contiene di volta in volta i valori della successione della somma
* min contiene di volta in volta l'ultimo minimo trovato
* max contiene di volta in volta l'ultimo massimo trovato
*/
for (i = 1; i < ITEM_COUNT; i++) {
sum += v[i];
if (sum < min) {
min = sum;
}
if (sum > max) {
max = min;
}
}
if (min < 0) {
max -= min;
}
return max;
questa è un'ottima versione della soluzione, è lineare e non c'è paragone con quella banale (per non parlare di quella banalissima), ma come avrete probabilmente notato questo codice ha il difetto di non controllare che il minimo si trovi effettivamente a sinistra del massimo, e in caso ciò non accada succede che come risultato l'algoritmo fornisce il peso minimo con segno opposto! :D
cioè se la finestra di peso minimo dell'array ha peso -10, l'algoritmo fornisce 10 (sempre che l'abbia scritto uguale a quello che scrissi quando questa cosa è capitata a me durante i vari esperimenti :p).
per correggere possiamo cambiare leggermente approccio: anziché dire ad ogni iterazione "aggiorna il minimo, aggiorna il massimo" e poi alla fine "vedi se devi togliere il minimo" potremmo fare una cosa del genere: ad ogni iterazione aggiorna il minimo, e se il valore corrente della successione meno l'ultimo minimo trovato costituisce un peso maggiore dell'ultimo peso trovato, allora aggiorna il risultato. in codice:
int i, sum, min, res;
sum = v[0];
min = sum;
res = sum;
for (i = 1; i < ITEM_COUNT; i++) {
sum += v[i];
if (sum < min) {
min = sum;
}
else if (sum - min > res) {
res = sum - min;
}
}
return res;
in altre parole: io in questa soluzione aggiorno a mano a mano i valori della successione della somma; se trovo un minimo (cioè un valore della successione più piccolo dell'ultimo minimo trovato) allora aggiorno la variabile min, altrimenti il valore corrente della successione non è un minimo allora vuol dire che potrebbe essere un risultato valido (cioè un massimo che sta a destra di un minimo): e quindi io verifico che la finestra compresa tra l'ultimo minimo e il valore corrente sia un risultato valido.
badate bene, lo verifico solo in termini di peso, mai di indici dei margini della finestra (guardate il secondo if nel for).
come molti di quelli che sono riusciti a seguirmi fin qui si saranno probabilmente accorti, quest'ultima versione ha il difetto di sottrarre dal massimo il minimo a sinistra del massimo sempre e comunque, mentre se vi ricordate si era detto che il minimo a sinistra del massimo andava sottratto solo se era negativo: se invece è positivo altro non fa che aiutarci ad alzare tutto il grafico, quindi va tenuto.
la correzione? presto detto: basta cambiare di poco il significato della variabile min. min per ora è due cose:
1) il valore dell'ultimo minimo trovato nella successione della somma, la quale, ricordiamo, altro non è che la successione dei pesi di tutte le possibili finestre zero-based
2) un valore da sottrarre al massimo che sta alla sua destra, in quanto se esso (il minimo) è negativo ci farà alzare il massimo di un certo gap precisamente uguale a -min
ovviamente il punto 2 non specifica l'osservazione del caso in cui min sia positivo e il gap negativo, cioè il caso in cui la curva si abbassi. ora cambiamo il significato di min nel seguente modo: se l'ultimo minimo trovato è negativo allora min corrisponde ad esso, altrimenti min è 0. in altre parole: fintanto chè il minimo trovato si mantiene positivo, min è uguale a 0, ma non appena trovo un minimo negativo min scende subito sotto zero. ovviamente non è che posso trovare un minimo positivo dopo un minimo negativo, un minimo sempre minimo è :D
che cosa succede con questa modifica? semplicemente succede che quando io, nel secondo if del for, vado a sottrarre min dal valore corrente della successione, sottraggo un gap valido se il minimo è negativo (cioè se posso alzare la curva), e non sottraggo un bel nulla nel caso in cui invece la abbasserei!! :)
tutto come volevamo; ecco dunque il nostro codice:
int i, sum, min, res;
sum = v[0];
min = 0;
if (sum < 0) {
min = sum;
}
res = sum;
for (i = 1; i < ITEM_COUNT; i++) {
sum += v[i];
if (sum < min) {
min = sum;
}
else if (sum - min > res) {
res = sum - min;
}
}
return res;
ora, questo codice che io sappia funziona sempre, ma come dissi all'inizio del post ci sono rari casi di vettori contenenti esclusivamente elementi negativi in cui l'algoritmo non funziona; però c'è da dire che ci sono anche casi di vettori contenenti esclusivamente elementi negativi in cui l'algoritmo funziona. arrivato fin qui non ho la forza mentale di capire il problema, so solo che nei vettori con elementi tutti negativi la successione della somma si trova completamente sotto lo zero (se vi si trova la successione di interi degli elementi del vettore, vi si trova a maggior ragione la successione della somma).
forse a2000 saprebbe dare la soluzione definitiva al problema in Visual Basic :D
per ora, eccovi il codice completo del mio programma:
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define ITEM_COUNT (5)
int v[ITEM_COUNT];
void generate() {
int i;
for (i = 0; i < ITEM_COUNT; i++) {
v[i] = rand() % 19 - 10;
printf("%d ", v[i]);
}
printf("\n");
}
/* f1 è la soluzione banale */
int f1() {
int max;
int i, j;
max = v[0];
for (i = 0; i < ITEM_COUNT; i++) {
int sum = 0;
for (j = i; j < ITEM_COUNT; j++) {
sum += v[j];
if (sum > max) {
max = sum;
}
}
}
return max;
}
/* f2 è la soluzione tamarra */
int f2() {
int i, sum, min, res;
sum = v[0];
min = 0;
if (sum < 0) {
min = sum;
}
res = sum;
for (i = 1; i < ITEM_COUNT; i++) {
sum += v[i];
if (sum < min) {
min = sum;
}
else if (sum - min > res) {
res = sum - min;
}
}
return res;
}
int main() {
int i;
srand(time(NULL));
for (i = 0; i < 100; i++) {
int r1, r2;
generate();
r1 = f1();
r2 = f2();
printf("soluzione 1: %d\n", r1);
printf("soluzione 2: %d\n", r2);
if (r1 != r2) {
printf("*** failed! (%d)\n", i + 1);
return -1;
}
}
printf("*** success.\n");
return 0;
}
un sentito grazie a chi avesse letto fin qui :D
ciao ;) *
* sintomo di VICIUSite
il problema era il seguente: dato un vettore di interi, anche negativi, trovare la finestra di peso massimo; per "finestra" si intende "sottovettore" (contiguo ovviamente), e per "peso" si intende semplicemente la somma di tutti gli elementi. quindi dato un vettore di N interi sia positivi che negativi, tra tutte le possibili finestre (di qualsiasi lunghezza) trovare quella che ha il peso massimo; se ce ne sono più d'una allora va bene una qualsiasi.
purtroppo non riesco più a trovare gli appunti dell'anno scorso, e quindi non riesco più a trovare la soluzione del professore (qella strafiga in tempo lineare); e così stavo cercando di ricostruirmela da solo, ma non riesco a fare il passo finale: la mia soluzione non funziona in rari casi di vettori contenenti esclusivamente interi negativi.
andiamo con ordine: la soluzione banale è N^2, anche se quella banalissima (di cui poco ci importa) sarebbe addirittura N^3; questa è quella banale:
#define ITEM_COUNT <numero di elementi>
int v[ITEM_COUNT];
int f() {
int max;
int i, j;
max = v[0];
for (i = 0; i < ITEM_COUNT; i++) {
int sum = 0;
for (j = i; j < ITEM_COUNT; j++) {
sum += v[j];
if (sum > max) {
max = sum;
}
}
}
return max;
}
a proposito, come vedete non è necessario restituire come risultato dell'algoritmo gli index dei due bounds della finestra, è sufficiente trovare il peso; lo scopo è trovare il massimo peso presente nell'array.
questa versione dell'algoritmo fa schifo perché fa una marea di lavoro inutile (ripete N volte sempre le stesse somme).
allora per ottimizzare dobbiamo analizzare la funzione della somma, ovvero la funzione che ad un dato index K dell'array associa la somma di tutti gli elementi dell'array dal primo al K-esimo. questa funzione va da N in N, quindi è una successione di naturali. noi altro non dobbiamo fare che trovare nel grafico di questa successione la tratta in salita più lunga di tutte, considerando che questa tratta può tranquillamente contenere anche dei pezzi in discesa; a noi interessa che "complessivamente" sia una salita, e che sia la più lunga di tutte. questa tratta corrisponde esattamente alla finestra di peso massimo che noi dobbiamo trovare.
come fare dunque per trovare questa salitona? innanzitutto è necessario trovare semplicemente il punto più alto di tutta la salita, ovvero il massimo della successione, il peso massimo di tutte le possibili finestre che partono dal'index 0. ci siete? la successione della somma altro non è che la successione dei pesi di tutte le finestre il cui bound di sinistra è l'index 0.
a questo punto una volta trovato il massimo della successione, dobbiamo verificare che esso non si possa addirittura alzare ancora di più: se per esempio nel grafico della successione a sinistra del massimo noi avessimo anche un minimo negativo, allora basterebbe stabilire il margine di sinistra della finestra proprio in corrispondenza dell'indice di tale minimo: così facendo la finestra escluderebbe tutti gli interi che nel vettore hanno portato a quel valore negativo, e la salita si alzerebbe di un bel gap.
ma che succede se invece che un minimo negativo, a sinistra del massimo troviamo solo valori positivi, e quindi un minimo positivo? succede che non dobbiamo assolutamente stabilire lì il margine di sinistra, perché il minimo, essendo positivo, altro non fa che contribuire ad alzare la finestra; quindi dovremo semplicemente lasciare il margine sinistro all'index 0.
una valida soluzione al problema sembrerebbe essersi formulata: analizzo la successione della somma, in essa cerco prima il massimo e poi il minimo a sinistra del massimo; se il minimo è negativo allora lo sottraggo al massimo e ottengo il peso finale, se invece è positivo allora il peso finale corrisponde proprio al massimo. iniziamo a tradurla in codice; per creare i valori della successione della somma posso usare un solo for, e man mano che li creo li posso analizzare per trovare il massimo e il minimo, quindi ottengo un algoritmo di complessità asintotica N:
int i, sum, min, max;
sum = v[0];
min = v[0];
max = v[0];
/*
* sum contiene di volta in volta i valori della successione della somma
* min contiene di volta in volta l'ultimo minimo trovato
* max contiene di volta in volta l'ultimo massimo trovato
*/
for (i = 1; i < ITEM_COUNT; i++) {
sum += v[i];
if (sum < min) {
min = sum;
}
if (sum > max) {
max = min;
}
}
if (min < 0) {
max -= min;
}
return max;
questa è un'ottima versione della soluzione, è lineare e non c'è paragone con quella banale (per non parlare di quella banalissima), ma come avrete probabilmente notato questo codice ha il difetto di non controllare che il minimo si trovi effettivamente a sinistra del massimo, e in caso ciò non accada succede che come risultato l'algoritmo fornisce il peso minimo con segno opposto! :D
cioè se la finestra di peso minimo dell'array ha peso -10, l'algoritmo fornisce 10 (sempre che l'abbia scritto uguale a quello che scrissi quando questa cosa è capitata a me durante i vari esperimenti :p).
per correggere possiamo cambiare leggermente approccio: anziché dire ad ogni iterazione "aggiorna il minimo, aggiorna il massimo" e poi alla fine "vedi se devi togliere il minimo" potremmo fare una cosa del genere: ad ogni iterazione aggiorna il minimo, e se il valore corrente della successione meno l'ultimo minimo trovato costituisce un peso maggiore dell'ultimo peso trovato, allora aggiorna il risultato. in codice:
int i, sum, min, res;
sum = v[0];
min = sum;
res = sum;
for (i = 1; i < ITEM_COUNT; i++) {
sum += v[i];
if (sum < min) {
min = sum;
}
else if (sum - min > res) {
res = sum - min;
}
}
return res;
in altre parole: io in questa soluzione aggiorno a mano a mano i valori della successione della somma; se trovo un minimo (cioè un valore della successione più piccolo dell'ultimo minimo trovato) allora aggiorno la variabile min, altrimenti il valore corrente della successione non è un minimo allora vuol dire che potrebbe essere un risultato valido (cioè un massimo che sta a destra di un minimo): e quindi io verifico che la finestra compresa tra l'ultimo minimo e il valore corrente sia un risultato valido.
badate bene, lo verifico solo in termini di peso, mai di indici dei margini della finestra (guardate il secondo if nel for).
come molti di quelli che sono riusciti a seguirmi fin qui si saranno probabilmente accorti, quest'ultima versione ha il difetto di sottrarre dal massimo il minimo a sinistra del massimo sempre e comunque, mentre se vi ricordate si era detto che il minimo a sinistra del massimo andava sottratto solo se era negativo: se invece è positivo altro non fa che aiutarci ad alzare tutto il grafico, quindi va tenuto.
la correzione? presto detto: basta cambiare di poco il significato della variabile min. min per ora è due cose:
1) il valore dell'ultimo minimo trovato nella successione della somma, la quale, ricordiamo, altro non è che la successione dei pesi di tutte le possibili finestre zero-based
2) un valore da sottrarre al massimo che sta alla sua destra, in quanto se esso (il minimo) è negativo ci farà alzare il massimo di un certo gap precisamente uguale a -min
ovviamente il punto 2 non specifica l'osservazione del caso in cui min sia positivo e il gap negativo, cioè il caso in cui la curva si abbassi. ora cambiamo il significato di min nel seguente modo: se l'ultimo minimo trovato è negativo allora min corrisponde ad esso, altrimenti min è 0. in altre parole: fintanto chè il minimo trovato si mantiene positivo, min è uguale a 0, ma non appena trovo un minimo negativo min scende subito sotto zero. ovviamente non è che posso trovare un minimo positivo dopo un minimo negativo, un minimo sempre minimo è :D
che cosa succede con questa modifica? semplicemente succede che quando io, nel secondo if del for, vado a sottrarre min dal valore corrente della successione, sottraggo un gap valido se il minimo è negativo (cioè se posso alzare la curva), e non sottraggo un bel nulla nel caso in cui invece la abbasserei!! :)
tutto come volevamo; ecco dunque il nostro codice:
int i, sum, min, res;
sum = v[0];
min = 0;
if (sum < 0) {
min = sum;
}
res = sum;
for (i = 1; i < ITEM_COUNT; i++) {
sum += v[i];
if (sum < min) {
min = sum;
}
else if (sum - min > res) {
res = sum - min;
}
}
return res;
ora, questo codice che io sappia funziona sempre, ma come dissi all'inizio del post ci sono rari casi di vettori contenenti esclusivamente elementi negativi in cui l'algoritmo non funziona; però c'è da dire che ci sono anche casi di vettori contenenti esclusivamente elementi negativi in cui l'algoritmo funziona. arrivato fin qui non ho la forza mentale di capire il problema, so solo che nei vettori con elementi tutti negativi la successione della somma si trova completamente sotto lo zero (se vi si trova la successione di interi degli elementi del vettore, vi si trova a maggior ragione la successione della somma).
forse a2000 saprebbe dare la soluzione definitiva al problema in Visual Basic :D
per ora, eccovi il codice completo del mio programma:
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define ITEM_COUNT (5)
int v[ITEM_COUNT];
void generate() {
int i;
for (i = 0; i < ITEM_COUNT; i++) {
v[i] = rand() % 19 - 10;
printf("%d ", v[i]);
}
printf("\n");
}
/* f1 è la soluzione banale */
int f1() {
int max;
int i, j;
max = v[0];
for (i = 0; i < ITEM_COUNT; i++) {
int sum = 0;
for (j = i; j < ITEM_COUNT; j++) {
sum += v[j];
if (sum > max) {
max = sum;
}
}
}
return max;
}
/* f2 è la soluzione tamarra */
int f2() {
int i, sum, min, res;
sum = v[0];
min = 0;
if (sum < 0) {
min = sum;
}
res = sum;
for (i = 1; i < ITEM_COUNT; i++) {
sum += v[i];
if (sum < min) {
min = sum;
}
else if (sum - min > res) {
res = sum - min;
}
}
return res;
}
int main() {
int i;
srand(time(NULL));
for (i = 0; i < 100; i++) {
int r1, r2;
generate();
r1 = f1();
r2 = f2();
printf("soluzione 1: %d\n", r1);
printf("soluzione 2: %d\n", r2);
if (r1 != r2) {
printf("*** failed! (%d)\n", i + 1);
return -1;
}
}
printf("*** success.\n");
return 0;
}
un sentito grazie a chi avesse letto fin qui :D
ciao ;) *
* sintomo di VICIUSite