Алгоритм минимизации суммы произведений листовых значений и их глубины
Я застрял с проблемой информатики, которую я пытаюсь решить. Предположим, у вас есть бинарное дерево (которое не нужно балансировать), в котором каждый узел имеет не более двух дочерних узлов и где только лист может содержать целочисленное значение (корневой и средний узлы не содержат). Нам дан массив значений и нужно построить такое дерево с ограничением:
𝐷𝑚 = мин ∑𝑛𝑖=1 𝐴𝑖 𝑑𝑖
Где 𝐴𝑖 — значение элемента массива 𝑖, а 𝑑𝑖 — глубина этого элемента. Сумма этих продуктов должна быть сведена к минимуму.
Как написать алгоритм со средой выполнения 𝑛log(𝑛), который строит такое дерево?
Спасибо @trincot за редактирование. Как мне использовать Tex в Stack Overflow?
К сожалению, в Stack Overflow нет поддержки Tex.
@user3386109 user3386109 Да, я никогда об этом не думал! Я проверю это
@trincot, но как тебе удалось включить символы Tex в свое редактирование?
Набор символов Юникода большой ;-) И вы можете использовать теги <sub> и <sup>. Просто щелкните ссылку редактирования, как если бы вы собирались редактировать свой пост, и вы увидите, как он был напечатан.
Все значения положительные?
Да, значения должны быть положительными целыми числами
Согласитесь с @user3386109, это либо проблема Хаффмана, либо проблема оптимального бинарного дерева поиска в зависимости от того, допустимо ли переупорядочивать листья относительно массива.
Ответы 1
Как предполагает @user3386109 в комментариях, это именно проблема поиска оптимального кода без префиксов для набора символов с учетом их количества.
Кодирование Хаффмана простое и известное как оптимальное:
- Начните с одноэлементного дерева для каждого значения
- Несколько раз соединяйте два дерева с наименьшим общим значением, пока не останется только одно дерево.
Чтобы доказать, что это оптимально, рассмотрим, что:
- Независимо от формы вашего дерева, самый глубокий уровень всегда будет содержать как минимум 2 листа, у которых есть общий родитель.
- Было бы оптимально присвоить этим листьям два наименьших значения.
Поэтому объединение двух наименьших значений всегда является оптимальным решением. Затем остальные соединения можно выполнить, решив меньший экземпляр той же задачи:
Допустим, вы соединяете значения a и b. Тогда стоимость размещения нового родителя на глубине d становится равной (a+b)*(d+1) = d(a+b) + a + b. Затем из всех возможных решений можно вычесть константу a+b.
Похоже на кодирование Хаффмана, где
A— массив частот.