File PDF .it

Condividi facilmente i tuoi documenti PDF con i tuoi contatti, il Web e i Social network.

Inviare un file File manager Cassetta degli attrezzi Ricerca PDF Assistenza Contattaci



01 greedy .pdf



Nome del file originale: 01 - greedy.pdf

Questo documento in formato PDF 1.4 è stato generato da Writer / LibreOffice 3.6, ed è stato inviato su file-pdf.it il 11/11/2014 alle 16:30, dall'indirizzo IP 193.205.x.x. La pagina di download del file è stata vista 789 volte.
Dimensione del file: 90 KB (4 pagine).
Privacy: file pubblico




Scarica il file PDF









Anteprima del documento


GREEDY APPROACH
Problema : “Selezione attività”
INPUT : una lista di N attività con i relativi orari di inizio e di fine.
Vogliamo determinare il numero massimo di attività che possono essere svolte senza
sovrapposizioni. La lista di attività è ordinata rispetto gli orari di fine.
Soluzione
Una soluzione intuitiva al problema può essere data dal seguente algoritmo :
1) Prendiamo la prima attività nella lista di input e inseriamola nella lista “soluzione parziale”
(inizialmente vuota). Manteniamo quindi l'informazione sull'ultima attività inserita in questa lista
che per il momento risulta essere la numero uno.
2) Continuiamo considerando in maniera sequenziale le altre attività nella lista di input, dalla
seconda in poi; quando ne troviamo una compatibile con l'ultima attività inserita nella lista
“soluzione parziale”, inseriamo anche lei in questa lista e aggiornando l'informazione sull'ultima
attività inserita.
3) Si ripete il secondo passaggio finché non ci sono più attività compatibili che possono essere
inserite (si è arrivati alla fine della lista di input). La soluzione è rappresentata dal numero di attività
presenti nella lista soluzione parziale.
NB : Un'attività B è compatibile con un'attività A se B inizia dopo che è finita A.
Nel caso in cui non si disponga di una lista di attività ordinata rispetto gli orari di fine, possiamo
aggiungere un passaggio iniziale in cui tramite qualche algoritmo di ordinamento si ordina la lista in
modo da proseguire normalmente con i passaggi precedentemente descritti.
Esempio
Per semplicità, in questo esempio gli orari di inizio e di fine attività sono stati visti come interi.
Data la seguente lista di attività in input, vediamo i passaggi per la risoluzione.
Attività Inizio

Fine

1

1

4

2

3

5

3

0

6

4

5

7

5

3

8

6

5

9

7

6

10

8

8

11

9

8

12

10

2

13

11

12

14

Nella figura di destra, le attività che determineranno la soluzione finale sono in rosso.
- inserisco l'attività numero 1 nella lista soluzione parziale → {1}
- l'attività 2 non è compatibile con la numero 1 (l'ultima inserita nella lista soluzione parziale)
- l'attività 3 non è compatibile con la numero 1
- l'attività 4 è compatibile con la numero 1, la inserisco nella lista soluzione parziale → {1,4}
- l'attività 5 non è compatibile con la numero 4 (l'ultima inserita nella lista soluzione parziale)
- l'attività 6 non è compatibile con la numero 4
- l'attività 7 non è compatibile con la numero 4
- l'attività 8 è compatibile con la numero 4, la inserisco nella lista soluzione parziale → {1,4,8}
- l'attività 9 non è compatibile con la numero 8 (l'ultima inserita nella soluzione parziale)
- l'attività 10 non è compatibile con la numero 8
- l'attività 11 è compatibile con la numero 8, la inserisco nella lista soluzione parziale → {1,4,8,11}
- non ci sono più attività da considerare, la soluzione al nostro problema è la cardinalità della lista
“soluzione parziale” fin qui costruita, ovvero 4.
Correttezza dell'algoritmo
Questo algoritmo porta sempre alla soluzione ottima per qualsiasi input ? Si! Perchè ?
Dobbiamo dimostrarlo, iniziamo con una definizione.
Dato un intervallo di tempo [i,j] si definisce Aij come l'insieme delle attività che possono essere
svolte in questo intervallo e sia Sij un sottoinsieme di Aij che rappresenta l'insieme di attività che
possono essere svolte senza sovrapposizioni (sempre in relazione all'intervallo [i,j]).
Chiameremo Sij insieme ottimo per [i,j].
NB : dato un intervallo di tempo, mentre Aij è univocamente determinato, ci possono essere più
rappresentazioni per Sij, però tutte con la medesima cardinalità.
Con questa definizione se n è il tempo di fine dell'ultima attività nella lista di input, banalmente A0n
è l'insieme di tutte le attività e la cardinalità dell'insieme S0n determina la soluzione al problema.
Proseguiamo con considerazioni di carattere generale, consideriamo un determinato insieme Sij e sia
k l'attività appartenente al relativo insieme Aij che abbia il minor tempo di fine; ammettiamo che k
non faccia parte di Sij. Proviamo a sostituire k con l'attività con il minor tempo di fine in Sij;
sicuramente non peggioriamo la situazione in quanto k finirà prima delle restanti attività in Sij e
quindi la compatibilità non verrà compromessa. Con la sostituzione dunque otteniamo un altro
insieme con la stessa cardinalità e quindi ottimo. Possiamo concludere a questo punto che esiste
sempre un insieme ottimo per Aij che contiene l'attività con il minor tempo di fine.
Grazie a questa proprietà, partendo dall'intervallo [0,n] possiamo iniziare a costruire la nostra
soluzione parziale proprio come fa l'algoritmo, cioè prendendo sempre l'attività compatibile con il
minor tempo di fine. Sia m il tempo di fine dell'attività appena inserita nella lista parziale,
continueremo sfruttando la proprietà per l'intervallo [m,n] fino a considerare tutte le attività e
arrivando quindi ad una soluzione ottima.

Problema : “Monete”
INPUT : un insieme di monete di diverso valore e un importo x.
Vogliamo minimizzare il numero di monete da utilizzare la cui somma dei valori sia uguale a x.
Si suppone che nell'insieme di monete è sempre presente la moneta di valore unitario (1 centesimo).
Soluzione
Una soluzione intuitiva al problema può essere data dal seguente algoritmo :
1) Inizialmente poniamo un intero “resto” uguale all'importo e un intero “contatore” uguale a 0.
2) Utilizziamo la moneta con valore maggiore possibile; contatore viene aumentato di uno mentre
resto viene decrementato rispetto al valore della moneta utilizzata.
3) Si ripete il secondo passaggio finché l'intero resto non sarà uguale a zero; la soluzione al
problema è il valore di contatore.
Esempio
Abbiamo a disposizione monete da 100,10,5 e 1 centesimo, l'importo da raggiungere è di 127.
- la moneta più grande utilizzabile è quella da 100 centesimi, contatore → 1, resto → 27
- la moneta più grande utilizzabile è quella da 10 centesimi, contatore → 2, resto → 17
- la moneta più grande utilizzabile è quella da 10 centesimi, contatore → 3, resto 7
- la moneta più grande utilizzabile è quella da 5 centesimi, contatore → 4, resto 2
- la moneta più grande utilizzabile è quella da 1 centesimo, contatore → 5, resto 1
- la moneta più grande utilizzabile è quella da 1 centesimo, contatore → 6, resto 0
- il nostro resto è 0, quindi la soluzione al nostro problema è 6.
Correttezza dell'algoritmo
Questo algoritmo porta sempre alla soluzione ottima per qualsiasi input ? No! Perchè ?
Dividiamo il nostro problema in due casi mutuamente esclusivi:
1) Abbiamo a disposizione un insieme di monete in cui ogni moneta è multipla di tutte le sue
monete più piccole.
In questo caso l'algoritmo porta in maniera banale sempre alla soluzione ottima; un multiplo riduce
sempre il numero di monete utilizzate al minimo.
2) Abbiamo a disposizione un insieme di monete in cui almeno una moneta non è multipla di tutte le
sue monete più piccole.
In questo caso, a seconda dell'importo da raggiungere, si può non arrivare alla soluzione ottima; ad
esempio prendiamo l'insieme di monete da 100,25,10 e 1 centesimo in cui appunto la moneta da 25
non è multipla della moneta da 10. Vediamo cosa succede con i seguenti due importi :
Con importo uguale a 127 si ottiene l'ottimo : 4 monete (una da 100, una da 25 e due da 1).
Con importo uguale a 134 si ottiene : 11 (una da 100, una da 25 e nove da 1) che non è l'ottimo in
quanto avremmo potuto utilizzare 8 monete (una da 100, tre da 10 e quattro da 1).

LA FAMIGLIA DEGLI ALGORITMI GREEDY
Gli algoritmi descritti per la risoluzione dei due problemi fanno parte della famiglia degli algoritmi
di tipo “Greedy”(in italiano algoritmi “golosi”).
Possiamo applicare questa tecnica quando per la risoluzione dobbiamo effettuare una serie di scelte
non ripudiabili. L'algoritmo parte da una soluzione parziale, di solito vuota, estendendola man mano
a seconda della scelta appena effettuata.
ATTENZIONE! : Questa tecnica può non portare alla soluzione ottima, ma solo ad una buona
soluzione.
Se non vogliamo accontentarci di una soluzione non ottima, dobbiamo inizialmente verificare la
correttezza dell'algoritmo a seconda dei vari tipi di input, come è stato mostrato con le
considerazioni alle soluzioni dei due problemi proposti, tramite ragionamenti di stampo logicomatematico.
Quando l’algoritmo tenta di estendere una soluzione parziale non lo fa considerando tutte le
possibili estensioni ma solamente quelle che possiamo chiamare estensioni locali. Fra tutte le
estensioni locali l'algoritmo sceglie la più conveniente o “golosa”, ovvero quella che sembra la più
promettente per raggiungere l'ottimo.
Nel problema 1 l'insieme delle estensioni locali era l'insieme delle attività compatibili con l'ultima
attività inserita nella soluzione parziale, l'algoritmo procedeva in modo goloso selezionando quella
con il minor tempo di fine.
In maniera analoga, nel problema 2 l'insieme delle estensioni locali era l'insieme di monete
utilizzabili, quelle di valore minore o uguale al resto, l'algoritmo procedeva in modo goloso
selezionando quella di maggior valore.
Ogni scelta effettuata quindi non verrà mai più ripresa in esame, questo ci porta a due grandi
vantaggi :
- l'implementazione dell'algoritmo è di semplice stesura.
- gli algoritmi prodotti godono sempre di buona efficienza in tempo, dato che praticamente il
numero di passaggi necessari a trovare la soluzione al problema è conforme alla grandezza
dell'input.
Uno grande svantaggio invece può nascere quando si deve verificare la correttezza dell'algoritmo;
può capitare infatti che non si riesca a concepire una dimostrazione logica che permetta di
procedere alla stesura dell'algoritmo per due motivi :
- perché la dimostrazione richiede conoscenze e capacità di ragionamento logico-matematico.
- perché si vuole attuare una strategia del tutto sbagliata (e quindi non esiste una dimostrazione sulla
correttezza).


01 - greedy.pdf - pagina 1/4
01 - greedy.pdf - pagina 2/4
01 - greedy.pdf - pagina 3/4
01 - greedy.pdf - pagina 4/4

Documenti correlati


Documento PDF 01 greedy
Documento PDF heuristics
Documento PDF 8x8 64
Documento PDF 8x8 64 1
Documento PDF 8x8 64 2
Documento PDF 2008


Parole chiave correlate