5

チェスに関するアルゴリズムの問​​題を解こうとしています。

A8 にキングがあり、それを H1 に移動したいとします (許可された移動のみ)。与えられた k 回の動きを正確に行う可能性 (パス) がいくつあるかを調べるにはどうすればよいでしょうか? (例: 15 回の移動でキングを A8 から H1 に移動したい場合、パス/可能性はいくつありますか?)

単純な解決策の 1 つは、これをグラフの問題と見なし、各移動のコストを 1 としてカウントする標準的なパス検索アルゴリズムを使用することです。たとえば、キングを A8 から H1 に 10 回移動させたいとします。合計が 10 になるすべてのパスを単純に検索します。

私の質問は、これを行うためのより巧妙で効率的な方法が他にある場合は? また、「アルゴリズム的」で「ブルートフォースのような」ものではなく、より「数学的」で簡単にこの数を見つけることができるかどうかも疑問に思っていました。

4

3 に答える 3

3

隣接行列を使用できます。このような行列をそれ自体で乗算すると、ポイントからポイントへのパスの量が得られます。例：

グラフ: 完全 K3 グラフ: A<->B<->C<->A

マトリックス：

[0 ; 1 ; 1]
[1 ; 0 ; 1]
[1 ; 1 ; 0]

長さ 2 のパス: M * M

[2 ; 1 ; 1]
[1 ; 2 ; 1]
[1 ; 1 ; 2]

長さ 3 は M * M * M になります

[2 ; 3 ; 3]
[3 ; 2 ; 3]
[3 ; 3 ; 2]
于 2012-06-04T09:28:48.450 に答える
3

これは単純な O(N^3) 動的計画法の問題です。

次のように 3D 配列を割り当てるだけです。

Z[x][y][k] をボード上の位置 (x,y) から目的地に到達するまでの k ステップの移動数とします。

基本ケースは次のとおりです。

foreach x in 0 to 7,
   foreach y in 0 to 7,
       Z[x][y][0] = 0 // forall x,y: 0 ways to reach H1 from
                      // anywhere else with 0 steps

Z[7][7][0] = 1 // 1 way to reach H1 from H1 with 0 steps

再帰的な場合は次のとおりです。

foreach k in 1 to K,
   foreach x in 0 to 7,
      foreach y in 0 to 7,
          Z[x][y][k+1] = Z[x-1][y][k]
              + Z[x+1][y][k]
              + Z[x][y-1][k]
              + Z[x][y+1][k]
              + ...; // only include positions in
                     // the summation that are on the board
                     // and that a king can make

あなたの答えは次のとおりです。

return Z[0][0][K]; // number of ways to reach H1(7,7) from A8(0,0) with K moves

(移動を水平移動と垂直移動の 2 つのセットに分解し、これらを組み合わせてインターリーブの数を掛けることにより、O(n^2) でこれを行うより高速な方法があります。)

この関連する質問と回答を参照してください: No of ways to walk M steps in a grid

于 2012-06-04T13:03:11.977 に答える
0 
.......E <-end
........
........
........
........
........
........
S....... <-start

残念ながら、パスが最短パスではない可能性があるため、「標準的なパス検索アルゴリズム」は使用できません。すべてのパスを考慮した単純な検索を具体的に使用する必要があります（たとえば、深さ優先または幅優先）。

ただし、どのようにしてタイルに到達したかは気にしないため、動的計画法と呼ばれる手法を使用できます。すべての場所 (i,j) について、n回の移動でそこに到達する方法の数 (方法i,j (n)と呼びましょう) は次のとおりです。

ウェイi,j (n) = ウェイi-1,j (n-1) + ウェイi+1,j (n-1) + ウェイi,j-1 (n-1) + ウェイi,j+1 (n-1) + ウェイi+1,j+1 (n-1) + ウェイi-1,j+1 (n-1) + ウェイi+1,j-1 (n-1) + ウェイi -1,j-1 (n-1)

つまり、キングは 1 回の移動で隣接するどのマスからでも移動できます。

ウェイi,j (n) = 合計ネイバー (i, j) (ウェイネイバー(n-1))

したがって、たとえば python では次のようにします。

SIZE = 8

cache = {}
def ways(pos, n):
    r,c = pos  # row,column
    if not (0<=r<SIZE and 0<=c<SIZE):
        # off edge of board: no ways to get here
        return 0
    elif n==0:
        # starting position: only one way to get here
        return 1 if (r,c)==(0,0) else 0
    else:
        args = (pos,n)
        if not args in cache:
            cache[args] = ways((r-1,c), n-1) + ways((r+1,c), n-1) + ways((r,c-1), n-1) + ways((r,c+1), n-1) + ways((r-1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c-1), n-1) + ways((r+1,c+1), n-1)
        return cache[args]

デモ：

>>> ways((7,7), 15)
1074445298

上記の手法はメモ化と呼ばれ、物事を行う順序について実際に考える必要がないため、動的プログラミングよりも簡単に記述できます。一連の大規模なクエリを実行すると、キャッシュが大きくなることがわかります。

>>> cache
{}
>>> ways((1,0), 1)
1
>>> cache
{((1, 0), 1): 1}
>>> ways((1,1), 2)
2
>>> cache
{((0, 1), 1): 1, ((1, 2), 1): 0, ((1, 0), 1): 1, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((1, 1), 2): 2, ((2, 2), 1): 0}
>>> ways((2,1), 3)
5
>>> cache
{((1, 2), 1): 0, ((2, 3), 1): 0, ((2, 0), 2): 1, ((1, 1), 1): 1, ((3, 1), 1): 0, ((4, 0), 1): 0, ((1, 0), 1): 1, ((3, 0), 1): 0, ((0, 0), 1): 0, ((2, 0), 1): 0, ((2, 1), 1): 0, ((4, 1), 1): 0, ((2, 2), 2): 1, ((3, 3), 1): 0, ((0, 1), 1): 1, ((3, 0), 2): 0, ((3, 2), 2): 0, ((3, 2), 1): 0, ((1, 0), 2): 1, ((4, 2), 1): 0, ((4, 3), 1): 0, ((3, 1), 2): 0, ((1, 1), 2): 2, ((2, 2), 1): 0, ((2, 1), 3): 5}

(Python では、@cachedまたは@memoizedデコレータを使用して、最後のelse:ブロックにコード全体を記述する必要がないようにすることもできます。他の言語には、メモ化を自動的に実行する別の方法があります。)

上記はトップダウンのアプローチでした。非常に大きなスタックが生成される場合があります (スタックは で大きくなりますn)。不必要な作業を避けるために非常に効率的になりたい場合は、ボトムアップのアプローチを行うことができます。このアプローチでは、1 歩、2 歩、3 歩、... について、キングがいる可能性のあるすべての位置をシミュレートします。

SIZE = 8
def ways(n):
    grid = [[0 for row in range(8)] for col in range(8)]
    grid[0][0] = 1

    def inGrid(r,c):            
        return all(0<=coord<SIZE for coord in (r,c))
    def adjacentSum(pos, grid):
        r,c = pos
        total = 0
        for neighbor in [(1,0),(1,1),(0,1),(-1,1),(-1,0),(-1,-1),(0,-1),(1,-1)]:
            delta_r,delta_c = neighbor
            (r2,c2) = (r+delta_r,c+delta_c)
            if inGrid(r2,c2):
                total += grid[r2][c2]
        return total

    for _ in range(n):
        grid = [[adjacentSum((r,c), grid) for r in range(8)] for c in range(8)]
        # careful: grid must be replaced atomically, not element-by-element

    from pprint import pprint
    pprint(grid)
    return grid

デモ：

>>> ways(0)
[[1, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(1)
[[0, 1, 0, 0, 0, 0, 0, 0],
 [1, 1, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(2)
[[3, 2, 2, 0, 0, 0, 0, 0],
 [2, 2, 2, 0, 0, 0, 0, 0],
 [2, 2, 1, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0]]

>>> ways(3)
[[6,  11, 6, 4, 0, 0, 0, 0],
 [11, 16, 9, 5, 0, 0, 0, 0],
 [6,  9,  6, 3, 0, 0, 0, 0],
 [4,  5,  3, 1, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0],
 [0,  0,  0, 0, 0, 0, 0, 0]]

>>> ways(4)
[[38, 48, 45, 20, 9,  0, 0, 0],
 [48, 64, 60, 28, 12, 0, 0, 0],
 [45, 60, 51, 24, 9,  0, 0, 0],
 [20, 28, 24, 12, 4,  0, 0, 0],
 [9,  12, 9,  4,  1,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0],
 [0,  0,  0,  0,  0,  0, 0, 0]]
于 2012-06-04T08:52:22.370 に答える