Sottostruttura ottimale

Da Wikipedia, l'enciclopedia libera.

In informatica, un problema possiede una sottostruttura ottimale se è possibile costruire efficientemente una soluzione ottimale a partire dalle soluzioni ottimali dei suoi sottoproblemi. Questa proprietà è necessaria per poter utilizzare tecniche di programmazione dinamica o algoritmi greedy.

Ricerca del cammino minimo in un grafo utilizzando le sottostrutture ottimali.

Un esempio di sottostrutture ottimali è la ricerca del cammino minimo tra due vertici in un grafo, come illustrato nella figura accanto: prima si trova il cammino minimo dal vertice di arrivo a tutti i vertici vicini a quello di partenza (ripetutamente e con lo stesso metodo); poi si sceglie il cammino che minimizza il peso totale degli archi.

Solitamente, un problema con sottostruttura ottimale viene risolto con un algoritmo greedy. Nel caso in cui il problema possieda anche sottoproblemi sovrapponibili si può usare un algoritmo dinamico.


Problemi con sottostruttura ottimale[modifica | modifica sorgente]

Voci correlate[modifica | modifica sorgente]

informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica