在方阵中从源移动到目的地的方式的数量

Question

假设我们有一个大小为 n*n (n<10) 的网格。我们必须从源 (a,b) 移动到目标 (x,y)。网格填充有 0's and 1's，其中 0 表示允许的路径，1 表示阻止的路径。在每一步，您都可以进行 chess piece kings` 移动，即移动到您周围 8 个网格中的任何一个。

我必须获得从源头到达目的地的多种方式。如果你走一条路然后向后折返，它就不会被计算在内（否则路径的数量将是无限的）。即使我没有确切的数字，它也很好，但近似值会起作用（即，如果它至少能给出一致的结果，即使是不正确的想法也会受到赞赏）。

任何类型的想法、伪代码、任何语言（最好是 c++，java）的片段都会有所帮助。

PS：如果解决方案对移动有限制（例如仅向右和向上以及 r/u 对角线），但可以扩展到其他类似的限制，它也会有所帮助。

Answer 1

你可以借鉴归并排序的思想，尝试一种比DFS更高效的算法。

想法是标记一个区域，对其进行详尽搜索（另一个 DFS），并记下该区域的进出顶点对和方法数。这样可以避免在同一区域反复遍历而导致复杂性。

然而，在 10*10 的板上实现一个简洁的伪代码可能会很笨拙，因为它不是 2 的指数，但是用你喜欢的任何随机数切割板都可以完成这项工作。

Answer 2

由于您不想重复一个单元格（图形节点），因此您可以通过的最多节点数为 10x10，即 100。

一种近似方法可能是考虑遍历所有组合中的所有空闲单元格。那会成功的（#free cells）！最多 100 个！但这可能是一个严重的高估。

一种更保守且可能更接近实际数量的方法是使用我们拥有的两个约束，即 100 个节点和 8 个分支方向，并将其设为 8^100。该数字近似于每步分支 8 次，直到耗尽 100 个单元格（如果它们都是空闲的）。

稍小一点的近似值不会返回到自身，因此只有 7 个分支方向，使它成为 7^100。这个近似值将估计 7^(#free cells).

考虑阻塞单元数量的更小近似值也用于分支估计，可以将 7 缩小阻塞单元的百分比，即使用 (7 x #free_cells/100) ^ (#free_cells ).一旦被阻塞的单元格数量的指数基数足够接近（或小于）1，这肯定会开始低估。

你没有说明为什么要这个号码。希望这些方法对你有所帮助。

Answer 3

如果你愿意接受不能导致循环的方向的解决方案，你可以用动态规划来解决这个问题。

例如，如果你只能下和右：

d[i, j] = number of ways of reaching [i, j] from [1, 1]

我们有：

d[1, 1] = 1
d[i, j] = d[i - 1, j] +        <- move down from (i - 1, j) to (i, j)
          d[i, j - 1]          <- move right from (i, j - 1) to (i, j)

注意：确保忽略无效索引。

只从(a, b)移动到(x, y)，你可以想象将d的左上角设置为(a, b)，然后计算到d[x - a + 1, y - b + 1] ].

为了处理被阻塞的单元格，只需将它们的位置设置为 d 到 0。

这可以很容易地扩展到其他不会导致循环的动作对（或三重动作）。您可以通过旋转矩阵并做同样的事情，或者稍微调整公式来做到这一点。

例如，对于 up 和 right，您将有：

d[i, j] = d[i + 1, j] + d[i, j - 1]

您需要通过从下到上而不是通常的从上到下迭代行来计算。

请注意，某些方向对与其他方向相同：例如，up 和 left 的答案与down 和 right.

Answer 4

这里尝试在 javascript 中对其进行编码，以利用 JS 函数式编程能力。

function out_bound(i,j,n) {
//returns true if coordinates (i,j) are out of bounds (n is the size of the grid)
  return (!((i<n)&&(i>=0)&&(j<n)&&(j>=0)));    
}    

function arrived(i,j,k,l) {
//returns true if the current position (i,j) is at the final position (k,l)
  return ((i===k)&&(j===l));    
}

function nb_path(i,j,k,l,grid) {
//returns the number of paths to go from (i,j) to (k,l) in the grid
  if (arrived(i,j,k,l)) {
    return 1;
  }
  else if (out_bound(i,j,grid.length)) {
    return 0;
  }
  else if (grid[i][j] === 1) {
    return 0;
  }
  else {
    grid[i][j]=1;
    return nb_path(i,j+1,k,l,deepCopy(grid)) + nb_path(i,j-1,k,l,deepCopy(grid)) + nb_path(i+1,j,k,l,deepCopy(grid)) + nb_path(i-1,j,k,l,deepCopy(grid)) + nb_path(i+1,j+1,k,l,deepCopy(grid)) + nb_path(i-1,j-1,k,l,deepCopy(grid)) + nb_path(i+1,j-1,k,l,deepCopy(grid)) + nb_path(i-1,j+1,k,l,deepCopy(grid));
  }
}

// it works for the following toy-case (I have checked by hand)
var myGrid = [[0,0],[0,0]];
console.log("there are: "+nb_path(0,0,1,1,deepCopy(myGrid))+" possible paths");

在方阵中从源移动到目的地的方式的数量

number of ways to move in a square matrix from source to destination

algorithm

graph

graph-algorithm