Rilasciato · in miglioramento
Algorithm
Gli algoritmi greedy fanno a ogni passo la scelta localmente migliore senza tornare indietro: scheduling di intervalli, codifica di Huffman, zaino frazionario.
Un algoritmo greedy (o goloso) costruisce la soluzione con una serie di decisioni: a ogni passo sceglie il candidato che sembra migliore secondo una regola fissa e non rimette mai in discussione la scelta. Quasi sempre i candidati vengono ordinati o inseriti in una coda di priorità e accettati uno alla volta, quindi il codice è breve e il tempo di esecuzione è tipicamente O(n log n), dominato dall'ordinamento o dalle operazioni sull'heap.
Quando funziona, l'approccio greedy è la soluzione più veloce e semplice, ma non funziona sempre. Per garantire l'ottimo servono la proprietà della scelta greedy e la sottostruttura ottima, che di solito si dimostrano con un argomento di scambio. Basta un controesempio, come formare 6 con monete da 1, 3 e 4, per capire che serve la programmazione dinamica. Il principio greedy è anche al centro di algoritmi molto usati, come la codifica di Huffman, i cammini minimi di Dijkstra e gli alberi di copertura minimi.
Comincia dallo scheduling di intervalli (selezione di attività) e spiega con un argomento di scambio perché scegliere la riunione che finisce prima è corretto. Poi implementa la codifica di Huffman, lo zaino frazionario e l'assegnazione delle sale con un heap, e prendi l'abitudine di confrontare i risultati greedy con una ricerca esaustiva su input piccoli: è il modo più rapido per scovare una regola sbagliata in un colloquio tecnico.
Deve esistere una soluzione ottima che contiene la prima scelta greedy; è la condizione chiave per la correttezza.
Si dimostra che qualunque soluzione ottima può essere trasformata, elemento per elemento, nella soluzione greedy senza peggiorare.
I candidati sono ordinati per orario di fine, valore per peso o frequenza, oppure estratti da un heap, quindi il costo è di solito O(n log n).
Con sistemi di monete arbitrari o con lo zaino 0/1 la regola greedy sbaglia e occorre passare alla programmazione dinamica.
Il programma sceglie il più grande insieme di riunioni che non si sovrappongono. Ordina le riunioni per orario di fine e accetta una riunione solo se inizia dopo la fine dell'ultima scelta. L'ordinamento costa O(n log n) e la scansione O(n); nell'esempio vengono scelte 4 riunioni su 11.
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.pySei capitoli che ti accompagnano dall'installazione ai concetti chiave di Algoritmi greedy.
Fai domande, condividi la tua esperienza e scambia opinioni su Algoritmi greedy.
Ancora nessuna discussione. Avvia la prima.
0 commenti
Accedi · Accedi per lasciare un commento.
Scrivi tu il primo commento.