7

给定一个像这样的简单无向图：

在此处输入图像描述

从 D、A、V_startB或C V_start（.V_startn

我正在考虑进行深度优先搜索，当 时停止steps > n || (steps == n && vertex != V_start)，但是，如果，例如，这将变得相当昂贵n = 1000000。我的下一个想法使我将 DFS 与动态编程相结合，但是，这就是我遇到的问题。

（这不是家庭作业，只是我为了学习而被困在玩图表和算法。）

我将如何在合理的时间内解决这个问题n？

4

2 回答 2

20

这个任务是通过矩阵乘法来解决的。

创建包含 0 和 1 的矩阵nx （如果有从到的路径，则为单元格 1 ）。将此矩阵乘以自身时间（考虑使用快速矩阵求幂）。然后在矩阵的单元格中，您有长度从 开始和结束的路径数。nmat[i][j]ijkmat[i][j]kij

注意：快速矩阵求幂与快速求幂基本相同，只是将数字乘以矩阵。

注意2：假设n是图中的顶点数。然后我在这里提出的算法以 O(log k * n 3 ) 的时间复杂度运行，并且具有 O(n 2 ) 的内存复杂度。如果您使用此处所述的优化矩阵乘法，则可以对其进行更多改进。那么时间复杂度将变为 O(log k * n log 2 7 )。

编辑应Antoine 的要求，我解释了为什么该算法实际上有效：

我将通过归纳证明该算法。归纳的基础很明显：最初我在矩阵中有长度为 1 的路径数。

让我们假设直到 的幂k如果我将矩阵提升到 的幂k我在长度介于和之间mat[i][j]的路径数量中。kij

现在让我们考虑下一步k + 1。很明显，每条长度路径k + 1都由长度前缀k和一条边组成。这基本上意味着k + 1可以通过以下方式计算长度路径（这里我表示mat_pow_k矩阵的kth 次方）

num_paths(x, y, k + 1) = sum i=0 i<n mat_pow_k[x][i] * mat[i][y]

再次：n是图中的顶点数。这可能需要一段时间才能理解，但基本上mat[i][y]只有在x和之间存在直接边时，初始矩阵的单元格中才有 1 y。我们计算这种边缘的所有可能前缀以形成长度路径k + 1。

但是我写的最后一件事实际上是计算 的k + 1st 幂mat，这证明了归纳的步骤和我的陈述。

于 2012-04-27T06:59:20.723 回答
2

这很像一个动态规划问题：

  1. 将 af[n][m] 定义为从起点到点 n 的路径数，步长为 m
  2. 从每个点 n 到其相邻的 k，您有公式： f[k][m+1] = f[k][m+1] + f[n][m]
  3. 在初始化中，所有 f[n][m] 都将为 0，但 f[starting_point][0] = 1
  4. 所以你可以计算最终结果

伪代码：

memset(f, 0, sizeof(f));
f[starting_point][0] = 1;
for (int step = 0; step < n; ++step) {
    for (int point = 0; point < point_num; ++point) {
        for (int next_point = 0; next_point < point_num; ++ next_point) {
            if (adjacent[point][next_point]) {
                f[next_point][step+1] += f[point][step];
            }
        }
    }
}
return f[starting_point][n]
于 2012-04-27T11:22:39.357 回答