altro che brainfuck... O.o'

[71104]

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!!

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!
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 ).

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 è

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

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

ciao *


* sintomo di VICIUSite

[71104]

ah, dimenticavo: volendo fare i pignoli la stima temporale della soluzione banale sarebbe, se ho calcolato bene, (N^2)/2, non N^2

[alesnoce]

Non ho avuto il coraggio di leggere tutto il tuo post, quindi ti chiedo scusa se non ho capito cosa cerchi di ottenere.

Supponendo che N sia la dimensione di vettore e n la dimensione della finestra, io avrei una soluzione banale:

crei un vettore pesi di dimensione N-n;
fai la somma dei primi n elementi e la poni in pesi[0];
a questo valore togli vettore[0] e sommi vettore[n];
poni il valore ottenuto in pesi[1];
.....
.....
guardi qual è il max elemento di pesi;
l'indice di questo elemento è l'indice di vettore a partire dal quale inizia la finestra di peso massimo.

Ciao

[alesnoce]

Ho detto una cretinata.
Solo ora ho visto che la dimensione della finestra può essere variabile.
Fa conto che non ti abbia risposto

[marco.r]

la mia idea (codice in python)

def cercaFinestra( v ):
    best = [0]*len(v)
    best[0] = v[0]
    for i in range(1,len(v)):
        best[i ] = v[i ] + max(0,best[i-1])
    return max( best )

Ovvero:
durante l'iterazione in best[ i] memorizzo il miglior peso di tutte le finestre che finiscono con l'i-esimo elemento
Per il primo elemento è facile, best[0] coincide col valore del primo elemento. Per gli altri si puo' vedere facilmente che il peso migliore è
1 - Il peso dell'elemento corrente piu' il miglior peso della finestra che finisce all'elemento precedente
oppure
2 - Il solo peso corrente se il miglior peso di cui sopra è negativo (in pratica ricomincio con una nuova finestra)

L'array e il secondo ciclo si possono sicuramente ottimizzare, ma mi sembrava piu' chiaro cosi'.


uyfff.. ma una volta [ code ] non disabilitava i tag ?

[marco.r]

ho visto ora che praticamente coincide con la tua

[71104]

Originariamente inviato da marco.r

ho visto ora che praticamente coincide con la tua

ma la tua funziona sempre?

[marco.r]

Originariamente inviato da 71104

ma la tua funziona sempre?

Non vedo errori nella dimostrazione del funzionamento dell'algoritmo, e la funzione li' sopra ne è la conversione pedissequa in codice.
Di sicuro nei casi che hai citato tu (vettori totalmente negativi) funziona, il vettore best coincide col vettore dei dati.
Se vuoi posso provare con una dimostrazione piu' rigorosa, non l'ho fatto per pigrizia .

[Furla]

non so se ho capito bene il problema, ci stavo ragionando un po' e la soluzione mi è parsa troppo semplice...

se tutti gli elementi del vettore fossero negativi, la finestra corrisponderebbe all'elemento dal valore più vicino allo zero, e l'output sarebbe tale valore?

[71104]

Originariamente inviato da Furla

se tutti gli elementi del vettore fossero negativi, la finestra corrisponderebbe all'elemento dal valore più vicino allo zero, e l'output sarebbe tale valore?

si... dunque? ^^

[Furla]

premetto che non ho avuto voglia di leggere attentamente tutto ciò che avete scritto, credo di aver inquadrato il problema e vi propongo una soluzione che mi sembra poter funzionare in tutte le situazioni.

ecco in un vb non molto ortodosso la mia idea:

dim best as long 'miglior peso
dim attuale as long 'peso attuale
dim v(0 to Nelementi) as integer 'vettore di interi

best = v(0)
attuale = v(0)

for i = 1 to Nelementi
	if v(i) > 0 then
		if v(i-1) < 0 and attuale < 0 then
			attuale = 0
		end if  
	else
		if v(i-1) > 0 then
			if best < attuale then
				best = attuale
			end if
		else
			if best < v(i) then
				best = v(i)
			end if
		endif
	end if
	attuale = attuale + v(i)
next

msgbox.show("il peso maggiore è " & best)

il codice non è ottimizzato, ho seguito la casistica come mi è venuta in mente e forse si può migliorare, intanto così mi sembra abbastanza comprensibile.

dunque, il mio ragionamento si basa tutto su alcune proprietà delle finestre che mi sono venute in mente mentre ci pensavo, ognuna conseguente dalle precedenti. è molto più lungo e difficile scriverle che capirle:
[rileggendo tutto, la faccenda è intricata perché il linguaggio necessita di chiarezza ed è quindi pieno di ripetizioni, ma mi sembra comprensibile]

- se il primo o l'ultimo elemento di una finestra costituita da più di un elemento è negativo, tale sottovettore comprende almeno un sottovettore dal peso maggiore del suo;
- se la finestra comprende almeno un elemento positivo, a partire dal primo elemento positivo è possibile dividerla in almeno un "sottovettore base", dove per "sottovettore base" si intende un sottovettore il cui primo elemento è positivo e che comprende una sequenza di soli elementi positivi (parte positiva, da ora in poi), seguita da una sequenza di soli elementi negativi (parte negativa, da ora in poi). la parte positiva costituisce il sottovettore di peso massimo del "sottovettore base". il peso di un "sottovettore base" è dato dalla differenza dei pesi della sua parte positiva e della sua parte negativa.
- possiamo ora vedere il vettore di interi come una sequenza iniziale di negativi (che può anche essere costituita da 0 elementi, quando il vettore parte con un elemento positivo) e da un certo numero di "sottovettori base" (che può essere 0, se tutti gli elementi sono negativi).

da tutto ciò deriva che se esiste almeno un "sottovettore base" nel vettore che analizziamo, la finestra dal peso maggiore è necessariamente costituita da un certo numero di "sottovettori base" contigui, il primo dei quali ha peso sicuramente positivo, e dalla sequenza di positivi che farebbe parte del "sottovettore base" successivo ad essi.
l'algoritmo che ho costruito sfrutta questa proprietà per determinare il peso massimo otenibile da ogni serie di "sottovettori base" contigui e la successiva sequenza positiva: è una specie di automa che in base al segno dell'elemento attuale e di quello precedente "capisce" in che situazione si trova e come agire sulle variabili.

se trovate errori in queste proprietà o se non risultano chiare ditemelo

[71104]

scusa ma alla prima iterazione non c'è la possibilità che il codice acceda all'elemento di indice -1 ...?

[Furla]

sì il for deve partire da 1^^

thx ora correggo