Ответ 1
Пусть начнется набор интересных наблюдений. Как отмечалось многими другими, цель состоит в том, чтобы найти некоторую линейную комбинацию 5x + 7y + 12z = b - a с целыми коэффициентами, для которой | x | + | y | + | z | минимизируется. Но между этими тремя числами есть очень интересные связи:
- Если у нас когда-либо есть комбинация 5x + 7y + 12z, где x и y оба положительные или оба отрицательные, мы можем отменить некоторое количество x и y, чтобы добавить эквивалентное число 12s. Другими словами, ни одно оптимальное решение не имеет одинакового знака как для x, так и для y, потому что мы всегда можем сделать это решение лучше.
- Если у нас когда-либо есть комбинация 5x + 7y + 12z, где y и z имеют противоположные знаки, мы всегда можем удалить 7 и 12 и добавить 5 соответствующих знаков, чтобы получить лучшее решение. Аналогично, если x и z имеют противоположные знаки, мы всегда можем удалить 5 и 12 и добавить 7 соответствующего знака. Это означает, что нам никогда не нужно рассматривать какое-либо решение, где z имеет тот же знак, что и x или y, потому что это означает, что должно быть лучшее решение.
Подумайте о том, что (1) и (2) сообщаем нам. (1) говорит, что знаки на х и у не могут быть одинаковыми, поскольку мы всегда можем добиться большего. (2) говорит, что если x и z имеют противоположные знаки или если y и z имеют противоположные знаки, мы всегда можем добиться большего успеха. В совокупности это означает, что
Лемма: по крайней мере один из x, y или z должен быть равен нулю в оптимальном решении.
Чтобы увидеть это, если все три отличны от нуля, если x и y имеют один и тот же знак, тогда мы можем четко сделать решение лучше, заменив их на 12s. В противном случае x и y имеют противоположные знаки. Таким образом, если x и z имеют разные знаки, то в силу (2) мы можем заменить их меньшим числом 7, в противном случае y и z имеют разные знаки, а по (2) мы можем заменить их меньшим числом 5.
Хорошо, это действительно здорово! Это означает, что нам просто нужно решить эти три целочисленных уравнения и найти, какая из них имеет наименьшую сумму коэффициентов:
- 5x + 7y = b - a
- 5x + 12z = b - a
- 7y + 12z = b - a
К счастью, идентификатор Bezout, поскольку gcd (5, 7) = gcd (5, 12) = gcd (7, 12) = 1, все эти системы уравнений имеют решение для любого значения b - a.
Теперь посмотрим, как решить каждое из этих уравнений. К счастью, мы можем использовать некоторые симпатичные трюки, чтобы значительно сократить наше пространство поиска. Например, для 5x + 7y = b - a значение x не может быть вне [-6, +6], так как если бы мы могли просто заменить семь из 5 на пять 7. Это означает, что мы можем решить вышеупомянутое уравнение, выполнив следующее:
Для x = -6 - +6, см., если 5x + 7y = b - a имеет целочисленное решение, вычислив (b - a) - 5x и увидев, если он делится на семь. Если это так, количество шагов, необходимых для решения проблемы, задается | x | + | ((b - a) - 5x)/7 |.
Мы можем использовать аналогичные трюки для решения последних двух уравнений - для второго уравнения х варьируется от -11 до +11, а для третьего у - от -11 до +11. Затем мы можем просто взять лучший ответ из всех трех уравнений, чтобы узнать, что такое ответ.
Здесь некоторый псевдокод для записи наименьшего количества шагов. Это можно легко изменить, чтобы вернуть то, что эти шаги, просто записав, какое из решений было использовано, а затем расширило его на полный путь:
Let best = infinity
# Solve 5x + 7y = b - a
for x = -6 to +6:
if ((b - a) - 5 * x) mod 7 = 0:
best = min(best, |x| + |((b - a) - 5 * x) / 7|)
# Solve 5x + 12y = b - a
for x = -11 to +11:
if ((b - a) - 5 * x) mod 12 = 0:
best = min(best, |x| + |((b - a) - 5 * x) / 12|)
# Solve 7x + 12y = b - a
for x = -11 to +11:
if ((b - a) - 7 * x) mod 12 = 0:
best = min(best, |x| + |((b - a) - 7 * x) / 12|)
return best;
Этот алгоритм изумительно быстр - он работает в O (1) раз, поскольку число итераций, необходимых для решения каждой из трех линейных систем, является константой (не более 23). Для хранения возможных значений требуется только память O (1), и я думаю, что на практике это, вероятно, самый быстрый алгоритм, который вы сможете записать.
Надеюсь, это поможет!