Как максимизировать вес дерева, удалив поддеревья

Для этого существует простой рекурсивный алгоритм. Наиболее выгодная обрезка, которую вы можете выполнить для дерева, — это либо выполнить наиболее выгодную обрезку для всех его прямых поддеревьев, либо просто удалить все дерево. Это можно перевести непосредственно в код.

Предполагая, что дерево было преобразовано в структуру данных, где каждый узел имеет атрибут value, представляющий значение узла, и атрибут children, хранящий список дочерних узлов узла, следующая функция Python вычислит максимальную прибыль:

def max_profit(node):
    return max(
        -X,
        node.value + sum(map(max_profit, node.children)))

с двумя параметрами в вызове max, представляющими выбор: либо удалить все дерево в корне, либо сохранить корень и обработать поддеревья.

Идея состоит в том, чтобы проанализировать дерево и посмотреть, какое поддерево можно удалить, чтобы прибыль увеличилась по сравнению с его начальным состоянием. Сделайте этот анализ для каждого узла, прежде чем что-либо удалять. Затем удалите поддеревья, которые больше всего увеличивают прибыль. Мы можем сделать это в два прохода:

1) Выполняя обход дерева в глубину (сначала листья, затем медленно возвращаясь к корню), вычислите прирост прибыли каждого узла как G(i)=-A(i)+G(j)+G(k)+..., где i — текущий узел, а j,k,... — дочерние узлы. Другими словами, прирост прибыли — это добавленная стоимость, если мы удалим текущий узел.

Во время того же обхода также вычислите максимальный прирост прибыли узла и его дочерних элементов. Это скажет нам, выгоднее ли удалить узел или выгоднее удалить поддерево этого узла. Мы рассчитываем максимальный прирост прибыли как M(i) = max(G(i),M(j),M(k),...), где i,j,k,... определены, как указано выше. Если дочерний элемент не существует, просто удалите его из уравнения max.

2) Обходя дерево в ширину, удаляем узел i (и его поддерево), если G(i) == M(i) и G(i) >= X.

def compute_gain(node):
    map(compute_gain, node.children)
    node.gain = -node.value + sum([c.gain for c in node.children])
    node.max_gain = max(node.gain, max([c.max_gain for c in node.children]))

def prune_tree(node):
    if node.gain >= X and node.max_gain == node.gain:
        k += 1
        return False
    node.children = [c for c in node.children if prune_tree(c) == True]