irmcast

Irmcast

== include(page="template/taskheader" task_id="irmcast") ==
Sa consideram o retea de comunicatie ce consta din $N$ noduri numerotate de la $1$ la $N$. Nodurile sunt interconectate in asa fel incat reteaua are structura unui arbore avand radacina in nodul $1$. Nodul $1$ doreste sa trimita un mesaj (acelasi mesaj) catre fiecare nod care este o frunza in arbore (adica nu are nici un fiu) - aceasta operatie este cunoscuta sub numele de *multicast*. Un mesaj poate fi transmis numai de la un nod la unul din descendentii acestuia (inclusiv nodul insusi). Fiecare muchie a arborelui are asociat un cost, iar costul transmiterii unui mesaj de la un nod $X$ la unul din descendentii acestuia este suma costurilor muchiilor de pe drumul unic de la $X$ la $Y$ (daca $X = Y$, atunci costul este $0$). Costul total al unei strategii de multicast este egal cu suma costurilor transmiterii fiecarui mesaj.

Pentru a-si indeplini scopul, nodul $1$ va utiliza urmatoarea strategie de multicast: Strategia consta din $K$ runde intermediare. In prima runda, nodul $1$ trimite un mesaj individual catre o submultime de noduri $S{~1~}$, astfel incat fiecare nod frunza din arbore este descendent exact al unui singur nod $X$ din $S{~1~}$ (aceasta inseamna ca orice nod $X$ din $S{~1~}$ nu este descendent al unui alt nod $Y$ din $S{~1~}$). In runda $i$ {$(2 ≤ i ≤ K)$}, fiecare nod X din $S{~i-1~}$ trimite un mesaj individual unei submultimi de noduri $S{~i,X~}$ din subarborele sau., in asa fel incat fiecare nod frunza care este descendent al lui $X$ este descendent al exact unui singur nod din $S{~i,X~}$. Submultimea de noduri $S{~i~}$ este reuniunea multimilor $S{~i,X~}$, pentru fiecare $X$ din $S{~i-1~}$. La final, fiecare nod $X$ din $S{~K~}$ trebuie sa trimita un mesaj individual fiecareui nod frunza care este descendent al lui $X$.

Pentru a-si indeplini scopul, nodul $1$ va utiliza urmatoarea strategie de multicast: Strategia consta din $K$ runde intermediare. In prima runda, nodul $1$ trimite un mesaj individual catre o submultime de noduri $S{~1~}$, astfel incat fiecare nod frunza din arbore este descendent al exact unui singur nod $X$ din $S{~1~}$ (aceasta inseamna ca orice nod $X$ din $S{~1~}$ nu este descendent al unui alt nod $Y$ din $S{~1~}$). In runda $i$ {$(2 ≤ i ≤ K)$}, fiecare nod X din $S{~i-1~}$ trimite un mesaj individual unei submultimi de noduri $S{~i,X~}$ din subarborele sau, in asa fel incat fiecare nod frunza care este descendent al lui $X$ este descendent al exact unui singur nod din $S{~i,X~}$. Submultimea de noduri $S{~i~}$ este reuniunea multimilor $S{~i,X~}$, pentru fiecare $X$ din $S{~i-1~}$. La final, fiecare nod $X$ din $S{~K~}$ trebuie sa trimita un mesaj individual fiecarui nod frunza care este descendent al lui $X$.

Fiind data reteaua de comunicatie, costul fiecarei muchii si numarul de runde intermediare $K$, determinati costul total minim al unei strategii de multicast.
h2. Date de intrare

h3. Explicatie

In prima (si singura) runda intermediara, nodul $1$ trimite mesaje nodului &6& (cu costul $18$) si nodului $2$ (cu costul $10$). Multimea $S{~1~}$ este ${2,6}$. La final, nodul $6$ va trimite un mesaj catre el insusi (cu costul $0$), iar nodul $2$ va trimite mesaje nodului $4$ (cu costul $2$) si nodului $5$ (cu costul $17$). Costul total este $18+10+21+17=66$.

In prima (si singura) runda intermediara, nodul $1$ trimite mesaje nodului $6$ (cu costul $18$) si nodului $2$ (cu costul $10$). Multimea $S{~1~}$ este ${2,6}$. La final, nodul $6$ va trimite un mesaj catre el insusi (cu costul $0$), iar nodul $2$ va trimite mesaje nodului $4$ (cu costul $21$) si nodului $5$ (cu costul $17$). Costul total este $18+10+21+17=66$.

!problema/irmcast?irmcast.jpg!
== include(page="template/taskfooter" task_id="irmcast") ==

2183