如何计算网格上所有可能的路径

Question

我最近在 brillant.org 的 Instagram 帐户上看到一张挑战图片：

说明：机器人随机走 4 步（不能走对角线）。

最有可能降落在哪个区域？

显然机器人有 4⁴ = 256 条可能的路径。我试图编写一个程序 (Javascript) 来解决该问题，但我的方法没有奏效。实际上我没有有用的代码可以在这里展示，因为我很早就卡住了。

所以我的问题是：你会如何编写一个程序：

检查所有 256 个可能的路径并且
告诉我有多少 (%) 降落在哪个区域

Answer 1

我会创建代表不同可能性的不同对象，如下所示：

function Path(x, y, movesLeft) {

    this.x = x;
    this.y = y;
    this.movesLeft = movesLeft;

    this.paths = [];
    if (movesLeft > 0) {
        this.paths.push(new Path(x - 1, y, movesLeft - 1));
        this.paths.push(new Path(x + 1, y, movesLeft - 1));
        this.paths.push(new Path(x, y - 1, movesLeft - 1));
        this.paths.push(new Path(x, y + 1, movesLeft - 1));
    }

    this.getArray = function() {
        if (this.movesLeft > 0) {
            var output = [];
            for (var i = 0; i < this.paths.length; i++) {
                output = output.concat(this.paths[i].getArray());
            }
            return output;
        }
        return [this];
    }

}

现在，您可以创建对象并测试结果：

var endPosArray = new Path(0, 0, 4).getArray();

您需要做的就是遍历数组并计算机会。

Answer 2

这是一个很酷的问题！感谢您让我发现 brillant.org 的 Instagram 帐户。因此，我将按以下步骤进行：

写一个函数来计算所有可能的重复排列 (n^k)
生成一个地图，在其中执行步骤 1 中计算出的所有可能移动
检查机器人最后一步的着陆区域并存储
根据步骤 3 中的计数计算百分比

第一步本身就是一个问题，不属于这个范围。您可以在此处使用或修改代码：https://rosettacode.org/wiki/Permutations_with_repetitions

然后，为了生成地图，我简单地使用了一个数组：

const map = [
  0, 0, 0, 0, 1, 0, 0, 0, 0,
  0, 0, 0, 1, 1, 1, 0, 0, 0,
  0, 0, 1, 1, 2, 1, 1, 0, 0,
  0, 1, 1, 2, 2, 2, 1, 1, 0,
  1, 1, 3, 3, 2, 3, 3, 1, 1,
  0, 1, 1, 3, 3, 3, 1, 1, 0,
  0, 0, 1, 1, 3, 1, 1, 0, 0,
  0, 0, 0, 1, 1, 1, 0, 0, 0,
  0, 0, 0, 0, 1, 0, 0, 0, 0,
];

这是您提供的图片的代表，每个区域都标有不同的编号，我们稍后会重复使用。

此时我定义了一个包含 4 种可能走法的数组：

const moves = [
  -1,  // left 
   1,  // right,
  -9,  // top
   9,  // bottom
];

这些值表示在评论中写的方向上移动所需的偏移量：左和右我想是不言自明的。对于顶部和底部，由于我们使用数组作为 "matrix"，我们基本上需要将 y 值转换为数组中的索引值。公式很简单：index = x + y * width 因此它意味着如果你想指定一个 y 将 up 移动一个你有 -1 * 9 的单元格，并移动 down 是 1 * 9.

同理机器人的起始位置（地图中心）计算如下：4 + 4 * 9.

现在我用排列函数计算所有可能的走法组合：

const allmoves = permutationsWithRepetition(4, moves);

并创建一个数组来存储结果：

let results = [0, 0, 0, 0];

之后，我只是迭代所有可能的走法数组，并计算走法结束时的位置：

for (let j = 0; j < allmoves.length; j++) {
  // set the robot's initial position at the center
  // before executing any moves' list
  let pos = 4 + 4 * 9;

  // calculate the new position using the current moves
  for (let i = 0; i < moves.length; i++) {
    let move = allmoves[j][i];
    pos += move;
  }

  // now `map[pos]` points to a number between 1 and 3
  // that identify the area where the robot is.
  // we use that number as index of the results
  // to increment its value.
  // Notice that it's impossible land to any 0 area
  // if we start from the center and we can only perform
  // 4 moves.
  // We use that number as `index` for our `results`
  results[map[pos]]++;
}

现在在 results 中，您将知道机器人在哪个区域结束了多少次：

console.log(results); // [0, 60, 100, 96]

如上所述，机器人在任何 0 区域着陆的起始位置和移动次数是不可能的，因此第一个索引的值为 0。您可以看到它在区域 1（橙色）中降落了 60 次，在区域 2 中降落了 100 次（最小区域，绿色/浅绿色），在区域 3 中降落了 96 次（蓝色/紫色） ).

此时您可以计算百分比 (times / total * 100) 并以适当的格式显示它：

// we skip the first element of results since
// it's not an area (and we'll be always 0)
for (let k = 1; k < results.length; k++) {
  console.log(k, `${(results[k] /  allmoves.length * 100).toFixed(2)}%`)
}

你会得到：

1 "23.44%"
2 "39.06%"
3 "37.50%"

你也可以做一个经验检查，实际上随机生成一万个动作，让程序应用这些动作而不是 allmoves，你会发现你总是以相似的数字结束（很明显，但这也是数学中有趣的部分，验证这实际上是您所期望的！）。

这里是一个工作代码，它也实现了 permutation code mentioned at the beginning, from rosettacode.org, and the code explained in this post: https://codepen.io/zer0/pen/RwWPZmE

（需要打开控制台才能看到结果）

如何计算网格上所有可能的路径

How to compute all possible paths on a grid

javascript

arrays

loops

matrix

pseudocode