在六边形网格上可以找到多少条长度为 n 且起点和终点相同的路径？
How many paths of length n with the same start and end point can be found on a hexagonal grid?
给定，起点和终点相同的特殊情况呢？
我的情况的另一个变化是我们必须步步为营。可以找到多少条这样的路径，什么是最有效的方法？我想这会是某种随机游走？
目前我的想法是，因为我们必须始终return到我们的起点，考虑n/2可能会更容易。在每一步，除了第 n/2 步，我们有 6 个选择。在 n/2，我们有不同数量的选择，具体取决于 n 是偶数还是奇数。根据我们所处的位置（我们之前做出的选择），我们也有不同数量的选择。例如，如果 n 是偶数，我们直接出去，我们在 n/2 只有一个选择，回去。但是如果n是偶数，我们没有直接出去，我们就有更多的选择。
这个转折点的所有情况，我都难以直截了当。
我走在正确的轨道上吗？
说清楚，我只是想数一下路径。所以我想我们正在寻找一些条件排列？
这个版本的组合问题看起来实际上有一个简短的公式作为答案。
尽管如此，一般版本，包括这个问题和原始问题，都可以通过动态编程在 O (n^3) 时间和 O (n^2) 内存中解决。
考虑一个六边形网格，它从目标单元格向各个方向跨越至少 n 步。
引入坐标系，使每个单元格的坐标格式为 (x, y).
令 f (k, x, y) 为在完成 k 步后从起始单元格到达单元格 (x, y) 的方法数。
这些可以递归或迭代计算：
f (k, x, y) 只是六个相邻单元格 (x', y').
的 f (k-1, x', y') 之和
起始单元格 (xs, ys) 的基本情况是 f (0, xs, ys) = 1，其他每个单元格 (x, y) 的基本情况是 f (0, x, y) = 0。
您的特定问题的答案是值 f (n, xs, ys)。
迭代解的一般结构如下：
let f be an array [0..n] [-n-1..n+1] [-n-1..n+1] (all inclusive) of integers
f[0][*][*] = 0
f[0][xs][ys] = 1
for k = 1, 2, ..., n:
for x = -n, ..., n:
for y = -n, ..., n:
f[k][x][y] =
f[k-1][x-1][y] +
f[k-1][x][y-1] +
f[k-1][x+1][y] +
f[k-1][x][y+1]
answer = f[n][xs][ys]
好吧，我在这里作弊了：上面的解决方案适用于矩形网格，其中单元格 (x, y) 有四个邻居。
六边形的六个邻居取决于我们如何精确地引入坐标系。
我更喜欢其他坐标系而不是原始问题中的坐标系。
This link gives an overview of the possibilities, and here 是 StackExchange 上该页面的简短摘要，以防止 link 腐烂。
我个人的偏好是轴坐标。
请注意，如果我们允许站着不动而不是移动到其中一个邻居，那只会在公式中再添加一项 f[k-1][x][y]。
这同样适用于使用三角形、矩形或六边形网格，在网格中使用 4 或 8 或其他一些邻居子集，等等。
如果您想到达其他目标单元格 (xt, yt)，那也包括在内：答案是值 f[n][xt][yt]。
同样，如果您有多个开始或目标单元格，并且可以从其中任何一个开始和结束，只需更改基本情况或对单元格中的答案求和即可。
解决方案的总体布局保持不变。
这显然适用于 n * (2n+1) * (2n+1) * number-of-neighbors，即 O(n^3) 对于任何常数数量的邻居（4 或 6 或 8...）一个单元格在我们的特定问题中可能具有。
最后注意，在主循环的第k步，我们只需要两层数组f：f[k-1]是源层，[=35] =] 是目标图层。
因此，我们可以只存储两层，而不是一直存储所有层，因为我们不需要更多：一层用于奇数 k，一层用于偶数 k。
仅使用两层就像将所有 f[k] 和 f[k-1] 分别更改为 f[k%2] 和 f[(k-1)%2] 一样简单。
这将内存要求从 O(n^3) 降低到 O(n^2)，如开头所宣传的那样。
对于更数学的解决方案，这里有一些可能会导致一个的步骤。
首先，考虑以下问题：从(xs, ys)到(xt, yt)的路数是n步，每步向北、西、南移动一个方格, 还是东?
要从 x = xs 到达 x = xt，我们需要朝着正确的方向迈出 H = |xt - xs| 步（不失一般性，让它向东）。
同样，我们需要在另一个正确的方向上 V = |yt - ys| 步才能到达所需的 y 坐标（让它在南边）。
我们剩下 k = n - H - V "free" 个台阶，可以任意拆分成一对南北台阶和一对东西台阶。
显然，如果 k 是奇数或负数，则答案为零。
因此，对于 "free" 步的每个可能拆分 k = 2h + 2v 进入水平和垂直步，我们要做的是构造一条向东 H+h 步的路径，h 向西，V+v 向南，v 向北。这些步骤可以按任何顺序完成。
这样的序列的个数是multinomial coefficient，等于n! / (H+h)! / h! / (V+v)! / v!。
要最终得到答案，只需对所有可能的 h 和 v 求和，使得 k = 2h + 2v。
如果我们预先计算阶乘，此解决方案将在 O(n) 中计算答案，也在 O(n) 中，并考虑所有算术运算需要 O(1) 时间。
对于六边形网格，一个复杂的特征是水平和垂直阶梯之间没有明确的分隔。
尽管如此，只要给定起始单元格和六个方向中每个方向的步数，我们就可以找到最终单元格，而不管这些步骤的顺序如何。
因此，解决方案如下：
- 枚举
n的所有可能划分为六个被加数a1、...、a6.
- 对于每个这样的分区，找到最后一个单元格。
- 对于最终单元格是我们想要的单元格的每个分区，将多项式系数
n! / a1! / ... / a6! 添加到答案中。
正是如此，这需要 O(n^6) 时间和 O(1) 内存。
通过仔细研究六边形网格上不同方向之间的关系，也许我们实际上可以只考虑到达目标单元格的分区，而完全忽略所有其他分区。
如果是这样，这个解决方案可以优化到至少一些 O(n^3) 或 O(n^2) 时间，也许进一步与体面的代数技能。
给定
我的情况的另一个变化是我们必须步步为营。可以找到多少条这样的路径，什么是最有效的方法？我想这会是某种随机游走？
目前我的想法是，因为我们必须始终return到我们的起点，考虑n/2可能会更容易。在每一步，除了第 n/2 步，我们有 6 个选择。在 n/2，我们有不同数量的选择，具体取决于 n 是偶数还是奇数。根据我们所处的位置（我们之前做出的选择），我们也有不同数量的选择。例如，如果 n 是偶数，我们直接出去，我们在 n/2 只有一个选择，回去。但是如果n是偶数，我们没有直接出去，我们就有更多的选择。
这个转折点的所有情况，我都难以直截了当。
我走在正确的轨道上吗？
说清楚，我只是想数一下路径。所以我想我们正在寻找一些条件排列？
这个版本的组合问题看起来实际上有一个简短的公式作为答案。
尽管如此，一般版本，包括这个问题和原始问题，都可以通过动态编程在 O (n^3) 时间和 O (n^2) 内存中解决。
考虑一个六边形网格，它从目标单元格向各个方向跨越至少 n 步。
引入坐标系，使每个单元格的坐标格式为 (x, y).
令 f (k, x, y) 为在完成 k 步后从起始单元格到达单元格 (x, y) 的方法数。
这些可以递归或迭代计算：
f (k, x, y) 只是六个相邻单元格 (x', y').
f (k-1, x', y') 之和
起始单元格 (xs, ys) 的基本情况是 f (0, xs, ys) = 1，其他每个单元格 (x, y) 的基本情况是 f (0, x, y) = 0。
您的特定问题的答案是值 f (n, xs, ys)。
迭代解的一般结构如下：
let f be an array [0..n] [-n-1..n+1] [-n-1..n+1] (all inclusive) of integers
f[0][*][*] = 0
f[0][xs][ys] = 1
for k = 1, 2, ..., n:
for x = -n, ..., n:
for y = -n, ..., n:
f[k][x][y] =
f[k-1][x-1][y] +
f[k-1][x][y-1] +
f[k-1][x+1][y] +
f[k-1][x][y+1]
answer = f[n][xs][ys]
好吧，我在这里作弊了：上面的解决方案适用于矩形网格，其中单元格 (x, y) 有四个邻居。
六边形的六个邻居取决于我们如何精确地引入坐标系。
我更喜欢其他坐标系而不是原始问题中的坐标系。
This link gives an overview of the possibilities, and here 是 StackExchange 上该页面的简短摘要，以防止 link 腐烂。
我个人的偏好是轴坐标。
请注意，如果我们允许站着不动而不是移动到其中一个邻居，那只会在公式中再添加一项 f[k-1][x][y]。
这同样适用于使用三角形、矩形或六边形网格，在网格中使用 4 或 8 或其他一些邻居子集，等等。
如果您想到达其他目标单元格 (xt, yt)，那也包括在内：答案是值 f[n][xt][yt]。
同样，如果您有多个开始或目标单元格，并且可以从其中任何一个开始和结束，只需更改基本情况或对单元格中的答案求和即可。
解决方案的总体布局保持不变。
这显然适用于 n * (2n+1) * (2n+1) * number-of-neighbors，即 O(n^3) 对于任何常数数量的邻居（4 或 6 或 8...）一个单元格在我们的特定问题中可能具有。
最后注意，在主循环的第k步，我们只需要两层数组f：f[k-1]是源层，[=35] =] 是目标图层。
因此，我们可以只存储两层，而不是一直存储所有层，因为我们不需要更多：一层用于奇数 k，一层用于偶数 k。
仅使用两层就像将所有 f[k] 和 f[k-1] 分别更改为 f[k%2] 和 f[(k-1)%2] 一样简单。
这将内存要求从 O(n^3) 降低到 O(n^2)，如开头所宣传的那样。
对于更数学的解决方案，这里有一些可能会导致一个的步骤。
首先，考虑以下问题：从(xs, ys)到(xt, yt)的路数是n步，每步向北、西、南移动一个方格, 还是东?
要从 x = xs 到达 x = xt，我们需要朝着正确的方向迈出 H = |xt - xs| 步（不失一般性，让它向东）。
同样，我们需要在另一个正确的方向上 V = |yt - ys| 步才能到达所需的 y 坐标（让它在南边）。
我们剩下 k = n - H - V "free" 个台阶，可以任意拆分成一对南北台阶和一对东西台阶。
显然，如果 k 是奇数或负数，则答案为零。
因此，对于 "free" 步的每个可能拆分 k = 2h + 2v 进入水平和垂直步，我们要做的是构造一条向东 H+h 步的路径，h 向西，V+v 向南，v 向北。这些步骤可以按任何顺序完成。
这样的序列的个数是multinomial coefficient，等于n! / (H+h)! / h! / (V+v)! / v!。
要最终得到答案，只需对所有可能的 h 和 v 求和，使得 k = 2h + 2v。
如果我们预先计算阶乘，此解决方案将在 O(n) 中计算答案，也在 O(n) 中，并考虑所有算术运算需要 O(1) 时间。
对于六边形网格，一个复杂的特征是水平和垂直阶梯之间没有明确的分隔。 尽管如此，只要给定起始单元格和六个方向中每个方向的步数，我们就可以找到最终单元格，而不管这些步骤的顺序如何。 因此，解决方案如下：
- 枚举
n的所有可能划分为六个被加数a1、...、a6. - 对于每个这样的分区，找到最后一个单元格。
- 对于最终单元格是我们想要的单元格的每个分区，将多项式系数
n! / a1! / ... / a6!添加到答案中。
正是如此，这需要 O(n^6) 时间和 O(1) 内存。
通过仔细研究六边形网格上不同方向之间的关系，也许我们实际上可以只考虑到达目标单元格的分区，而完全忽略所有其他分区。
如果是这样，这个解决方案可以优化到至少一些 O(n^3) 或 O(n^2) 时间，也许进一步与体面的代数技能。