通过加或减求两个整数之间的最短路径

发布于 2024-12-02 23:15:05 字数 331 浏览 0 评论 0原文

这是这个问题的描述:

给定两个整数 a 和 b。您想要找到将 a 转换为 b 所需的最短操作序列,其中每一步都允许您添加或减去 5、7 或 12。

例如,如果给定 a = -5 且 b = 19,最短路径是

-5 + 12 + 12 = 19

如果给你 1 和 3,最短路径将是

1 + 7 - 5 = 2

我能想到解决这个问题的唯一方法是使用 BFS 以及可能更多的修剪。我可以使用更好的算法吗?

谢谢!

Here's the description of this problem:

You are given two integers a and b. You want to find the shortest sequence of operations necessary to transform a into b, where at each step you are allowed to add or subtract 5, 7, or 12.

For example, if you are given a = -5 and b = 19, the shortest path is

-5 + 12 + 12 = 19

If you were given 1 and 3, the shortest path would be

1 + 7 - 5 = 2

The only way I can think about solving this is using BFS and maybe some more pruning. Is there a better algorithm I could use instead?

Thanks!

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(6

╰つ倒转 2024-12-09 23:15:05

让我们从一组有趣的观察开始。正如许多其他人所指出的,目标是找到一些具有整数系数的线性组合 5x + 7y + 12z = b - a ,使得 |x| + |y| + |z|被最小化。但是我们可以利用这三个数字之间的一些非常有趣的联系:

  1. 如果我们有一个组合 5x + 7y + 12z,其中 x 和 y 都是正数或都是负数,我们可以取消一些 x 和 y 来相加相当于 12 秒。换句话说,没有一个最优解在 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 具有相同的符号,那么我们可以通过将它们替换为 12 来明显地使解决方案更好。否则,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],因为如果超出,我们只需用五个 7 替换七个 5。这意味着我们可以通过执行以下操作来求解上面的方程:

对于 x = -6 到 +6,通过计算 (b - a) - 5x 并查看它是否能被 7 整除,查看 5x + 7y = b - a 是否有整数解。如果是这样,解决问题所需的步骤数由 |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) 内存来保存可能的值,我认为实际上它可能是您能够编写的最快的算法。

希望这有帮助!

Let's start off with a set of interesting observations. As many others have noted, the goal is to find some linear combination 5x + 7y + 12z = b - a with integer coefficients such that |x| + |y| + |z| is minimized. But there are some very interesting connections between these three numbers that we can exploit:

  1. If we ever have a combination 5x + 7y + 12z where x and y are both positive or both negative, we can cancel out some number of x's and y's to add an equivalent number of 12s. In other words, no optimal solution has the same sign on both x and y, because we could always make this solution better.
  2. If we ever have a combination 5x + 7y + 12z where y and z have opposite signs, we can always remove a 7 and 12 and add in a 5 of the appropriate sign to get a better solution. Similarly, if x and z have opposite signs, we can always remove a 5 and 12 and add a 7 of the appropriate sign. This means that we never need to consider any solution where z has the same sign as either x or y, because it means that there would have to be a better solution.

Let's think about what (1) and (2) collectively tell us. (1) says that the signs on x and y can't be the same, since we can always do better. (2) says that if x and z have opposite signs or if y and z have opposite signs, we can always do better. Collectively this means that

Lemma: At least one of x, y, or z must be zero in the optimal solution.

To see this, if all three are nonzero, if x and y have the same sign, then we can clearly make the solution better by replacing them with 12s. Otherwise, x and y have opposite signs. Thus if x and z have different signs, by (2) we can replace them with fewer 7's, otherwise y and z have different signs and by (2) we can replace them with fewer 5's.

Okay, this is looking really great! This means that we just need to solve these three integer equations and find which one has the smallest sum of coefficients:

  • 5x + 7y = b - a
  • 5x + 12z = b - a
  • 7y + 12z = b - a

Fortunately, by Bezout's identity, because gcd(5, 7) = gcd(5, 12) = gcd(7, 12) = 1, all of these systems of equations have a solution for any value of b - a.

Now, let's see how to solve each of these equations. Fortunately, we can use some cute tricks to greatly reduce our search space. For example, for 5x + 7y = b - a, the value of x can't be outside of [-6, +6], since if it were we could just replace seven of the 5's with five 7's. This means that we can solve the above equation by doing the following:

For x = -6 to +6, see if 5x + 7y = b - a has an integer solution by computing (b - a) - 5x and seeing if it's divisible by seven. If so, the number of steps required to solve the problem is given by |x| + |((b - a) - 5x) / 7|.

We can use similar tricks to solve the latter two equations - for the second equation, x ranges from -11 to +11, and for the third y ranges from -11 to +11 as well. We can then just take the best answer out of all three equations to see what the answer is.

Here's some pseudocode to record the fewest number of steps possible. This can easily be modified to return what those steps are by just recording which of the solutions was used and then expanding it out into a full path:

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;

This algorithm is amazingly fast - it runs in O(1) time because the number of iterations required to solve each three of the linear systems is a constant (at most 23). It requires only O(1) memory to hold the possible values, and I think that in practice it's probably the fastest algorithm you'll be able to write.

Hope this helps!

橘虞初梦 2024-12-09 23:15:05

这个问题相当于获取数字ab。或 abs(ab),因为它围绕零对称。我认为通过采用动态编程可以轻松完成此任务。例如,最快获得 23 的方法是获得 23+5,23-5,23+7,23-7,23+1223-12 的最快方法代码> 加一运算。如果您在开始条件上应用几次(+5、-5、.. 的成本为 1,其他为无限),您将在 O(ab) 中得到答案。

The problem is equivalent to getting the number a-b. Or abs(a-b), since it's symmetric around zero. I think this can be done easily with an adoption of dynamic programming. For example, to quickest way to get 23 is the quickest way to get 23+5,23-5,23+7,23-7,23+12 or 23-12 plus one operation. If you apply that a couple of times on the start condition (cost of +5,-5,.. is 1, others are infinite), you'll have your answer in O(a-b).

瀟灑尐姊 2024-12-09 23:15:05

你需要解 5x+7y+12z = ba。使得|x| + |y| + |z|是最小值。也许有一种简单的数学方法。也许这有帮助: 链接< /a>

You need to solve 5x+7y+12z = b-a. such that |x| + |y| + |z| is minimum. Perhaps there is a straightforward mathematical way. Perhaps this helps: Link

梦开始←不甜 2024-12-09 23:15:05

我想你可以看看子集和问题来获取想法。

I guess you could have a look at the Subset Sum Problem for ideas.

猫卆 2024-12-09 23:15:05

预先计算第一个最小范围所需的运算,然后继续添加+12的倍数。

Pre calculate the operations needed for the first minimum range, after that just keep adding multiples of +12.

忆伤 2024-12-09 23:15:05

将所有操作组合预先计算到哈希图中,然后只需查找答案即可。

预计算步骤需要时间,但一旦完成,您就可以在预计算范围内找到答案,即 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);

Pre-calculate all your operations combos into a hash map then just do a look-up on the answer.

The pre-calculation step will take time but once its done you have finds for answers within the pre-calculated range that are 1 look-up operation.

Here is a small JavaScript demonstration:

// 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);
~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文