Optimální vyhledávací strom
(
Dynamické Programování)
Minimalizuje
\sum_{i=1}^n h(a_i)\cdot f(a_i) pro daná
f — frekvence hledání prvků, kde
h je hloubka daného prvku.
P
n,k := strom s
n po sobě jdoucí prvky počínaje
k.
Vždy rozmyslím, co můžu dát do kořene, co jako syny (3 možnosti) a syny už mám spočtené. Pozor na to, že se mi mění hloubka podřešení, když je vložím jako syny.
Zbytek si domyslete podle ostatních úloh spadajících pod
Dynamické Programování.
