Algoritmi golosi sono una classe di algoritmi che creano localmente ottimale scelte ad ogni passo con la speranza di trovare a ottimo globale soluzione. In questi algoritmi le decisioni vengono prese sulla base delle informazioni disponibili al momento senza considerare le conseguenze di tali decisioni nel futuro. L’idea chiave è selezionare la migliore scelta possibile in ogni passaggio, portando a una soluzione che potrebbe non essere sempre la più ottimale ma spesso è abbastanza buona per molti problemi.
In questo articolo, comprenderemo gli algoritmi greedy con esempi. Esamineremo anche i problemi e le loro soluzioni utilizzando l'approccio avido.
len di stringa in Java
Algoritmi golosi
Tabella dei contenuti
- Cos'è l'algoritmo Greedy?
- Passaggi per la creazione di un algoritmo goloso
- Esempi di algoritmi golosi
- Applicazioni dell'algoritmo Greedy
- Svantaggi/limitazioni dell'utilizzo di un algoritmo Greedy
- Nozioni di base sull'algoritmo Greedy
- Algoritmi Greedy standard
- Problemi golosi sull'array
- Problemi golosi sul sistema operativo
- Problemi avidi sul grafico
- Algoritmo Greedy approssimativo per NP completo
- Avido di casi particolari di DP
- Problemi facili sull'algoritmo Greedy
- Problemi medi sull'algoritmo Greedy
- Problemi difficili sull'algoritmo Greedy
Cos'è l'algoritmo Greedy?
UN algoritmo avido è un tipo di algoritmo di ottimizzazione che effettua scelte ottimali a livello locale in ogni passaggio per trovare una soluzione ottimale a livello globale. Funziona secondo il principio di scegliere l’opzione migliore ora senza considerare le conseguenze a lungo termine.
Per sapere cos'è il metodo greedy e come utilizzare l'approccio greedy, leggi il tutorial fornito sull'algoritmo Greedy:
dialetto ibernato
Passaggi per la creazione di un algoritmo goloso
I passaggi per definire un algoritmo greedy sono:
- Definisci il problema: Indicare chiaramente il problema da risolvere e l'obiettivo da ottimizzare.
- Individua la scelta golosa: Determinare la scelta ottimale a livello locale in ogni fase in base allo stato attuale.
- Fai la scelta golosa: Seleziona la scelta golosa e aggiorna lo stato attuale.
- Ripetere: Continua a fare scelte avide finché non viene raggiunta una soluzione.
Seguendo i passaggi indicati, si può imparare come utilizzare algoritmi greedy per trovare soluzioni ottimali.
Esempi di algoritmi golosi
Esempi di algoritmi greedy sono il modo migliore per comprendere l'algoritmo. Alcuni esempi di vita reale di algoritmi avidi sono:
potatura a-b
- Zaino frazionario : Ottimizza il valore degli oggetti che possono essere inclusi in modo frazionario in uno zaino con capacità limitata.
- Algoritmo di Dijkstra : Trova il percorso più breve da un vertice sorgente a tutti gli altri vertici in un grafico pesato.
- L'algoritmo di Kruskal : Trova l'albero di copertura minimo di un grafico ponderato.
- Codifica di Huffman : Comprime i dati assegnando codici più brevi a simboli più frequenti.
Applicazioni dell'algoritmo Greedy
Ci sono molti applicazioni del metodo greedy in DAA . Alcune importanti applicazioni dell'algoritmo greedy sono:
- Assegnazione di attività alle risorse per ridurre al minimo i tempi di attesa o massimizzare l'efficienza.
- Selezionare gli oggetti più preziosi da inserire in uno zaino con capacità limitata.
- Dividere un'immagine in regioni con caratteristiche simili.
- Ridurre la dimensione dei dati rimuovendo le informazioni ridondanti.
Svantaggi/limitazioni dell'utilizzo di un algoritmo Greedy
Di seguito sono riportati alcuni svantaggi dell’algoritmo Greedy:
- Gli algoritmi avidi potrebbero non trovare sempre la migliore soluzione possibile.
- L’ordine in cui gli elementi vengono considerati può avere un impatto significativo sul risultato.
- Gli algoritmi golosi si concentrano sulle ottimizzazioni locali e potrebbero perdere soluzioni migliori che richiedono la considerazione di un contesto più ampio.
- Gli algoritmi greedy non sono applicabili a problemi in cui la scelta greedy non porta ad una soluzione ottimale.
Nozioni di base sull'algoritmo Greedy:
- Algoritmi Greedy (struttura generale e applicazioni)
- Differenza tra l'algoritmo Greedy e l'algoritmo Divide and Conquer
- Approccio goloso vs programmazione dinamica
- Confronto tra gli algoritmi Greedy, Divide and Conquer e Programmazione Dinamica
Algoritmi Greedy standard:
- Problema di selezione delle attività
- Problema di sequenza dei lavori
- Codifica Huffman
- Decodifica Huffman
- Problema di collegamento idrico
- Swap minimi per il bilanciamento delle parentesi
- Frazione egiziana
- I poliziotti catturano i ladri
- Problema di montaggio degli scaffali
- Assegna i mouse ai buchi
Problemi golosi sull'array:
- Sottoinsieme minimo del prodotto di un array
- Massimizza la somma dell'array dopo K negazioni utilizzando l'ordinamento
- Somma minima del prodotto di due matrici
- Somma minima della differenza assoluta di coppie di due array
- Incremento/decremento minimo per rendere l'array non crescente
- Ordinamento dell'array con inversione attorno al centro
- Somma delle aree dei rettangoli possibili per un array
- Matrice lessicografica più grande con al massimo K scambi consecutivi
- Partizione in due sottoarray di lunghezza k e (N – k) tali che la differenza delle somme sia massima
Problemi golosi sul sistema operativo:
- Algoritmo First Fit nella gestione della memoria
- Algoritmo Best Fit nella gestione della memoria
- Algoritmo di Worst Fit nella gestione della memoria
- Prima pianificazione del lavoro più breve
- Pianificazione dei lavori con due lavori consentiti alla volta
- Programma per l'algoritmo ottimale di sostituzione della pagina
Problemi golosi sul grafico:
- Albero di copertura minimo di Kruskal
- Albero di copertura minimo di Prim
- Albero di copertura minimo di Boruvka
- Algoritmo del percorso più breve di Dijkastra
- Algoritmo di Dial
- Costo minimo per collegare tutte le città
- Introduzione al problema del flusso massimo
- Numero di componenti del singolo ciclo in un grafico non orientato
Algoritmo Greedy approssimativo per NP completo:
- Imposta il problema della copertina
- Problema di imballaggio del contenitore
- Colorazione del grafico
- Problema dei centri K
- Problema delle superstringhe più corte
- Soluzione approssimativa per il problema del commesso viaggiatore utilizzando MST
Avido di casi particolari di DP:
- Problema dello zaino frazionario
- Numero minimo di monete richieste
Problemi facili su Greedy Algoritmo :
- Dividi n in numeri compositi massimi
- Acquista azioni massime se le azioni possono essere acquistate l'i-esimo giorno
- Trova l'importo minimo e massimo per acquistare tutte le N caramelle
- La somma massima possibile è pari alla somma di tre stack
- Dividi il cuboide in cubi in modo che la somma dei volumi sia massima
- Numero massimo di clienti che possono essere soddisfatti con una determinata quantità
- Rotazioni minime per sbloccare una serratura circolare
- Sale minime per m eventi di n lotti con un determinato programma
- Costo minimo per creare un array di dimensione 1 rimuovendo le coppie più grandi
- Costo minimo per l'acquisizione di tutte le monete con k monete extra consentite con ogni moneta
- Incremento minimo di k operazioni per rendere uguali tutti gli elementi
- Trova il numero minimo di banconote e valori che si sommano a un determinato importo
- Sottoinsieme più piccolo con somma maggiore di tutti gli altri elementi
Problemi medi su Greedy Algoritmo :
- Numero massimo di treni per i quali è possibile prevedere la fermata
- Termini minimi di Fibonacci con somma pari a K
- Dividi da 1 a n in due gruppi con una differenza di somma minima
- Carta tagliata nel numero minimo di quadrati
- Differenza minima tra gruppi di dimensione due
- Collega n corde con un costo minimo
- Numero minimo di binari richiesti per una stazione ferroviaria/degli autobus
- Vertici iniziali minimi per attraversare l'intera matrice con determinate condizioni
- Numero palindromico più grande permutando le cifre
- Trova il numero più piccolo con un determinato numero di cifre e la somma delle cifre
- Sottosequenza lessicograficamente più grande tale che ogni carattere ricorre almeno k volte
Problemi difficili su Greedy Algoritmo :
- Numero massimo di elementi che possono essere resi uguali con k aggiornamenti
- Riduci al minimo il flusso di cassa tra gli amici
- Costo minimo per tagliare una tavola in quadrati
- Costo minimo per elaborare m attività in cui i costi di trasferimento
- Tempo minimo per completare tutti i lavori con determinati vincoli
- Ridurre al minimo la differenza massima tra le altezze delle torri
- Bordi minimi da invertire per creare il percorso da una sorgente a una destinazione
- Trova il cubo più grande formato eliminando le cifre minime da un numero
- Riorganizzare i caratteri in una stringa in modo tale che non ce ne siano due adiacenti uguali
- Riorganizzare una stringa in modo che tutti gli stessi caratteri diventino distanti d
Link veloci:
- Impara la struttura dei dati e gli algoritmi | Tutorial DSA
- Le 20 migliori domande per l'intervista sugli algoritmi avidi
- “Problemi pratici” sugli algoritmi golosi
- “Quiz” sugli algoritmi golosi