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

Question

这是这个问题的描述:

你有两个整数a和b.您希望找到将a转换为b所需的最短操作序列,其中每个步骤允许您添加或减去5,7或12.

例如,如果给出a = -5且b = 19,则最短路径为

-5 + 12 + 12 = 19

如果给你1和3,那么最短的路径就是

1 + 7 - 5 = 2

我可以考虑解决这个问题的唯一方法是使用BFS,也许还有一些修剪.我可以使用更好的算法吗？

谢谢!

Answer 1

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

1. 如果我们有一个组合5x + 7y + 12z,其中x和y都是正数或者都是负数,我们可以取消一些x和y来添加相当数量的12s.换句话说,没有最优解在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

幸运的是,根据Bezout的身份,因为gcd(5,7)= gcd(5,12)= gcd(7,12)= 1,所有这些方程组都有一个解b-a的任何值.

现在,让我们看看如何解决这些方程式.幸运的是,我们可以使用一些可爱的技巧来大大减少我们的搜索空间.例如,对于5x + 7y = b - a,x的值不能超出[-6,+ 6],因为如果是,我们可以用5个7替换5个中的7个.这意味着我们可以通过以下方式解决上述等式:

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

希望这可以帮助!