从 A[a,b] 到 A[c,d] 的不同非循环路径的计数？

我正在编写一个推箱子求解器，用于娱乐和练习，它使用一个简单的算法（类似于 BFS，但略有不同）。

现在我想估计它的运行时间（O 和 omega）。但需要知道如何计算网络中从一个顶点到另一个顶点的非循环路径的计数。 实际上我想要一个表达式来计算 m*n 顶点矩阵的两个顶点之间的有效路径数。

有效路径：

• 访问每个顶点 0 次或 1 次。
• 没有电路

例如，这是一个有效的路径：

替代文本 http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png http://megapic.ir/images/f1hgyp5yxcu8887kfvkr.png

但这不是：

替代文本 http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png http://megapic.ir/images/wnnif13ir5gaqwvnwk9d.png

需要一种方法来查找两个顶点之间所有非循环路径的计数a and b.

欢迎对解决方法和技巧提出意见。

这不是一个解决方案，但也许你可以进一步思考这个想法。问题是您还需要计算最长的可能路径才能获得所有路径。这最长路径问题 http://en.wikipedia.org/wiki/Longest_path_problem对于一般图来说是 NP 完全的，因此即使对于相对较小的图（8x8 或更大）也会花费很长的时间。

想象一下起始顶点位于矩阵的左上角，结束顶点位于矩阵的右下角。

• 对于 1x2 矩阵，只有 1 条可能的路径
• 2x2 矩阵 => 2***1** 路径 => 2
• 3x2 矩阵 => 2***2** 路径 => 4
• 3x3 矩阵 => 2***4** + 2*2 路径 => 12
• 3x4 矩阵 => 2***12** + 12 + 2 条路径 => 38

每次我都会将先前计算的结果合并为当前路径数。对于这样的平面图，可能有一个紧密的公式，甚至可能有很多理论，但我太愚蠢了......

您可以使用以下 Java（抱歉，我不是 C++ 专家:-/）片段来计算较大矩阵的可能路径：

public static void main(String[] args) {
    new Main(3, 2).start();
}
int xSize;
int ySize;
boolean visited[][];

public Main(int maxX, int maxY) {
    xSize = maxX;
    ySize = maxY;
    visited = new boolean[xSize][ySize];
}

public void start() {
    // path starts in the top left corner
    int paths = nextCell(0, 0);
    System.out.println(paths);
}

public int nextCell(int x, int y) {
    // path should end in the lower right corner
    if (x == xSize - 1 && y == ySize - 1)
        return 1;

    if (x < 0 || y < 0 || x >= xSize || y >= ySize || visited[x][y]) {
        return 0;
    }

    visited[x][y] = true;
    int c = 0;
    c += nextCell(x + 1, y);
    c += nextCell(x - 1, y);
    c += nextCell(x, y + 1);
    c += nextCell(x, y - 1);
    visited[x][y] = false;
    return c;
}

=>

• 4x4 => 184
• 5x5 => 8512
• 6x6 => 1262816
• 7x7（即使是这个简单的情况也需要很多时间！）=> 575780564

这意味着您可以（仅在理论上）计算从 MxM 矩阵的任意位置到右下角的所有可能路径，然后使用该矩阵快速查找路径数。动态规划 http://en.wikipedia.org/wiki/Dynamic_programming（使用之前的计算结果）可以稍微加快速度。