Вычисление наименьшего возможного дерева

Question

Учитывая набор узлов, как я могу построить дерево, которое связывает все узлы таким образом, чтобы минимизировать max (max (степень), max (глубина)) ?

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

Однако это не является минимальным, поскольку max (градус) == 4 и max (глубина) == 1, лучшее дерево будет:

, который имеет max (градус) == 2 и max (глубина) == 2

Редактировать :: Алгоритм не должен быть быстрым, но важно вычислить абсолютно оптимальное дерево.

Answer 1

Идти в противоположном направлении.Для заданной степени и глубины максимальное количество узлов представляет собой сумму = 1 + степень + степень ^ 2 + ... + степень ^ глубина.Это целочисленная последовательность A031973 .Вы можете рассчитать его каждый раз или просто сохранить первый набор значений.В любом случае, вы ищете минимальное значение, которое больше, чем количество ваших узлов, и вычисляете соответствующий D = градус = глубина

. Когда вы знаете свой D, просто заполните дерево любым удобным вам способом, сего границы.

Answer 2

Максимальное количество узлов в дереве с глубиной == градус равно n = Суммарный градус ^ k для k = 0 до степени-1. На самом деле эта сумма является геометрическим рядом. Таким образом, его значение равно (градус ^ градус-1) / (градус-1), что, вероятно, гораздо быстрее вычислить. (хотя скорость не имеет значения ;-)) Но вы не можете решить уравнение n = (градус ^ градус-1) / (градус-1) алгебраически, поэтому вам придется хранить предварительно рассчитанные значения суммы, а затем выбрать значение степени, которое дает наименьшее возможное значение, еще большее / равное по номеру