格子中的寻路 - 帮助理解示例
Pathfinding in a lattice - help to understand example
我正在研究一个问题，计算 N * N 个可能选项的网格的可能路径数。已经有一些数学答案暗示了一个简单的“组合数学”答案，但我没有组合数学的经验。四处搜索，我找到了这个相对简短的答案，但它对我来说意义不大，即使我尝试逐步执行顺序逻辑以遵循代码。
#include <iostream>
#include <vector>
uint64_t lattice_path(size_t grid_size)
{
std::vector<uint64_t> grid((grid_size + 1) * (grid_size + 1), 1);
for (int rows = grid_size - 1; rows >= 0 ; --rows) {
for (int cols = grid_size - 1; cols >= 0; --cols) {
int pos = (cols * (grid_size + 1)) + rows;
grid.at(pos) = grid.at(pos + 1) + grid.at(pos + (grid_size + 1));
}
}
return grid.at(0);
}
int main()
{
std::cout << "Paths: " << lattice_path(20) << std::endl;
return 0;
}
此代码取自 http://tvarley.github.io/blog/euler/cpp/problem_015 此网站 -（提交答案的作者很糟糕 xD）- 进行了一些编辑以使其更清晰。
我之所以选择这段代码是因为我的目标是使用 STL 容器和 method/member 函数来解决问题，但是在这个例子中顺序逻辑对我来说意义不大。
通常 projecteuler 上的问题有更简单的先驱示例（如 2x2 网格），这些示例很容易通过检查顺序逻辑在代码中建模。然后就像进行更大的测试一样简单。不过，在这种情况下，我无法在代码中真正模拟出简单的格子。
有很多方法可以得出这个问题的正确答案，具体取决于您的处理方式。
我强烈建议您首先尝试自己解决这个难题，而不是看其他解决方案 - 这通常具有最好的学习效果。
我只会解释不同方法背后的逻辑，不会为它们提供任何代码示例。
到特定点的路径数
只有两种方法可以到达网格中的某个点：要么从它正上方的点到达它，要么从它左边的点直接到达。
对于网格的顶部和左侧，这很简单；只有一种方法可以到达每个点 - 沿特定方向直线移动，例如：
您可以从那里开始填写到每个点的可能路径数。因为到达每个点的方法只有 2 种，所以到特定点的可能路径数是该点直接左侧和该点正上方的点的可能路径之和，例如：
从这里开始，您可以继续填写网格上的所有其他点，直到到达 bottom-right 角，其中将包含您的解决方案：
在这种情况下，对于 3 × 3 网格，可能的路径数为 20。
这也是您的代码示例使用的方法：它计算网格中每个点的可能路径数 - 虽然它是从底部到顶部而不是像我的那样从顶部到底部例如。
这里 a godbolt 显示了您的代码正在构建的网格。
注意规律
通过上述方法，您可能会注意到两件事：
- 我们将每个数字计算为两个邻居的总和
- 数字似乎遵循某种模式
实际上我们计算的数字是 binomial coefficients - notice how the 3 × 3 grid from above matches the elements of pascal's triangle:
所以您可以去掉上面的网格计算，而是简单地计算您要查找的二项式系数。
在这种情况下，对于 x × y 网格，公式为：
如果我们为 x 和 y 取 20，我们也会得到正确答案：
总是一样的动作
你只能向右或向下移动 - 所以向下移动一格的唯一方法是向下移动，向右移动的唯一方法是向右移动（并且有无法向左/向上移动） - 所以你移动的数量 - 无论你走哪条路 - 总是相同的。
即正好格子的高度向下移动，正好格子的宽度向右移动。
例如在 4x3 网格上，您正好向右移动 4 次，向下移动 3 次：
所以一开始你有一个你可以做的所有动作的“包”，在上面的例子中它是 {⮞,⮞,⮞,⮞,⮟,⮟,⮟} 并且在路径的每个点你都可以选择是否要走从你的包里拿出一个 ⮞ 或一个 ⮟，向那个方向移动（除非你 运行 一个，在那种情况下你只有一个选择）。
这个“袋子”的数学术语是 Multiset。
在上面的例子中我们也可以把它写成{⮞⁴, ⮟³}，以使其更短。
现在要回答有多少条可能的路径这个问题，我们需要找出有多少种可能的方式来使用多重集中的元素，例如：
⮞⮞⮞⮟⮞⮟⮟、⮟⮞⮟⮞⮟⮞⮞、等等...
所以我们正在寻找多重集的所有可能排列（长度与多重集中的元素相同）
这叫做multiset permutation，它的公式很容易记住：
其中 n 是多重集中的项目总数（上例中为 7），m₁、m₂ 等是每个元素的计数在集合中（在这种情况下，我们只有 m₁ = 4 和 m₂ = 3，所以 n = 7）。
因此，要将其概括为大小为 x × y 的网格，可能路径数的公式为：
如果将 x 和 y 的 20 代入上述等式，对于 20 × 20 网格中可能的路径数，您将得到相同的正确答案 137846528820。
这种方法还有一个好处，它适用于 2 个以上的维度，例如你也可以用这个解决这个谜题的 3 维变体。
我正在研究一个问题，计算 N * N 个可能选项的网格的可能路径数。已经有一些数学答案暗示了一个简单的“组合数学”答案，但我没有组合数学的经验。四处搜索，我找到了这个相对简短的答案，但它对我来说意义不大，即使我尝试逐步执行顺序逻辑以遵循代码。
#include <iostream>
#include <vector>
uint64_t lattice_path(size_t grid_size)
{
std::vector<uint64_t> grid((grid_size + 1) * (grid_size + 1), 1);
for (int rows = grid_size - 1; rows >= 0 ; --rows) {
for (int cols = grid_size - 1; cols >= 0; --cols) {
int pos = (cols * (grid_size + 1)) + rows;
grid.at(pos) = grid.at(pos + 1) + grid.at(pos + (grid_size + 1));
}
}
return grid.at(0);
}
int main()
{
std::cout << "Paths: " << lattice_path(20) << std::endl;
return 0;
}
此代码取自 http://tvarley.github.io/blog/euler/cpp/problem_015 此网站 -（提交答案的作者很糟糕 xD）- 进行了一些编辑以使其更清晰。
我之所以选择这段代码是因为我的目标是使用 STL 容器和 method/member 函数来解决问题，但是在这个例子中顺序逻辑对我来说意义不大。
通常 projecteuler 上的问题有更简单的先驱示例（如 2x2 网格），这些示例很容易通过检查顺序逻辑在代码中建模。然后就像进行更大的测试一样简单。不过，在这种情况下，我无法在代码中真正模拟出简单的格子。
有很多方法可以得出这个问题的正确答案，具体取决于您的处理方式。
我强烈建议您首先尝试自己解决这个难题，而不是看其他解决方案 - 这通常具有最好的学习效果。
我只会解释不同方法背后的逻辑，不会为它们提供任何代码示例。
到特定点的路径数
只有两种方法可以到达网格中的某个点：要么从它正上方的点到达它，要么从它左边的点直接到达。
对于网格的顶部和左侧，这很简单；只有一种方法可以到达每个点 - 沿特定方向直线移动，例如：
您可以从那里开始填写到每个点的可能路径数。因为到达每个点的方法只有 2 种，所以到特定点的可能路径数是该点直接左侧和该点正上方的点的可能路径之和，例如：
从这里开始，您可以继续填写网格上的所有其他点，直到到达 bottom-right 角，其中将包含您的解决方案：
在这种情况下，对于 3 × 3 网格，可能的路径数为 20。
这也是您的代码示例使用的方法：它计算网格中每个点的可能路径数 - 虽然它是从底部到顶部而不是像我的那样从顶部到底部例如。
这里 a godbolt 显示了您的代码正在构建的网格。
注意规律
通过上述方法，您可能会注意到两件事：
- 我们将每个数字计算为两个邻居的总和
- 数字似乎遵循某种模式
实际上我们计算的数字是 binomial coefficients - notice how the 3 × 3 grid from above matches the elements of pascal's triangle:
所以您可以去掉上面的网格计算，而是简单地计算您要查找的二项式系数。
在这种情况下，对于 x × y 网格，公式为：
如果我们为 x 和 y 取 20，我们也会得到正确答案：
总是一样的动作
你只能向右或向下移动 - 所以向下移动一格的唯一方法是向下移动，向右移动的唯一方法是向右移动（并且有无法向左/向上移动） - 所以你移动的数量 - 无论你走哪条路 - 总是相同的。
即正好格子的高度向下移动，正好格子的宽度向右移动。
例如在 4x3 网格上，您正好向右移动 4 次，向下移动 3 次：
所以一开始你有一个你可以做的所有动作的“包”，在上面的例子中它是 {⮞,⮞,⮞,⮞,⮟,⮟,⮟} 并且在路径的每个点你都可以选择是否要走从你的包里拿出一个 ⮞ 或一个 ⮟，向那个方向移动（除非你 运行 一个，在那种情况下你只有一个选择）。
这个“袋子”的数学术语是 Multiset。
在上面的例子中我们也可以把它写成{⮞⁴, ⮟³}，以使其更短。
现在要回答有多少条可能的路径这个问题，我们需要找出有多少种可能的方式来使用多重集中的元素，例如：
⮞⮞⮞⮟⮞⮟⮟、⮟⮞⮟⮞⮟⮞⮞、等等...
所以我们正在寻找多重集的所有可能排列（长度与多重集中的元素相同）
这叫做multiset permutation，它的公式很容易记住：
其中 n 是多重集中的项目总数（上例中为 7），m₁、m₂ 等是每个元素的计数在集合中（在这种情况下，我们只有 m₁ = 4 和 m₂ = 3，所以 n = 7）。
因此，要将其概括为大小为 x × y 的网格，可能路径数的公式为：
如果将 x 和 y 的 20 代入上述等式，对于 20 × 20 网格中可能的路径数，您将得到相同的正确答案 137846528820。
这种方法还有一个好处，它适用于 2 个以上的维度，例如你也可以用这个解决这个谜题的 3 维变体。