h2(#treesearch). 'Tree Search':problema/treesearch

Problema se rezolva prin programare dinamica. Presupunem ca agatam arborele intr-un nod oarecare. Folosind DFS, calculam P[$i$] = costul maxim al unui drum care contine drept capat nodul i, si contine doar noduri din subarborele lui i. Relatia de recurenta se determina relativ simplu: P[$i$] = C[$i$], daca $i$ este nod terminal, iar P[$i$] = max ( C[$i$], C[$i$] + P[$k$] ), pentru $k$ - adiacent a lui $i$ ( diferit de tatal lui $i$ ). De asemenea, mai trebuie calculat si un vector de tati: tata[x] = tatal nodului x. Avand acesti vectori calculati, mai trebuie sa determinam drumul de cost maxim care are drept extremitate nodul i, si pleaca "in sus". Astfel, notam cu T[$i$] - costul maxim al unui drum care pleaca din i, "in sus". Pentru a calcula acest vector, ne trebuie cate o parcurgere DF pt fiecare fiu al radacinii. Presupunem ca dorim sa calculam T[] pentru subarborele $k$ al radacinii (asadar, $k$ este fiu al radacinii). Trebuie sa procedam astfel:

Problema se rezolva prin programare dinamica. Presupunem ca agatam arborele intr-un nod oarecare. Folosind DFS, calculam P[$i$] = costul maxim al unui drum care contine drept capat nodul i, si contine doar noduri din subarborele lui i. Relatia de recurenta se determina relativ simplu: P[i] = C[i], daca i este nod terminal, iar P[$i$] = max ( C[$i$], C[$i$] + P[$k$] ), pentru $k$ - adiacent a lui $i$ ( diferit de tatal lui $i$ ). De asemenea, mai trebuie calculat si un vector de tati: tata[x] = tatal nodului x. Avand acesti vectori calculati, mai trebuie sa determinam drumul de cost maxim care are drept extremitate nodul i, si pleaca "in sus". Astfel, notam cu T[$i$] - costul maxim al unui drum care pleaca din i, "in sus". Pentru a calcula acest vector, ne trebuie cate o parcurgere DF pt fiecare fiu al radacinii. Presupunem ca dorim sa calculam T[] pentru subarborele $k$ al radacinii (asadar, $k$ este fiu al radacinii). Trebuie sa procedam astfel:

* T[$radacina$] se initializeaza cu max ( C[$radacina$], P[$j$] ), unde $j$ este un fiu al radacinii, diferit de $k$.
* Aplicam un algoritm de tip DF, avand ca punct de plecare $k$. Pentru fiecare nod x pe care il parcurgem (avand tatal t) calculam T[$x$] = max ( C[$x$], C[$x$] + T[$t$], C[$x$] + C[$t$] + P[$j$]), unde $j$ este un fiu al lui $t$, diferit de $i$ si diferit de $tata[$t$]$.