Проект Эйлера # 219

Question

Я пытаюсь сделать проект Эйлера с номером 219 , но мне не удается его понять. Я пытаюсь использовать Python, который согласно проекту Euler должен быть в состоянии сделать это в течение минуты! Это заставляет меня думать, что они, возможно, не хотят, чтобы я вычислял каждую отдельную цепочку битов, поскольку это было бы слишком медленно в Python - должен быть алгоритм sub O (n).

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

cost(1) = 1
cost(2) = 5
cost(3) = 11
cost(4) = 18
cost(5) = 26
cost(6) = 35
cost(7) = 44
cost(8) = 54
cost(9) = 64
cost(10)= 74
cost(11)= 85
cost(12)= 96

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

1
01
001
0001
00001
00000

Но это не оптимально для более чем 7 цепочек битов. Кто-нибудь может направить меня в том, что я должен рассмотреть?

Answer 1

Грубая сила не правильный способ сделать это. Это одна из тех проблем, когда, если вы знаете что-то определенное, это не так сложно, но если вы никогда не слышали об этом, это практически невозможно. Это 1001 * деревья Хаффмана .

[Редактировать] При дальнейшем рассмотрении кажется, что вы не можете построить дерево Хаффмана на N узлах с определенными частотами, потому что функция стоимости для строки равна 4 * (# of 1) + (# of 0) , Если бы функцией стоимости была длина строки (или ее кратное число), вы могли бы создать дерево Хаффмана.

Любой кодовый набор без префиксов может быть представлен в виде бинарного дерева, подобного Хаффману, где каждый узел имеет 0 или 2 дочерних узла, а конечные узлы представляют коды. Учитывая дерево с N узлами, мы можем построить дерево с N + 1 узлами следующим образом:

1. Выберите листовой узел с наименьшей стоимостью, где стоимость листового узла составляет 4 * (количество единиц на пути от корня к листу) + (число нулей на пути)
   • Добавить 2 детей в этот узел

Таким образом, если код узла был ранее xxxx, то мы удаляем этот код из нашего кодового набора (поскольку он больше не является листом) и добавляем два кода xxxx0 и xxxx1. Общая стоимость кодового набора теперь увеличилась на

`стоимость (xxxx0) + стоимость (xxxx1) - стоимость (xxxx) = стоимость (0) + стоимость (1) + стоимость (xxxx) = 5 + стоимость (xxxx)

Следовательно, mincost (N + 1) <= mincost (N) + 5 + стоимость (самый дешевый код в лучшем решении для N). Моя теория заключается в том, что это неравенство должно быть равенством, но я пока не смог доказать это. Для всех значений, которые вы перечислили и которые вы использовали для подбора, это утверждение фактически является равенством. </p>

Если это равенство, то для решения проблемы вы должны сделать следующее:

1. Начните с пустого набора кодов, общая стоимость которого равна нулю
   • Итерируя от 1 до 10 ⁹ , выполните:
     1. Найдите самый дешевый код в вашем наборе кодов
   • Разделите этот код на два, добавив 0 и 1
   • Добавьте стоимость этого кода + 5 к общей стоимости

Если вы используете приоритетную очередь , вы сможете сделать это за O (N log N). Это может или не может быть осуществимо, учитывая верхний предел 10 ⁹ .

Answer 2

N = 10 ** 9

t = [0]

для c в xrange (N): м = мин (т) t.remove (м) t.append (т + 1) t.append (т + 4) сумма печати (т), т

Answer 3

Адам: Спасибо за ссылки - это выглядит очень многообещающе! После прочтения статьи в Википедии я не уверен, как учитывается коэффициент 4. Я изо всех сил пытаюсь "сопоставить" проблему Project Euler с алгоритмом. Алфавит должен быть длиной 10 ^ 9 пунктов, но каков будет вес?

Еще одна вещь, которая беспокоит меня, это то, что кодирование Хаффмана в лучшем случае O (n), безусловно, слишком медленное, как я упоминал выше ...

mattiast: Я не думаю, что ваше повторение работает (или я неправильно понимаю!). Моя интерпретация этого:

def cost(n):
    if n == 1: return 1

    m = None
    for k in range(1, n):
        v = cost(k)+cost(n-k)+k+4*(n-k)
        if not m or v < m: m = v

    return m

print(cost(6))

Возвращаемое значение равно 41, тогда как должно быть 35. Тем не менее, если мои значения верны, я не могу найти различия в энциклопедии целочисленных последовательностей ATT.

Answer 4

Оказывается, что O [n * log (n)] не слишком медленный, а сложность памяти, которая примерно равна O (n). Однако предложенный выше алгоритм может быть дополнительно уменьшен до O (n) временной сложности и также низкой сложности памяти. Для этого можно использовать массив x, для которого x [a] = количество числовых значений стоимости a.

Сделанные предположения дают правильный результат для 10 ^ 9, поэтому я думаю, что они верны.

Answer 5

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

Я сообщу об успехе алгоритмов, но рассуждения кажутся мне обоснованными и соответствуют данным (как сказано выше). Однако, поскольку я продолжаю бормотать, должен быть алгоритм sub O (n)! ; -)

Answer 6

Как я решил, вычислял Cost (n) до n = 1000, а затем просто угадывал, как это будет происходить. Если вы посмотрите на различия последовательных значений и используете Энциклопедию целочисленных последовательностей (и немного воображения), вы сможете угадать правило.

Вы можете вычислить маленькие (<= 1000) примеры с помощью динамического программирования, используя повторение <code>Cost(n) = min {Cost(k)+Cost(n-k)+k+4*(n-k) | 0 < k < n}.