Algoritmi greedy applicazioni esame

Algoritmo greedy

Un algoritmo che prende decisioni ottimali locali per trovare una soluzione globale. Si basa sull'idea di scegliere sempre l'opzione migliore in quel momento.

Principio di scelta locale

Ogni passo dell'algoritmo implica una scelta che sembra migliore in quel momento, senza considerare le conseguenze future.

Esempio di problema: zaino

Problema in cui si devono selezionare oggetti da un insieme, massimizzando il valore totale senza superare un peso limite. Si usano pesi e valori per determinare le scelte.

Vero o falso: gli algoritmi greedy garantiscono sempre la soluzione ottimale.

Falso. Gli algoritmi greedy non sempre trovano la soluzione globale ottimale, ma funzionano bene in molti casi specifici.

Differenza tra algoritmo greedy e programmazione dinamica

L'algoritmo greedy fa scelte immediate senza considerare tutte le possibilità, mentre la programmazione dinamica esplora tutte le opzioni per trovare la soluzione ottimale.

Esempio di scelta greedy: cambio

Se si devono restituire 1, 2 e 5 euro come resto, l'algoritmo greedy restituirà prima 5 euro, poi 2 euro e infine 1 euro.

Criteri per applicare greedy

- Struttura del problema - Optimalità locale - Soluzione globale raggiungibile attraverso scelte locali

Algoritmo di Prim

Un algoritmo greedy per trovare l'albero di copertura minimo in un grafo. Aggiunge il nodo più vicino non incluso nell'albero corrente.

Fase di selezione

In ogni iterazione, l'algoritmo seleziona l'elemento migliore secondo un criterio definito. Questa fase è cruciale per ottenere una buona soluzione.

Esempio di problema: intervalli

Nel problema di selezione degli intervalli, si scelgono il maggior numero possibile di intervalli che non si sovrappongono. Si ordinano per fine e si selezionano sequenzialmente.

Vantaggi degli algoritmi greedy

Semplicità Velocità Facilità di implementazione. Spesso più efficienti di altre tecniche, anche se non sempre ottimali.

Condizione di ottimalità

Perché un algoritmo greedy funzioni, deve soddisfare la condizione di ottimalità. Questo implica che ogni scelta locale contribuisce alla soluzione globale.

Problema del cambio monetario

Utilizza algoritmi greedy per determinare il numero minimo di monete per un importo dato.

Albero di copertura minimo

L'algoritmo di Prim trova l'albero di copertura minimo in un grafo pesato con un approccio greedy.

Ciclo di attività

Seleziona attività non sovrapposte, massimizzando il numero totale di attività svolte.

Problema della borsa

Massimizza il valore degli oggetti in base al peso, selezionando gli oggetti in ordine di valore per unità di peso.

Vero o falso: Algoritmi greedy garantiscono sempre la soluzione ottima.

Falso. Non sempre forniscono la soluzione ottima, ma possono essere molto efficienti.

Algoritmo di Dijkstra

Trova il percorso più breve in un grafo senza pesi negativi usando un approccio greedy.

Selezione di intervalli

Un esempio di algoritmo greedy che richiede di selezionare il maggior numero di intervalli non sovrapposti.

Riempimento di knapsack

In un knapsack frazionario, utilizza un approccio greedy per massimizzare il valore totale degli oggetti.

Problema di Huffman

Utilizza un algoritmo greedy per costruire un codice di compressione ottimale basato sulla frequenza dei caratteri.

Vero o falso: Gli algoritmi greedy sono sempre più lenti di quelli dinamici.

Falso. Gli algoritmi greedy possono essere più rapidi grazie alla loro semplicità e alla mancanza di memorizzazione.

Esempio di selezione di attività

Attività: [1-3, 2-5, 4-6, 6-7, 5-9]. Seleziona: 1-3, 4-6, 6-7.

Vantaggi degli algoritmi greedy

- Semplicità - Velocità - Facili da implementare