h1(#subarbore). 'Subarbore':problema/subarbore

Trebuie sa selectam un arbore partial de cost minim care poate avea maxim T frunze. Acesta poate avea maxim T-2 noduri interne. Astfel noi alegem cele T noduri si pe langa ele mai luam inca T-2. Pentru toate aceste posibilitati facem arborele partial de cost minim si selectam minimul.

Observăm că numărul de noduri speciale $T$ este foarte mic, deci problema admite o soluţie exponenţială. Vom construi următoarea dinamică: $D[i][j]$ = dimensiunea minimă a unui subarbore care conţine nodurile speciale corespunzătoare biţilor de $1$ din configuraţia binară a lui $i$, şi are rădăcina în nodul $j$. Avem două metode prin care putem construi un astfel de subarbore:

Complexitate: Combinari(N,T-2)*T*logT

# Unim doi subarbori mai mici care au rădăcina în acelaşi nod $j$ şi acoperă două mulţimi disjuncte de noduri speciale.
# Având un subarbore cu rădăcina în alt nod $x$, adăugăm un lanţ de la nodul $j$ la nodul $x$.
 
Astfel, recurenţa noastră devine:
 
$D[i][j] =$ minim din:
 
* $D[i{~1~}][j] + D[i{~2~}][j]$, unde $i{~1~} or i{~2~} = i$ (submulţimile $i{~1~}$ şi $i{~2~}$ reunite dau submulţimea i) şi $i{~1~} and i{~2~} = 0$ (submulţimile sunt disjuncte). Submulţimile pot fi găsite de exemplu, găsind mai întâi pe $i{~1~}$ astfel încât să fie o submulţime a lui $i$, iar apoi aflăm pe $i{~2~} = i - i{~1~}$;
* $D[i][x] + Dist[j][x]$, unde în matricea Dist avem precalculate distanţele între oricare două noduri din arbore. Această precalculare poate fi făcută aplicând algoritmul Roy-Floyd.
 
Este important ca, pentru orice stare $i$, să calculăm întâi dinamica pentru toate rădăcinile $j$ bazându-ne pe prima parte a recurenţei (unirea a doi arbori) şi abia apoi pe a doua (prelungirea unui lanţ) deoarece rezultatele celei de-a doua recurenţe depind de cele obţinute din prima.
 
Complexitate: $O(3^T^*N + 2^T^*N^2^)$ timp şi $O(2^T^*N)$ memorie.