math - 最小骑士移动从一个方格到另一个方格

Question

这个问题在这里已经有了答案:





Knight's Shortest Path on Chessboard

(17 个回答)


7年前关闭。




是否有一个数学公式可以用来计算在无限 2D 网格中两点之间的最小骑士移动次数？我可以使用广度优先搜索来解决这个问题，但是我们可以使用封闭形式的表达式吗？

谢谢!

Answer 1

我认为没有一个公式可以为所有点对生成最小距离。

但是对于一些特殊的点有。
让 A,B 成为 2D 上的点 - 网格 A = (0,0)和 B = (x,y)和 dist(x,y)最少的骑士移动次数。

首先，距离是对称的:
dist(x,y) = dist(-x,y) = dist(x,-y) = dist(-x,-y) = dist(y,x)

案例:2x=y -> dist(x,2x) = x

案例:x = 0

子案例 1:y = 4k (k 是自然数)
-> dist(x,y) = 2k

子案例 2:y = 4k+1或 y = 4k+3-> dist(x,y) = 2k + 3

子案例 3:y = 4k+2-> dist(x,y) = 2k + 2

案例:x = y

子案例 1:x = 3k (k 是自然数)
-> dist(x,y) = 2k

子案例 2:x = 3k+1-> dist(x,y) = 2k + 2

子案例 3:y = 3k+2-> dist(x,y) = 2k + 4

如果 B(带有 0 <= x <= y )在任何情况下都不适合，您至少知道 dist(x,y) <= dist(x-k,y-2k) + dist(k,2k) = dist(0,y-2k) + k和 dist(x,y) <= dist(x-z,y-z) + dist(z,z) = dist(0,y-z) + dist(z,z)
编辑:
我想多了。我认为以下算法计算最小移动(Maple Code):

dist := proc(x,y)
  global d;
  local temp;

  if x < 0 then x:= -x; fi;
  if y < 0 then y:= -y; fi;
  if x > y then temp := x; x:= y; y:= temp; fi;

  if y = 2*x then return x; fi;
  if x = y then 
    if x mod 3 = 0 then return 2*(x/3); fi;
    if x mod 3 = 1 then return 2+2*(x-1)/3 fi;
    if x mod 3 = 1 then return 4+2*(x-2)/3 fi;
  fi;
  if x = 0 then
    if y mod 4 = 0 then return y/2; fi;
    if y mod 4 = 1 or y mod 4 = 3 then return 3+(y - (y mod 4))/2; fi;
    if y mod 4 = 2 then return 2+(y-2)/2; fi;
  fi;
  if y > 2*x then
    return dist(0,y-2*x) + dist(x,2*x);        
  else
    return dist(2*x-y,2*x-y) + dist(y-x,2*(y-x));
  fi;
end proc:

注意:这仅适用于无限 2D 网格。

编辑2:这个(递归)算法在 O(1) 中运行(时间和空间)因为它有一个常数 O(1)操作并最多再调用一次。

EDIT3:我想了一点，我认为这在有限二维网格上也是正确的，如果 A或 B距离至少一个边界至少 1 行/列。