2

在大小为 m*n 的矩形网格中，从 (0,0) 到 (m,n) 的路径数（没有回溯）是 (m+n)!/(m!*n!)。现在，如果网格中有我们想要避开的某些点，我们如何计算避开这些点的路径数？

4

3 回答 3

2

定义解的（递归）方程如​​下：

  • 从 (m,n) 到 (m,n) 的单调路径数为 1
  • 从任何禁止点到 (m,n) 的单调路径数为 0，与第一个坐标大于 m 或第二个大于 n 的点相同。
  • 从任何其他点 (x,y) 到 (m,n) 的单调路径数是以下各项的总和：
    • 从 (x+1,y) 到 (m,n) 的路径数和
    • 从 (x,y+1) 到 (m,n) 的路径数（参见上文处理使我们脱离网格的增量）

显然，正如 Qnan 所说，您需要使用动态编程（即记住部分解决方案以避免指数时间）来解决这些问题（0,0）。

于 2012-09-05T09:49:39.223 回答
1

我认为对于完全k被阻塞的网格没有合理的分析解决方案，但是可以使用动态编程算法计算路径。

解析解很麻烦，因为阻塞路径的数量不仅取决于阻塞节点的数量和每个节点的位置，还取决于它们的相对位置。例如，在 4x4 网格中，这两种配置给出了非常不同的结果：

....      ....
..x.      .xx.
.x..      ....
....      ....

很容易看出，前者只允许两条单调路径，而后者至少有 5 条。

于 2012-09-05T09:36:33.080 回答
0

这里一个自然的问题是要问：对于任何给定的 k，避免 k 个点的集合 S 的单调路径的最大数量是多少（其中最大值是所有可能的集合 S）？

这实际上是 Johnson、Leader 和 Russell 的一篇论文中提出的一个开放问题：http: //arxiv.org/pdf/1309.4643.pdf

于 2015-08-06T15:20:58.687 回答