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

La inceput se ruleaza algoritmul roy floyd pentru a determina toate drumurile posibile de cost minim si formam din ele un graf complet.

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:

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 submultimile formate din multimea celor T-2 selectate facem arborele partial de cost minim pe graful complet si selectam minimul.

# 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$.

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

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.