Разбиение взвешенного дерева одинаково взвешенные поддеревьев

Question

Входной сигнал:

• корневого дерево с n узлами;
• каждый узел p имеет положительный целочисленный вес w(p);
• У узла может быть более двух детей.

Проблема:

• делят дерево в k поддеревьев/перегородки (очевидно, путем удаления k-1 края);
• поддерево вес W(p) - вес всех узлов в поддереве, укорененном на узле p;
• все поддеревья должны быть взвешены как можно более равномерно - разница между min(W(p)) и max(W(p)) должна быть как можно меньше.

Мне еще предстоит найти подходящий алгоритм для этого. С чего начать? Подсказки, инструкции и псевдокод оцениваются.

Answer 1

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

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

a(b(c,d,e,f),g) 

Вы не можете разбить это на две сбалансированные секции. Лучшее, что вы можете сделать, это удалить край от а до Ь:

а (г) и Ь (с, д, е, е)

Также этот критерий является немного underdefined при к> 2. Что лучше раскол 10,10,10,1 или 10,10,6,5?

Но вы можете придумать метод разбиения деревьев на наиболее сбалансированный способ.

Реализуйте дерево таким образом, чтобы каждый узел содержал количество всех его дочерних элементов. Вы можете добавить это довольно эффективно к любому дереву. (Например, когда вы добавляете узел, вы должны итерировать цепочку родительского узла, увеличивая счетчик. Удалите узел и вы итерации вычитаете из счета).

Затем, начиная с корня, итерации вниз, в ширину в первом порядке пока вы не найдете набор узлов, которые доминируют над дочерними узлами таким образом, который наиболее сбалансирован. У меня нет алгоритма для этого наготове, но я думаю, что вы можете найти его довольно легко.

Я думаю, что где-то, когда вы хотите разделить на k поддеревьев, вы создаете массив из корней k деревьев. Один из этих узлов всегда должен быть корнем текущего дерева, а затем итерации, ища узлы для замены на кандидатах k-1, которые улучшают разбиение. Вам нужно какое-то условие завершения, в котором вы не будете взаимодействовать с каждым листовым узлом. Например. никогда не имеет смысла подразделять что-либо на самый большой узел-кандидат.