Lezione 7.2: alberi, etichette, condizioni di Bellman
Aggregazione dei criteri
Il problema dei cammini di costo minimo da un nodo a tutti gli altri: formulazione e proprietà, alberi orientati radicati come soluzioni ottime. Capire se un albero è ottimo attraverso le etichette: già nei fatti un algoritmo (su un esempio, senza dettagli). Condizioni di Bellman e teorema di Bellman, con dimostrazione del lemma critico: il nostro primo esempio di condizioni di ottimalità [p. 54-56].