Algorytm - problem

Hej, mam problem z jednym zadaniem z algorytmiki, kompletnie go nie umiem zrobić. Ktoś poradzi, doradzi, wspomoże?

"Rozważmy ukorzenione drzewo, w którego korzeniu pojawia się pewna informacja. W każdej rundzie, wierzchołek posiadający informację, może poinformować jedno swoje dziecko. Pokaż algorytm, który na podstawie struktury drzewa, obliczy dla każdego wierzchołka w jakiej kolejności ma on informować dzieci, tak żeby czas dotarcia informacji do wszystkich wierzchołków drzewa był najkrótszy.

Pozdrwawiam,
Pomidor

Tak na pierwszy rzut oka to algorytm zachłanny -> każdy wierzchołek przekazuje informacje do poddrzewa które jest "wyższe", bo propagacja w tym poddrzewie zajmie więcej czasu, więc sensowniej jest przekazać informacje najpierw tam.
Więc należy sprawdzić jak długa jest ścieżka od danego wierzchołka do liścia i wybrać takie poddrzewo dla którego ta wartość jest największa.

Jak dla mnie to BFS, jeżeli można użyć kolejki. W pierwszej kolejności informujesz dzieci z większą ilością elementów w poddrzewie. Niżej niż najdłuższa ścieżka i tak nie da się zejść, a tak będziesz rozpracowywał drzewo warstwami we wszytkie kierunki na raz (zakładam, że w jednej rundzie może poinformować swoje dziecko więcej niż jeden wierzchołek).

W zasadzie to może zamiast kolejki użyć kolejki priorytetowej/kopca i przetwarzać wierzchołki w zależności od tego jak wysokie poddrzewa ukorzeniają. (przetworzenie: przekazanie informacji dziecku i zakolejkowanie dziecka i siebie po raz kolejny)

W pierwszej kolejności informujesz dzieci z większą ilością elementów w poddrzewie

Też przez chwilę tak myślałem, ale nie, istotna jest wysokość poddrzewa a nie liczba dzieci. Zauważ że propagacja w drzewie pełnym o 3 poziomach (czyli 2+4 = 6 dzieci) trwa krócej (4 ruchy) niż propagacja w drzewie które ma po 1 dziecku na 6 poziomach (5 dzieci) bo tutaj ruchów trzeba wykonać aż 5. Więc jeśli mamy do wyboru takie dwa poddrzewa to należy zacząć propagacje do tego z 5 dzieci które ma wysokość 6, mimo że ma ono mniej wierzchołków niż to poddrzewo pełne.

Shalom napisał(a):

W pierwszej kolejności informujesz dzieci z większą ilością elementów w poddrzewie

Też przez chwilę tak myślałem, ale nie, istotna jest wysokość poddrzewa a nie liczba dzieci.

Tak, masz oczywiście rację. Chodziło mi o wysokość. Zresztą napisałem to w drugiej części z użyciem kopca/kolejki priorytetowej.