12

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

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

有效路径：

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

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

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

但这不是：

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

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

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

4

5 回答 5

4

计算图中简单路径数量的一般问题是#P complete。一些#P-complete 问题具有完全多项式随机逼近方案，而有些则没有，但您声称对逼近不感兴趣。也许有一种方法可以利用网格结构，就像计算 Tutte 多项式一样，但我对如何做到这一点没有任何想法。

于 2010-03-24T22:29:27.160 回答
4

不是一个解决方案，但也许你可以进一步思考这个想法。问题是您还需要计算获得所有路径的最长可能路径。对于一般图，最长路径问题是 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 矩阵的任何位置到右下角的所有可能路径，然后使用该矩阵快速查找路径数。动态编程（使用以前的计算结果）可以加快速度。

于 2010-03-28T11:02:15.337 回答
3

Euler 项目有一个类似但不太普遍的问题：http ://projecteuler.net/index.php?section=problems&id=237

我认为论坛中描述的一些解决方案可以扩展以解决您的一般情况。这是一个非常困难的问题，特别是对于您的一般情况。

要访问他们的论坛，您首先需要解决问题。我不会在这里发布答案，也不会链接到列出答案的某个站点，您可以通过搜索非常明显的内容在 google 上轻松找到该站点。

于 2010-03-23T16:39:34.943 回答
2

这是数学中的一个悬而未决的问题，直接应用于化学和物理学，用它来模拟聚合物键。最早在这方面所做的一些工作是在曼哈顿项目（核弹二战）期间完成的。

它更好地称为自我避免步行问题。

我在大学数学系度过了一个夏天，研究了一种称为枢轴算法的蒙特卡罗算法，以逼近给定长度的自我避免步行次数的渐近拟合参数n。

请参阅 Gordon Slade 的名为“ The Self Avoiding Walk ”的优秀书籍，了解迄今为止用于解决此问题的各种技术类型。

This is a very complex problem and I wonder what your motivation may be for considering it. Perhaps you can find a simpler model for what you want, because Self Avoiding Walks are not simple at all.

于 2010-05-26T16:51:50.593 回答
1

显示边缘的矩阵会起作用吗？考虑构建一个矩阵来显示边的位置，即 [a,b]=1 <=> a->b 是图中的边，否则为 0。现在，将此矩阵提高到各种幂，以显示使用 n 步在顶点之间存在多少种方法，然后将它们相加得到结果。这只是解决问题的一种方法的想法，可能还有其他方法可以解决问题。

我想知道这是否属于MathOverflow，作为另一个想法

没错，一旦你有一个零矩阵，你就可以像你的情况一样停止求幂，在 3 之后没有很多地方可以去，但是从 1 到 3 的路径将是直接路径和经过 2 的路径，所以在找到全零之前，只有几个矩阵要加在一起。

我认为应该有一种方法来计算 n^(n+1) 的界限，其中 n 是图中的顶点数，这将指示一个停止点，因为到那时，每个顶点都将是去过一次。我不确定如何解决循环路径问题，或者可以假设图形没有循环？

于 2010-03-23T15:51:24.487 回答