AからBへの動きのカウント数

Question

次の問題があります。

チェス盤では、特定の広場（赤色で表示）に騎士がいて、別の広場（緑色で表示）に到達するために騎士が取ることができる道を見つける必要があります。このような

：私は

私はチェス（L字移動）に騎士の移動ルールに従っている間の最短経路を検索し、移動の数をカウントする必要が異なることを試みたが、成功しなかった。

どうすればよいですか？

Answer 1

問題を一定の時間内に解決したいと考えています。 breadth-first searchアルゴリズムを使用して、開始点からすべての可能な移動を試してください。騎士をすでに訪問した四角に移動させる移動を無視する。

目的地点に到達すると、より長い解を検索する必要はなく、最初の解と同じ長さのすべての解を列挙し終えるだけで済みます。

Answer 2

私は、このための任意のヒューリスティックを見つけるためにオンラインでチェックしませんでしたが、私はそれについてあなたにいくつかの内部のヒントを与えることができます。

騎士の実際の正方形の対角線上のすべての正方形を2つだけの移動で到達することができますただし、騎士はコーナーにいない。正方形（x-1、y + 1）、（x + 1、y + 1）、（x + 1、y-1）および（x-1、y-1）動きます。

• 実際の正方形の上、上、右、左の四角は3つの動きをとります。 実際の四角形の対角線上のすべての四角形（たとえば、実際の四角形= c4、ターゲット四角形a6）は、4つの動きをとります。

• 実際の正方形の対角線上にある2つの正方形（たとえば、実際の正方形= c4、ターゲット正方形f7）の各正方形は、わずか2つの動きしかかかりません。

• 最後に、指定された色の四角形の中にある場合、反対の色の四角に到達するために奇数回の移動を行います。ターゲットの四角形があなたが現在いる四角形と同じ色を持っている場合、それは偶数の動きを取るでしょう。

• 8x8のボードに別のものに指定された位置から騎士を取るステップの数は、私はあなたが上記のヒューリスティックを組み合わせたアルゴリズムを作ることができると思うと適応最大6

でありますG. Sliepenがそれについて言及している、幅優先探索アルゴリズム。

answerからhttp://math.stackexchange.comまでお寄せください。あなたはまた、O（1）の解決策で、たくさんの良い答えhereを見つけることができます。

Answer 3

動的計画ソリューションは、再発の説明があります。

DP(x,y)= 1 + min(
       DP(x-2,y-1),DP(x-2,y+1),DP(x+2,y-1),DP(x+2,y+1), 
       DP(x-1,y-2),DP(x-1,y+2),DP(x+1,y-2),DP(x+1,y+2) 
     ); 

私は間違っていない場合は、memoizeするO（N^2）が必要になります。