Introduzione a Greedy Algorithm
Una strategia utilizzata per risolvere i problemi. Greedy Algorithm è considerato uno degli approcci utilizzati per risolvere i problemi. Questo eretico di risoluzione dei problemi si accompagna a fare una scelta che sembra la migliore in quel momento. Questo approccio viene utilizzato al meglio per risolvere problemi di ottimizzazione. I problemi di ottimizzazione possono essere definiti come problemi che richiedono risultati minimi o massimi. Un algoritmo Greedy è un approccio più semplice e diretto che può essere utilizzato per ottenere una soluzione ottimale.
Cos'è Greedy Algorithm?
Greedy Algorithm è una strategia algoritmica utilizzata per fare la migliore scelta facoltativa in una fase molto piccola, producendo alla fine una soluzione globale ottimale. Questo algoritmo seleziona la migliore soluzione possibile in quel momento, indipendentemente dalle conseguenze. Il metodo avido dice che il problema dovrebbe essere risolto nelle fasi in cui ogni input è considerato dato che questo input è fattibile. Poiché questo approccio si concentra solo su un risultato immediato senza riguardo per il quadro generale, è considerato avido.
Definire il concetto di base
Fino ad ora, sappiamo cos'è un algoritmo avido e perché è chiamato così. I seguenti puntatori ti faranno capire l'algoritmo goloso in un modo migliore. Ormai è stato molto chiaro che l'algoritmo avido funziona solo quando c'è un problema; tuttavia, questo approccio è applicabile solo se abbiamo una condizione o un vincolo a quel problema.
Tipi di problemi
- Problema di minimizzazione: ottenere una soluzione a un problema è facile dato che tutte le condizioni sono soddisfatte. Tuttavia, quando questo problema richiede un risultato minimo, viene quindi chiamato Problema di minimizzazione.
- Problema di massimizzazione: un problema che richiede il massimo risultato è noto come problema di massimizzazione.
- Problema di ottimizzazione: un problema si chiama problema di ottimizzazione quando richiede risultati minimi o massimi.
Tipi di soluzioni
- Soluzione fattibile: ora quando si presenta un problema, abbiamo molte soluzioni plausibili a questo problema. Tuttavia, prendendo in considerazione la condizione impostata su quel problema, scegliamo soluzioni che soddisfano la condizione data. Tali soluzioni che ci aiutano a ottenere risultati che soddisfano la condizione data si chiama Soluzione fattibile .
- Soluzione ottimale: una soluzione viene definita ottimale quando è già fattibile e raggiunge l'obiettivo del problema; il miglior risultato. Questo obiettivo potrebbe essere il risultato minimo o massimo. Il punto qui da notare è che qualsiasi problema avrà solo una soluzione ottimale.
L'esempio seguente ti farà capire facilmente il metodo goloso. Diciamo, uno vuole comprare la migliore macchina disponibile sul mercato. Uno dei metodi per scegliere questa auto è analizzando tutte le auto sul mercato. Ora, ciò richiede molto tempo, per semplificare la scelta dell'auto tra quei marchi specifici in cui sono interessati a investire. Classificando ulteriormente questo, si sceglierebbe di nuovo i modelli desiderati osservandone le caratteristiche. Pertanto, l'approccio utilizzato qui è avido in quanto questa soluzione è stata la soluzione ottimale per te considerando che tutti i fattori erano favorevoli a te.
Componenti principali di un avido algoritmo
Ora, quando abbiamo una migliore comprensione di questo meccanismo, esploriamo i componenti principali di un algoritmo avido che lo distingue dagli altri processi:
- Set di candidati: da questo set viene creata una risposta.
- Funzione di selezione: seleziona il miglior candidato da includere nella soluzione.
- Funzione di fattibilità: questa sezione calcola se un candidato può essere utilizzato per contribuire alla soluzione.
- Una funzione oggettiva: assegna un valore a una soluzione completa o parziale.
- Una funzione di soluzione: viene utilizzata per indicare se è stata soddisfatta una soluzione adeguata.
Dove funziona l'algoritmo goloso?
Algoritmo goloso può essere applicato ai problemi di seguito indicati.
- L'approccio Greedy può essere usato per trovare il grafico dell'albero spanning minimo usando l'algoritmo di Prim o Kruskal
- Trovare il percorso più breve tra due vertici è ancora un altro problema che può essere risolto usando un algoritmo avido. Applicare l'algoritmo di Dijkstra insieme all'algoritmo goloso ti darà una soluzione ottimale.
- Huffman Coding
vantaggi
Il più grande vantaggio che l'algoritmo Greedy ha sugli altri è che è facile da implementare e molto efficiente nella maggior parte dei casi.
svantaggi
Greedy Algorithm fondamentalmente costruisce una soluzione parte per parte e sceglie la parte successiva in modo tale da fornire immediatamente la migliore soluzione al problema attuale. Di conseguenza, non vi è alcun rispetto o preoccupazione per le conseguenze dell'attuale decisione presa. Non riconsiderando mai le scelte fatte in precedenza, Greedy Algorithm non riesce a produrre una soluzione ottimale, sebbene fornisca una soluzione quasi ottimale . Problema allo zaino e Problema del commesso viaggiatore sono esempi di problemi in cui l'algoritmo goloso non riesce a produrre una soluzione ottimale.
- Problema allo zaino : il più comunemente noto con il nome di zaino, è un problema quotidiano affrontato da molte persone. Diciamo che abbiamo un insieme di articoli e ognuno ha peso e valore (profitto) diversi da riempire in un contenitore o dovrebbe essere raccolto in modo tale che il peso totale sia inferiore o uguale a quello del contenitore mentre il profitto totale è massimizzato .
Conclusione
Greedy Algorithm è il migliore da applicare quando si ha bisogno di una soluzione in tempo reale e le risposte approssimative sono "abbastanza buone". Chiaramente, un algoritmo avido riduce al minimo il tempo assicurandosi che venga prodotta una soluzione ottimale, quindi è più applicabile da utilizzare in una situazione in cui è richiesto meno tempo. Dopo aver letto questo articolo, si potrebbe avere una buona idea sugli algoritmi golosi. Inoltre, questo post spiega perché è considerato il miglior framework che risponde a quasi tutte le sfide di programmazione e ti aiuta a decidere la soluzione ottimale in un determinato momento.
Tuttavia, per quanto riguarda l'aspetto approssimativo, per applicare la teoria dell'algoritmo avido bisogna lavorare di più per conoscere i problemi corretti. Sebbene sia un concetto scientifico che ha una logica, ha anche un'essenza di creatività.
Articoli consigliati
Questa è stata una guida a What is a Greedy Algorithm. Qui abbiamo discusso il concetto di base, i componenti, il vantaggio e lo svantaggio dell'algoritmo goloso. Puoi anche consultare i nostri altri articoli suggeriti per saperne di più -
- Algoritmo in programmazione
- Che cos'è il Perl?
- Introduzione all'algoritmo
- Che cos'è Agile Sprint?