Кратчайший путь между двумя целыми числами путем сложения или вычитания

Вот описание этой проблемы:

Вам даны два целых числа a и b. вы хотите найти кратчайшую последовательность операций, необходимых для преобразования a в b, где на каждом шаге вам разрешено сложить или вычесть 5, 7 или 12.

Например, если вам даны a = -5 и b = 19, кратчайший путь - 

-5 + 12 + 12 = 19

Если бы вам дали 1 и 3, кратчайший путь был бы

1 + 7 - 5 = 2

Единственный способ, которым я могу думать о решении этой проблемы, - это использование BFS и может быть, еще немного подрезать. Есть ли лучший алгоритм, который я мог бы использовать вместо этого?

Спасибо!

6 17
numbers theory algorithm equation

6 ответов:

Давайте начнем с ряда интересных наблюдений. Как отмечали многие другие, цель состоит в том, чтобы найти некоторую линейную комбинацию 5x + 7y + 12z = b - a с целочисленными коэффициентами, такими что |x| + |y| + |z| минимизируется. Но есть некоторые очень интересные связи между этими тремя числами, которые мы можем использовать:

  1. Если у нас когда-нибудь будет комбинация 5x + 7y + 12z, где x и y оба положительны или оба отрицательны, мы можем отменить некоторое количество x и y, чтобы добавить эквивалент другими словами, ни одно оптимальное решение не имеет одинакового знака как на x, так и на y, потому что мы всегда могли бы сделать это решение лучше.
    2. Если у нас когда-либо будет комбинация 5x + 7y + 12z, где y и z имеют противоположные знаки, мы всегда можем удалить 7 и 12 и добавить 5 соответствующего знака, чтобы получить лучшее решение. Аналогично, если x и z имеют противоположные знаки, мы всегда можем удалить 5 и 12 и добавить 7 соответствующего знака. Это означает, что нам никогда не нужно рассматривать какое-либо решение, где z имеет тот же знак, что и x или y, потому что это означает, что должно быть лучшее решение.
Давайте подумаем о том, что (1) и (2) сообща говорят нам. (1) говорит, что знаки на x и y не могут быть одинаковыми, так как мы всегда можем сделать лучше. (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
К счастью, по тождеству Безута , поскольку 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|.

Мы можем использовать подобные трюки, чтобы решите два последних уравнения - для второго уравнения x колеблется от -11 до +11, а для третьего y колеблется также от -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) памяти, и я думаю, что на практике это, вероятно, самый быстрый алгоритм, который вы сможете написать.

Надеюсь, это поможет!

32

Задача эквивалентна получению числа a-b. Или abs(a-b), поскольку она симметрична относительно нуля. Я думаю, что это может быть легко сделано с принятием динамического программирования. Например, самый быстрый способ получить 23 - это самый быстрый способ получить 23+5,23-5,23+7,23-7,23+12 или 23-12 плюс одну операцию. Если применить это пару раз на стартовом условии (стоимость +5, -5,.. есть 1, другие бесконечны), вы получите свой ответ в O(a-b).

2

Вам нужно решить 5x+7y+12z = b-a. такое, что |x / + / y| + / z / минимально. Возможно, существует простой математический способ. Возможно, это поможет: http://mathforum.org/library/drmath/view/66870.html

2

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

0

Предварительно вычислите операции, необходимые для первого минимального диапазона, после чего просто продолжайте добавлять кратные +12.

0

Предварительно вычислите все ваши комбо операций в хэш-карту, а затем просто посмотрите на ответ.

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

Вот небольшая демонстрация JavaScript: 

// maximum depth of combos to try
var MAX = 6;
// possible operations
var ops = ["+-5", "+5", "+-7", "+7", "+-12", "+12"];
// initial hash map of operations->value
var all = {"+5":5, "+-5":-5, "+7":7, "+-7":-7, "+12":12, "+-12":-12};
var allcnt = 6; // count combos *not needed*
// initial hash map of values->operations, plus "0" so we can avoid it
var unique = {"0": "0", "5":"+5", "-5":"+-5", "7":"+7", "-7":"+-7", "12":"+12", "-12":"+-12" };
var ready = false;
// get all useful combinations of ops
function precalc() {
  var items = [];
  for(var p in all) {
     items.push(p);
  }
  for(var p=0; p<items.length; p++) {
    for(var i=0; i<ops.length; i++) {
      var k = items[p] + ops[i];
      var v = eval(k);
      if(unique[v] == null) {
        unique[v] = k;
        all[k] = v;
        allcnt++;
      }
    }
  }
}
// find an answer within the pre-calc'd depth
function find(a, b) {
  if(ready === false) {
    for(var i=0; i<MAX; i++) precalc();
    ready = true;
  }
  return unique[""+Math.abs(a-b)];
}
// test
find(-5,19);
-1