math - ある正方形から別の正方形に移動するための最小ナイトの動き

Question

無限の 2D グリッド内の 2 点間を移動するための騎士の移動の最小数を計算するために使用できる数式はありますか? 幅優先探索で解けるのですが、代わりに使える閉じた式はありますか？

ありがとう！

Answer 1

ポイントのすべてのペアの最小距離を生成する式が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)

1. ケース: 2x=y->dist(x,2x) = x
2. 場合：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
3. 場合：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 (with 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 グリッドでのみ正しいです。

EDIT2：この（再帰的）アルゴリズムはO(1)（時間と空間）で実行されます。これは、一定数のO(1)操作があり、最大でもう一度自分自身を呼び出すためです。

EDIT3：さらに少し考えましたが、少なくとも1つの境界線から少なくとも1行/列離れている場合A、これは有限の2Dグリッドでも正しいと思います。B