Sottostruttura ottimale
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.
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.
