Data:
- un elenco di "foglie" che hanno ciascuna un costo,
- il costo per la creazione di un 'edge'
- Il vincolo che un nodo struttura costruito può avere al massimo due figli.
Ora vogliamo trovare l'albero con il costo massimo più basso quando si sommano i costi dei bordi da ciascuna foglia fino al nodo radice.
Quando si tenta ingenuamente di costruire tutti i diversi alberi binari possibili, si vede che questo richiede% passiO(C(n)), dove C (n) è il n -th Catalan Number
Una semplice soluzione di programmazione dinamica è isomorfo con la risoluzione del problema di ordinamento della moltiplicazione della catena di maglie , ma riempiendo la matrice utilizzata da questo algoritmo richiederà una quantità ridicola di memoria.
Mi aspetto che sia possibile trovare una soluzione che sia molto più efficiente (sia in termini di tempo che di memoria).
Come puoi scoprire quale sarebbe la struttura ad albero ottimale?
Come si può determinare quale sarebbe il costo più alto (costo del nodo foglia + costo degli spigoli tra esso e il nodo radice) in tale albero?