EDIT: уточненное описание проблемы
Существует ли быстрый алгоритм, решая следующую задачу?
И, также для расширенной версии этой проблемы
заменяя натуральные числа на Z/(2 ^ n Z)? (эта проблема была слишком сложной, чтобы добавить больше вопросов в одном месте, IMO.)
Проблема:
Для данного набора натуральных чисел, таких как {7, 20, 17, 100}, требуется алгоритм возвращает кратчайшую последовательность дополнений, вычислений и вычислений мощности все заданные числа. Каждый элемент последовательности (правильное) уравнение соответствует следующему шаблону:
<number> = <number> <op> <number>
где < число > представляет собой число natual, <op> является одним из {+, *, ^}.
В последовательности каждый операнд <op> должен быть одним из
- 1
- числа, которые уже появились в левой части равенства.
Пример:
Input: {7, 20, 17, 100}
Output:
2 = 1 + 1
3 = 1 + 2
6 = 2 * 3
7 = 1 + 6
10 = 3 + 7
17 = 7 + 10
20 = 2 * 10
100 = 10 ^ 2
Я написал алгоритм обратного слежения в Haskell. он работает для небольшого ввода, например, выше, но мой реальный запрос случайно распределенных ~ 30 номеров в [0,255]. для реального запроса следующий код занимает от 2 до 10 минут на моем ПК.
(Фактический код, очень простой тест)
Мой текущий (псевдо) код:
-- generate set of sets required to compute n.
-- operater (+) on set is set union.
requiredNumbers 0 = { {} }
requiredNumbers 1 = { {} }
requiredNumbers n =
{ {j, k} | j^k == n, j >= 2, k >= 2 }
+ { {j, k} | j*k == n, j >= 2, k >= 2 }
+ { {j, k} | j+k == n, j >= 1, k >= 1 }
-- remember the smallest set of "computed" number
bestSet := {i | 1 <= i <= largeNumber}
-- backtracking algorithm
-- from: input
-- to: accumulator of "already computed" number
closure from to =
if (from is empty)
if (|bestSet| > |to|)
bestSet := to
return
else if (|from| + |to| >= |bestSet|)
-- cut branch
return
else
m := min(from)
from' := deleteMin(from)
foreach (req in (requiredNumbers m))
closure (from' + (req - to)) (to + {m})
-- recoverEquation is a function converts set of number to set of equation.
-- it can be done easily.
output = recoverEquation (closure input {})
Дополнительное примечание:
Ответы как
- Существует не быстрый алгоритм, потому что...
- Существует эвристический алгоритм, это...
также приветствуются. Теперь я чувствую, что нет быстрого и точного алгоритма...
Ответ # 1 можно использовать как эвристику, я думаю.
