Algoritmi Greedy

[Nich999]

Salve a tutti. Sto leggendo il Cormen e in particolare ho da poco finito la parte sulla programmazione Greedy.
Ho un dubbio sulla tecnica greedy. In pratica il libro dice che un problema può essere risolto con la tecnica greedy se gode delle seguenti proprietà:
1) sottostruttura ottima
2)scelta golosa

A me invece era parso di capire che le due proprietà sono necessarie solo si richiede che la soluzione del problema sia quella ottima. Se invece si accetta un sub-ottimo del problema di ottimizzazione, le due proprietà non sono richieste.
Ho capito bene? Spero che qualcuno possa chiarirmi se le due proprietà sono condizioni di applicabilità della tecnica o delle condizioni attraverso le quali la tecnica raggiunge una soluzione ottima, ma senza le quali la tecnica possa comunque trovare applicazione...

Grazie

[Nich999]

Nessuno può aiutarmi per piacere?

[hamming_burst]

"Nich999":Salve a tutti. Sto leggendo il Cormen e in particolare ho da poco finito la parte sulla programmazione Greedy.
Ho un dubbio sulla tecnica greedy. In pratica il libro dice che un problema può essere risolto con la tecnica greedy se gode delle seguenti proprietà:
1) sottostruttura ottima
2)scelta golosa

A me invece era parso di capire che le due proprietà sono necessarie solo si richiede che la soluzione del problema sia quella ottima. Se invece si accetta un sub-ottimo del problema di ottimizzazione, le due proprietà non sono richieste.
Ho capito bene? Spero che qualcuno possa chiarirmi se le due proprietà sono condizioni di applicabilità della tecnica o delle condizioni attraverso le quali la tecnica raggiunge una soluzione ottima, ma senza le quali la tecnica possa comunque trovare applicazione...

Grazie

se trovi la sottostruttura ottima e la scelta greedy, allora l'algoritmo greedy restituirà SEMPRE l'ottimo.
Se è sub-ottimo allora non si tratterà di trovare un algoritmo greedy, si intenderà un algoritmo di approssimazione perchè l'ottimo non si può trovare (vedi complessità computazionale o spazio delle soluzioni) oppure perchè anche se l'ottimo è calcolabile, ci si accontenta.

[Nich999]

Grazie mille per la risposta "hamming_burst". Ok quindi era quello che pensavo, cioè se applico un algoritmo greedy ad un problema che gode di sottostruttura ottima e scelta golosa allora la soluzione ottenuta dall'algoritmo sarà sempre ottima.
Ho letto che esistono anche dei problemi di ottimizzazione che non godono della sottostruttura ottima. Sarebbe possibile applicare una tecnica greedy ad un problema di questo tipo? Ovviamente partendo dal presupposto che la soluzione trovata dall'algoritmo sicuramente non sarà ottima.
Purtroppo non riesco a rispondere a qst domanda...nè trovo esempi che mi possano aiutare.

Ancora una volta, grazie in anticipo.

[claudio862]

"Nich999":Ho letto che esistono anche dei problemi di ottimizzazione che non godono della sottostruttura ottima. Sarebbe possibile applicare una tecnica greedy ad un problema di questo tipo? Ovviamente partendo dal presupposto che la soluzione trovata dall'algoritmo sicuramente non sarà ottima.
Purtroppo non riesco a rispondere a qst domanda...nè trovo esempi che mi possano aiutare.

Sì, basta che tu riesca a ridurre il problema ad una sequenza di scelte. Ad esempio, puoi risolvere il problema del commesso viaggiatore in modo greedy: parti da un nodo qualsiasi, ed aggiorni il percorso aggiungendo ogni volta l'arco più breve dall'ultimo nodo ad uno dei nodi non ancora visitati. Ovviamente il risultato non è detto che sia ottimo.
Esistono anche tecniche per migliorare l'algoritmo greedy quando non garantisce l'ottimo, es. GRASP.

[Nich999]

Grazie mille claudio86.