Problemi di ottimizzazione

Sistema di indipendenza

Definizione [sistema di indipendenza]: un sistema di indipendenza è una coppia $\lang E,F \rang$ dove

• $E$ è un insieme finito
• $F \subseteq 2^E$ (famiglia di sottoinsiemi di $E$)
• $A \in F \land B \subseteq A \rarr B \in F$, cioè per ogni A appartenente alla famiglia F, anche tutti i sottoinsiemi di A appartengono a F

Definizione [problema di ottimizzazione]:

Input: un sistema di indipendenza $\lang E, F \rang$ e una funzione peso $w:E \rarr \R^+$

Output: $M \in F$ tale che $\forall A \in F, \ w(A) \leq w(M)$

nota: $w(M)=\sum_{e \in M}w(e)$

Procedura Greedy

greedy → goloso

Definiamo una procedura che prova a risolvere un problema di ottimizzazione cercando ad ogni passo di estendere una soluzione parziale aggiungendo un elemento localmente ottimo

Procedura Greedy(<E, F>, w){
	set S;
	S = emptyset();
	while(!is_empty(E)){
		m = max(E); //elemento massimo corrente
		E = E \\ {m}; //toglilo da E
		if(member(S+{m}, F)) add(m, S); //nuova soluzione
	}
	return S;
}

Ordinando gli elementi di E una volta per tutte otteniamo:

Procedura Greedy(<E,F>, w){
	set S;
	int i;
	S = emptyset();
	sort(E);
	for(i = 1; i <= #E; i++)
		if(member(S+{E[i]}, F)) add(E[i], S);
	
	return S;
}

Costi: se $n= \#E$ allora

• sort(E): $O(n\log n)$
• member(x, F): $C(n)$
• greedy: $O(n\log n + n C(n))$

Matroidi