3

今日の試験では、チェス盤のサイズN * Mが与えられたアルゴリズムの問​​題が発生しました。騎士がチェス盤の左下の端から移動できる、可能な最小の移動数を決定する必要があります。右上端に。どうすればそれができますか？

4

4 に答える 4

2

BFSとmemoizationを使用したソリューション:

# Memoization
memo = a matrix of NOVISITED of size N x M

# Starting position
# (row, column, jumps)
queue.push((0, 0, 0))

while queue is not empty:
  # Get next not visited position
  row, column, jumps = queue.pop()

  # Mark as visited
  memo[row][column] = jumps

  for each possible move (nrow, ncolumn) from (row, column):
    if memo[nrow][ncolumn] is NOVISITED:
      # Queue next possible move
      queue.append((nrow, ncolumn, jumps + 1))

NOVISITED値を持つことができます。-1またはnull、可能な距離を非負の数と見なした場合[0,+inf)。

各正方形のジャンプの最小数は でアクセスできるmemo[row][column]ため、左下から右上隅の答えは になりますmemo[N - 1][M - 1]。

アップデート

行列が正方形の場合、N x N対称原理を適用できることに注意してください。

于 2012-06-28T17:53:42.107 に答える
1

BFSまたはDFSを使用して、騎士の動きをシミュレートできます。個人的には、再帰的に実装できるため、DFSアプローチを好みます。process現在のx位置、現在のy位置、テーブルの行、テーブルの列、およびカウンターをパラメーターとして受け取る関数がある場合、ソリューションは次のようになります。

/* .......... */
process(x-1, y-2, R, C, count+1);
process(x+1, y-2, R, C, count+1);
process(x-2, y-1, R, C, count+1);
process(x-2, y+1, R, C, count+1);
process(x-1, y+2, R, C, count+1);
process(x+1, y+2, R, C, count+1);
process(x+2, y-1, R, C, count+1);
process(x+2, y+1, R, C, count+1);
/* .......... */

目的地に到着したら、countの現在の値を返します。

編集：動的計画法を使用して解決することもできます。dp(i,j)あなたは正方形（i、j）に到達するための最良の方法であると定義します。したがって、dp（i、j）は次のようになります。

dp(i,j) = min{dp(all squares that can reach (i,j) in one move)} + 1
于 2012-06-28T19:17:07.687 に答える
1

これを3つのケースに減らすことができると思います。

  1. ソリューションの例がないボードがあります：2w * 4h

  2. あなたは1：2w*3hのソリューションを持つボードを持っています

  3. あなたは正方形のボードを持っているので、4：3w*3hの解があります

これらよりも大きいボードがある場合は、1つの移動の終点をより大きなボードの開始点として設定することにより、ボードを1つに減らすことができます。

例：サイズ4w * 5hのボード：

_ _ _ _
_ _ _ _
_ e _ _
_ _ _ _
s _ _ _

ここで、sは開始、eは終了です。

そこから、それを正方形のボードに縮小します。

_ 1 e
3 _ _
s _ 2

最後まで4手かかるところ。したがって、このサイズでは1+4移動=5になります。

それで始められるといいのですが。

編集：これはそのままでは完璧ではないようです。ただし、この問題を解決するためのヒューリスティックな方法を示しています。これがあなたの見る楽しみのためのもう一つのケースです：

_ _ _ e
_ 3 _ _
_ _ _ _
_ _ 2 _
_ _ _ _
_ 1 _ _
_ _ _ _
s _ _ _

それは4x8ボードの最後まで4つの動きがあります。

プログラミング言語を介して、これは、現在の場所からのすべての可能な動きをマッピングし、それらがエンドポイントと一致するかどうかを確認することから始めることによって、よりよく解決される可能性があります。そうでない場合は、問題が以前に解決したより単純な問題であるかどうかを確認してください。コメント投稿者が指摘したように、これはメモ化によって実現されます。

ただし、これを手作業で行う場合は、私が始めたように、少数のケースに分離することで解決できると思います。

于 2012-06-28T17:03:57.210 に答える
1

これが効率的な解決策です。

まず、特殊なケース。n = 1ジャンプできず、問題が でしか解決できない場合(1, 1)。n = 2調べてみると、たどることができるパスが1つしかなく、問題が解決できるのは、そこに到達するためにジャンプm = 4k + 3が必要な場合のみです。2k + 1の場合は逆ですm = 1,2。

さて、一般的なケースです。ナイトには 8 回のジャンプがあり、一方向に 2 回、別の方向に 1 回ジャンプします。可能な方向はr, l, u, d(右、左、上、下) です。nru右に 2 回、次に上に 1 回ジャンプし、残りの 7 回のジャンプについても同様です。その場合、答えは次の 1 対の方程式の解でなければなりません。

n - 1 = 2*nru + nur - nul - 2*nlu - 2*nld - ndl + ndr + 2*nrd
m - 1 = nru + 2*nur + 2*nul + nlu - nld - 2*ndl - 2*ndr - nrd

そして、ジャンプの数は次のとおりです。

nru + nur + nul + nlu + nld + ndl + ndr + nrd

ジャンプの数はできるだけ少なくすることを期待しています。直観的には、上の 2 つの方程式を満たす一連の数値があり、ジャンプの数を少なくした場合、ボックス内に留まるジャンプを配置する順序を見つけるのにそれほど苦労することはありません。証明はしませんが、 と の場合、これは真であることがわかり2 < nます2 < m。

したがって、この整数計画問題を解いて (ジャンプの数をできるだけ少なくしてこれらの 2 つの方程式を解いて)、答えが得られます。これには解決策がありますが、この特定の問題は非常に単純です。目標に近づくために「明白なこと」を行い、余分なジャンプをいくつか見つけます。これが整数方程式の最適解であることを証明することは難しくありません。したがって、チェスの答えでなければなりません。問題。

では、明らかなことは何ですか？まず、 の場合m < n、ボードをひっくり返すだけでよいので、一般性を失うことなく、 と仮定できn < mます。（ボードは、少なくとも横向きと同じくらいあなたから離れます。） その事実を考えると、明らかなことは、壁にぶつかるまで左上にジャンプするか、必要なコーナーから下に伸びる対角線にぶつかることです。その時点で、壁に沿って、またはターゲットに向かって斜めに進みます。

ターゲットに直接着地すると、可能な限り最善の答えが得られます。

壁に沿って進み、1 点も逃した場合、ジャンプの 1 つをペアに変換することで、必要な場所にたどり着くことができます。壁に沿って行って 2 ミスした場合 (つまり、1 つの対角線)、2 つのジャンプを挿入する必要があります。(距離は、少なくとももう 1 つ必要であることを示し、単純なパリティの引数は、少なくとも 2 つ必要であることを示し、ジャンプのペアでそれを行います。)

対角線に沿って進み、1 ミスした場合は、ジャンプを 1 ペア挿入すればOKです。

対角線に沿って進み、2 回失敗した場合は、右上/右上のペアを右上/右上/左上/左上に変換すると、あと 2 回のジャンプでそれを行うことができます。

対角線に沿って移動せずに左上があった場合は、それを右上/左上/右上のトリプレットに変換すると、あと 2 回のジャンプで実行できます。

残りの特殊なケースは 3x3 ボードで、4 回ジャンプします。

（絵がうまくいく適切な不等式とモジュロのすべてを理解することはあなたに任せます。）

于 2012-06-28T20:12:15.183 に答える