Раскрасьте дерево так, чтобы вес, умноженный на время, был минимальным

Question

Учитывая двоичное дерево, с n узлами и каждым узлом, имеющим вес wi (i обозначает вес для i-го узла), мы должны раскрасить каждый узел дерева.Стоимость окраски узла равна весу узла, умноженному на время его окраски.Время начинается с 1 и увеличивается на 1, когда вы продолжаете окрашивать узлы.При окраске обязательно, чтобы родитель окрашивался перед ребенком.Рассчитать минимальную стоимость раскраски всего дерева?

Answer 1

То, что вы можете сделать, это то, что вы можете пройти уровень дерева за уровнем.Сортируйте весь уровень, затем раскрасьте каждый из узлов таким образом, чтобы их сумма была минимальной.Повторите это для каждого уровня.

Для иллюстрации, если у вас есть следующее дерево:

      4
     / \
    3   7
       / \
      1   9
     /
    2

1. Получить первый уровень: 4.
2. Сортировкаэто в порядке убывания.и умножить на time: 4*1.Стоимость = 4.
3. Получить 2-й уровень: 3 7.
4. Сортировать по убыванию.и умножьте каждый узел на time: 7*2 + 3*3 = 23.Стоимость = 4 + 23 = 27.
5. Получить 3-й уровень: 1 9
6. Сортировать по убыванию.и умножьте каждый узел на time: 9*4+1*5 = 41.Стоимость = 27 + 41 = 68.
7. Получить 4-й уровень: 2
8. Сортировать в порядке убывания.и умножьте каждый узел на time: 2*6 = 12.Стоимость = 68 + 12 = 80.

Как пройти бинарное дерево в порядке уровней.Пожалуйста, обратитесь это: https://www.geeksforgeeks.org/level-order-tree-traversal/

Answer 2

В исследовательской литературе эта проблема заключается в планировании заданий с приоритетом на одной машине, чтобы минимизировать общее взвешенное время выполнения.Есть алгоритм O (n log n) для параллельно-последовательного приоритета из-за Лоулера.Позвольте мне резюмировать это ниже в особом случае деревьев.

Если бы не было требования, чтобы родители были запланированы раньше, чем их дети, то мы бы хотели раскрашивать в порядке увеличения веса.Процедура Лоулера работает снизу вверх, объединяя узлы в так называемые составные узлы.Выходными данными в каждом узле x является набор составных узлов, который (1) содержит каждого потомка x ровно один раз (2) может быть окрашен в неубывающем порядке веса (где вес составного узла - это средний вес егосоставляющие узлы) без нарушения ограничений по порядку «родитель-потомок».

В каждом узле x в порядке следования сначала объедините наборы из дочерних элементов x.Хотя в объединенном наборе существует составной узел, который по крайней мере такой же тяжелый, как x, извлеките этот узел и замените x составным, состоящим из x и этого узла.Для эффективности представьте наборы как объединяемую очередь приоритетов (например, кучи сопряжения).

Наконец, сортируйте составные узлы и сведите их в список.