algorithm - 涉及国际象棋的图算法：k 步中的可能路径

Question

我正在尝试解决涉及国际象棋的算法问题。

假设我在 A8 中有一个国王，并且想将其移动到 H1（仅允许移动）。我怎样才能找出有多少种可能性（路径）正在做出任何给定的 k 移动？（例如，如果我想用 15 步将国王从 A8 移动到 H1，有多少条路径/可能性？）

一个简单的解决方案是将其视为图形问题，并使用任何标准寻路算法将每一步计为成本 1。因此，假设我想在 10 步内将我的国王从 A8 移动到 H1。我会简单地搜索总和为 10 的所有路径。

我的问题是，是否还有其他更聪明、更有效的方法来做到这一点？我还想知道，是否可以找到更“数学”和更直接的方法来找到这个数字，而不是那么“算法”和“类似蛮力”？

score 3 · Accepted Answer

您可以使用邻接矩阵。如果将这样的矩阵与自身相乘，则得到从点到点的路径数量。例子：

图表：完整的 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]

score 3 · Accepted Answer

这是一个直接的 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

（在 O(n^2) 中有一种更快的方法来做到这一点，方法是将移动分解为两组水平和垂直移动，然后将它们组合并乘以交错的数量。）

请参阅此相关问题和答案：No of ways to walk M steps in a grid

score 0 · Accepted Answer

.......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中，也可以使用a @cachedor@memoized装饰器来避免必须在最后一个else:块中编写整个代码。其他语言有其他方式可以自动执行memoization。）

以上是自上而下的方法。它有时会产生非常大的堆栈（您的堆栈会随着增长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]]

algorithm - 涉及国际象棋的图算法：k 步中的可能路径

3 回答 3

Related

Reference