algorithm - 在 n x m 矩阵中放置 k 条不相交路径的方法有多少

Question

所以我有一个 n x m矩阵。我需要找出有多少种不同的方式可以放置 k此矩阵上的不相交路径。每条路径都满足这些条件:

-它从第一列开始。

-在最后一个结束。

-如果路径结束于(a,b)对于 b<m , 那么下一步只能上格(a',b+1) , 其中|a'-a|<=1 (意思是我沿对角线向下移动一步，元组中的第一个是 x 坐标，第二个是 y 坐标)。

-我知道n很小(比如 8)，所以它不会破坏算法的复杂性。

明显的蛮力法(递归探索所有可能的选项)是正确的，但是因为m可能非常大，在这里没有用。

我在思考这些不相交的路径时遇到了极大的麻烦。对于 k=1事情会很简单。我们会将数组的每个元素与其结束的路径数相关联，并使用以下公式递归计算它 tab[m][n]=tab[m-1][n-1]+tab[m-1][n+1] .但是什么时候 k=2 ？我认为如果我能解决这个问题，我可以很容易地将它扩展为更大的 k的，但我在考虑成本不是指数级的算法时遇到了麻烦。

Answer 1

我无法建立一个非指数算法，但至少我相信我可以将问题归纳为 k>=2，前提是 k 小于 n 且 n 相对较小(比如 8)

假设我们正在查看一个 8 行 M 列矩阵，其中 M 很大，并且您需要适应从左到右一直摆动的 k 条路径。

单列可以用 C(8,k) 种可能的配置绘制，最大大约为 70。你应该可以进一步建立一个70x70的矩阵，表明每个配置可以连续到其他列配置，遵守你的路径规则。

上面的矩阵实际上是一个70个顶点的无向图。

问题现在已经转换为找到图中所有 M 长度的路径。

进一步编辑:如果您只想获得可能的 M 列配置的总数，多项式算法是可能的，如下所示:

考虑以下已经获得:

N-1 列配置的总计数，其中计数根据最后一列配置求和(例如，5 个配置以配置 1 结尾，46 个以配置 2 结尾，等等... 28 个以配置 70 结尾)。这可以用数组或哈希表表示

您可以使用 70x70 矩阵轻松导出 N 列配置的下一个数组。

因此，上面形成了一个多项式时间算法来计算 M Column 配置的总数。你只需要从 N=1 开始