Сбалансированный алгоритм ветвления

Question

Итак, я делаю школьное задание, которое выглядит следующим образом

и я совершенно не знаю, с чего начать. Может ли кто-нибудь указать мне правильное направление?

Моя идея отправной точки состояла бы в том, чтобы сначала вычислить значение расхождения узла root (абсолютное значение суммы указанных значений листа), а затем (каким-то образом) проверить, существует ли расхождение значение выше значения root, в противном случае значение root является минимально возможным несоответствием входных данных. Я на правильном пути? В настоящее время я не могу продвинуться дальше этого.

Важное примечание: построенное дерево должно "уважать" заданный порядок значений. Например, если входное значение (5, 0, 0, -5), вы не можете построить свое дерево, сначала объединив первый и последний элементы в дерево. Более формально: на каждом внутреннем узле входные значения, появляющиеся как листья в левом поддереве этого узла, должны все приходить до того, как входные значения, появляющиеся как листья в правом поддереве.

Спасибо!

Answer 1

Для данного набора a [1] ... a [n], каждый из которых соответствует листовому узлу, ясно, что несоответствие каждого дерева ограничено снизу:

B(x[]) = max (abs(x[1]),...,abs(x[n]), abs(sum))

Где sum, сумма всех x[i], соответствует весу узла root каждой сборки дерева из x[i].

Цель здесь просто показать, что всегда можно построить дерево, несоответствие которого равно этой нижней границе.

Это реализуется в два этапа.

На первом этапе, если два соседних узла имеют разные знаки, мы просто объединяем их. Это соответствует замене этих двух узлов новым узлом, вес которого является суммой двух весов. Абсолютное значение этого веса меньше максимума абсолютных значений двух входных весов, поэтому меньше, чем предел. Мы повторяем этот процесс до тех пор, пока не получим только узлы (новый набор), веса которых имеют один и тот же знак.

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

Наконец, мы получаем дерево, вес которого все меньше или равен нижней границе.

Пример:

-1 -5 4 -2      -> merge -5 and 4
-1 -1 -2        -> all signs equal, 2nd step: the maximum node of this sub-array correspond to the sum -4

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

-1 -5 4 -2      -> merge 4 and -2
-1 -5 2         -> merge -5 and 2
-1 -3           -> all signs equal, 2nd step: sum equals -4

Answer 2

Прежде всего, обратите внимание, что это удобная рекурсивная проблема: всякий раз, когда вы объединяете смежные узлы, вы уменьшаете проблему на один узел. Состояние проблемы может быть полностью выражено в виде списка значений и максимального значения; Ваша заданная проблема может быть отправлена ​​в функцию решения как

a = [-1, -5, 4, -2]
balance(a, max(max(a), abs(min(a))))

Проще говоря,

balance(a, 5)

Правое решение этой проблемы будет развиваться следующим образом:

[-1, -5, 4, -2], 5
[-1, -1, -2], 5    * see note below
[-1, -3], 5
[-4], 5

• отсюда, соединение не имеет значения, так как не осталось ни одного пути, который мог бы превысить первоначальное расхождение в 5.

---

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

-5 1 1 -5 1 1 -5 1

Нам не нужно кричать от идеи понижения ниже -5: итоговое значение равно -10, поэтому мы не можем избежать такого высокого расхождения. Это может быть более поздней тонкой настройкой

---

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

Например:

4 -5 1 1 2 -1 -1 -6 -2 -1 2 -3 2 2

расхождение составляет 6 около середины. Разделите последовательность в этой точке на две отступающие подпоследовательности с их текущими суммами:

seq: -1 -1 2 1 1 -5 4
sum: -1 -2 0 1 ...

seq: -2 -1  2 -3  2 2
sum: -3 -3 -1 -4 -2 0

Левая сторона (обратная, в порядке от элемента -6) достигает контрбалансовой суммы ( противоположный знак, поэтому их объединение уменьшит расхождение) в четвертом элементе: -1 -1 2 1 - самая короткая подпоследовательность с положительной суммой. Повторите для [1 2 -1 -1], 6 как подзадачу (поддерево для рассмотрения). Это вернет поддерево, такое как ((1 (2 -1) )-1), со значением 1. Теперь список значений:

4 -5 1 1 -6 -2 -1 2 -3 2 2
       ^ this is the sub-tree we just reduced.

Теперь у нас есть значение уравновешивания, смежное с наибольшим расхождением; это означает, что следующая операция состоит в объединении этих двух значений:

4 -5 1  -5  -2 -1 2 -3 2 2

Продолжайте аналогичным образом здесь. Обратите внимание, что свобода возврата к значению 6 может - в некоторых случаях - ускорить поиск решения.

Продолжая по частям, мы свернем это значение до

-1 -4     -2 -1 2 -3 2 2

Это будет прогрессировать справа, постепенно уменьшаясь ...

-1 -4     -2 -1 2 -3 2 2
-1 -4     -2 -1 2  -1  2
-1 -4     -2   1   -1  2
-1 -4       -1     -1  2
-1 -4       -1        1
-1 -4             0

Здесь мы окончательно выползли обратно к наибольшему оставшемуся значению в полном списке ...

-1 -4 0
-1 -4
-5

Этого достаточно, чтобы заставить вас двигаться?