我正在写一个推箱子求解器的乐趣和实践，它使用一个简单的算法（像BFS有一点区别的）。

I'm writing a sokoban solver for fun and practice, it uses a simple algorithm (something like BFS with a bit of difference).

现在我想估计它的运行时间（O和欧米茄）。但需要知道如何计算的非循环路径计数从一个顶点到另一个网络中。 其实我想一个前pression，计算的有效路径数量，顶点时* n矩阵的两个顶点之间。

now i want to estimate its running time ( O and omega). but need to know how to calculate count of acyclic paths from a vertex to another in a network. actually I want an expression that calculates count of valid paths, between two vertices of a m*n matrix of vertices.

有效的路径：

在访问每个顶点0次或一次。 在没有电路

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

for example this is a valid path:

，但这不是

所需要的是一个方法来找到的所有非循环路径计数之间的两个顶点的一的和的 B 的。

What is needed is a method to find count of all acyclic paths between the two vertices a and b.

解决方法和技巧，评论欢迎。

comments on solving methods and tricks are welcomed.

推荐答案

不是一个解决方案，但也许你可以稍微再想到这个主意。问题是，你也需要计算最长的可能路径来获取所有路径。该最长路径问题是NP完全为一般图，因此它会得到一个很长的时间甚至相对小图（8×8或更高）。

Not a solution but maybe you can think this idea a bit further. The problem is that you'll need to calculate also the longest possible path to get all paths. The longest path problem is NP complete for general graphs, so it will get a very long time even for relative small graphs (8x8 and greater).

想象一下，开始顶点是在顶部，左上角和结束的顶点是在矩阵下，右下角。

Imagine the start-vertex is in the top, left corner and the end vertex is in the lower, right corner of the matrix.

对于一个1x2的矩阵中，只有一个可能的路径 2×2矩阵=> 2 * 1 路径=> 2 的3x2矩阵=> 2 * 2 路径=> 4 在3x3矩阵=> 2 * 4 + 2 * 2路=> 12 3×4矩阵=> 2 * 12 + 12 + 2路径=> 38 For a 1x2 matrix there is only 1 possible path 2x2 matrix => 2*1 paths => 2 3x2 matrix => 2*2 paths => 4 3x3 matrix => 2*4 + 2*2 paths => 12 3x4 matrix => 2*12 + 12 + 2 paths => 38

每次我结合从previous计算路径的当前数量的结果。这可能是因为有这样的平面图密切公式推，也许甚至有许多理论认为的，但我太愚蠢了这...

Everytime I combined the results from the previous calculation for the current number of paths. It could be that there is a close formular for such a planar graph, maybe there is even a lot of theory for that, but I am too stupid for that ...

您可以使用以下Java（对不起，我不是一个C ++专家： - /）片段来计算更大的矩阵可能的路径：

You can use the following Java (sorry, I am not a c++ expert :-/) snippet to calculate possible paths for larger matrices:

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;
}

=>

在4×4 => 184 在5×5 => 8512 在6×6 => 1262816 为7x7（即使这个简单的情况下，需要花费大量的时间！）=> 575780564

这意味着你可以（只在理论上）计算从为M×M矩阵下，右下角的任意位置上所有可能的路径，然后使用这个矩阵来快速查找路径数量。 动态规划（使用previous计算结果）可能的事情加快一点。

This means you could (only theoretically) compute all possible paths from any position of a MxM matrix to the lower, right corner and then use this matrix to quickly look up the number of paths. Dynamic programming (using previous calculated results) could speed up things a bit.