Pentru rezolvare se va folosi programare dinamica.
Se
determina pentru fiecare nod NOD din arbore, numarul minim de arce care
trebuie eliminate pentru a obtine un subarbore cu radacina NOD, care
are i noduri (0 <= i <= P), retinandu-le in matricea NR pe linia
NOD a nodului curent. Rezultatul problemei este elementul minim de pe coloana P din matricea NR.
Constructia matricei NR se va face pornindu-se cu nodurile frunza, spre radacina arborelui.
La implementare se vor folosi doi vectori auxiliari: AUX si FINAL care vor retine urmatoarele:
In vectorul FINAL se vor depune rezultatele optime obtinute pe parcurs prin reuniunea subarborilor cu radacini in fiii lui NOD.
AUX va contine rezultatele optime pentru NOD luandu-se in considerare pe rand, rezultatele optime din FINAL.
Valorile din AUX se vor depune in matricea NR pe linia NOD.
Matricea ARB contine pe fiecare linie NOD (1<= NOD <= N) fii lui NOD.
Pasul 1:
Se coboara recursiv in arbore pana in frunze;
Pasul 2:
Daca NOD nu reprezinta frunza, se preiau rezultatele optime pentru primul fiu al nodului curent:
for i:=0 to p do aux[i]:=nr[arb[nod,1],i];
Pasul 3:
Se
determina numarul minim de muchii care trebuie eliminate pentru a izola
un subarbore cu radacina in NOD, ce are I descendenti (0...P-1). Izolez optim un
subarbore cu radacina in NOD avand i descendenti, ca minimul obtinut
prin reuniunea unor subarbori cu radacini in fii lui NOD.
final[i] = min{aux[j]+nr[fiu,i-j]}
unde FIU parcurge toti ceilalti fii ai lui NOD, iar j<=i;
for k:=2 to vec[nod] do begin
fiu:=arb[nod,k];
for i:=0 to p do begin
min:=200;
for j:=0 to i do
if (aux[j]<>200) and (nr[fiu,i-j]<>200) then
if aux[j]+nr[fiu,i-j]<min then min:=aux[j]+nr[fiu,i-j];
final[i]:=min;
end;
for i:=0 to p do aux[i]:=final[i]; {reactualizez}
end;
nr[nod,0]:=1;
for i:=1 to p do nr[nod,i]:=aux[i-1];
Pasul 4:
Se va determina minimul pe coloana P in matricea NR.
Solutia se gaseste in arhiva de teste.
Pentru fiecare test de evaluare s-au acordat 10 puncte.
|