Esiste una regola generalizzata per decidere se applicare l'algoritmo greedy su un problema produrrà una soluzione ottimale o no? Ad esempio, alcuni dei problemi più comuni dell'algoritmo, come il problema del "cambio monete" e il problema del "venditore ambulante", non possono essere risolti in modo ottimale dall'approccio avido.
Gli algoritmi greedy non trovano soluzioni ottimali per il qualsiasi problema di ottimizzazione non banale. Questo è il motivo per cui l'ottimizzazione è un intero campo di ricerca scientifica e ci sono tonnellate di diversi algoritmi di ottimizzazione per diverse categorie di problemi.
Inoltre, "algoritmi greedy" è solo una categoria di algoritmi di ottimizzazione, per un dato problema, ci possono essere molti algoritmi greedy diversi, quindi non ha molto senso chiedere a "se si applica l'algoritmo greedy su un il problema produrrà la soluzione ottimale ". Ciò che potrebbe avere senso è chiedere "se applicare un algoritmo greedy specifico " arriverà sempre a una soluzione ottimale, o chiedere se per un dato problema esiste o meno un algoritmo greedy "ottimale". Tipicamente, non esiste un algoritmo "ottimale" avido quando un determinato problema di ottimizzazione ha massimi locali che non sono il massimo globale, perché un algoritmo avido si bloccherà quando raggiungerà un tale massimo locale.
Leggi altre domande sui tag algorithms