logo标签列表

给定一个矩阵，有多少种方法可以访问矩阵中的所有点？

algorithmgraphmatrixtraversal
3
有一个m*n的矩阵。从矩阵中的一点出发，你可以移动到八个相邻的点（上、下、左、右、左上、左下、右上、右下）。如果某个方向上的点已经被访问过，你可以继续朝着这个方向移动到下一个未被访问的点。不能访问已被访问过的点，但是可以通过已经访问过的相邻点来访问其他未访问的点。例如，当前点为(5,5)：
1. 如果(5,4)已被访问，则可以移动到(5,3)。如果(5,3)也已被访问，则可以移动到(5,2)。 2. 对角线方向同理。如果(4,4)已被访问，则可以移动到(3,3)等等。 现在需要访问矩阵上的所有点，有多少种方法？（第一个和最后一个点可以是任何一个点。）
1
我会说有很多种可能。例如，拿一个1*n的矩阵来说。每一种可能的路径选择都形成了一个正确的序列，总共有2^(n-1)种组合。现在如果你再加上第二行，事情就变得非常复杂了（至少对我而言是这样）。我猜测答案应该是2^(n*m-1)，但是没有证明。 - Vesper
1
当m=n=2时，有4个点。结果是4！=24。因此，2^(m*n-1)=2^3=8是错误的。 - fanjindou
让我明确一下。你的意思是“路径（一系列单元格）从给定的（x，y）点开始访问每个单元格，并且不与自身重叠”？如果你真的是这个意思，那就相当棘手了，我只会在你确认后再研究它。 - Apiwat Chantawibul
@Billiska 我们需要找到从任意一个点开始访问每个单元格的路径数量。已访问的点不能再次访问。但是我们可以通过已访问的点 A 经过，以访问与 A 方向相同的相邻点。 - fanjindou
当你说“穿过A”时，你的意思是如果我在(5,5)，并且(5,6)已经被访问过，我可以穿过(5,6)并访问接下来的(5,7)吗？ - Apiwat Chantawibul
@Billiska 是的。你可以在一个方向上访问下一个未被访问的相邻点，因此你不能通过(5,6)来访问(4,6)，后者是(5,6)的相邻点。 - fanjindou
2个回答
3
这与棋盘上的希腊钥匙旅行数量 / 即网格上的自避行走数量（参见维基百科）相似。

但在您的变体中，您可以向8个方向移动，而不是4个。

对于原始版本，似乎没有已知的公式适用于大量的n。 这里和这里有解释。

我编写了一个简短的C++程序来计算您的情况（我猜不是最有效的）：

const size_t _DIM_m= 4; // cols
const size_t _DIM_n= 4; // rows

typedef struct // we want to pass the array by value (for recursion), so we'll wrap it with a struct
{
    bool g[_DIM_m][_DIM_n];
} Grid;

int Traverse(Grid g, int i, int j, int nVisit= 0)
{
    int nWays= 0;

    ++nVisit;        // points visited so far
    g.g[i][j]= true;
    Grid h= g;

    // original problem:
    if (                   (0        != j) && (!g.g[i  ][j-1])) nWays+= Traverse(g, i  , j-1, nVisit); // up
    if (                   (_DIM_n-1 != j) && (!g.g[i  ][j+1])) nWays+= Traverse(g, i  , j+1, nVisit); // down
    if ((0        != i)                    && (!g.g[i-1][j  ])) nWays+= Traverse(g, i-1, j  , nVisit); // left
    if ((_DIM_m-1 != i)                    && (!g.g[i+1][j  ])) nWays+= Traverse(g, i+1, j  , nVisit); // right

    // additions for your problem:
    if ((_DIM_m-1 != i) && (0        != j) && (!g.g[i+1][j-1])) nWays+= Traverse(g, i+1, j-1, nVisit); // upper right
    if ((0        != i) && (_DIM_n-1 != j) && (!g.g[i-1][j+1])) nWays+= Traverse(g, i-1, j+1, nVisit); // lower left
    if ((0        != i) && (0        != j) && (!g.g[i-1][j-1])) nWays+= Traverse(g, i-1, j-1, nVisit); // upper left
    if ((_DIM_m-1 != i) && (_DIM_n-1 != j) && (!g.g[i+1][j+1])) nWays+= Traverse(g, i+1, j+1, nVisit); // lower right

    if (_DIM_m * _DIM_n == nVisit) ++nWays; // if all points visited
    return nWays;
}

int _tmain(int argc, _TCHAR* argv[])
{
    Grid g;

    for (size_t i= 0; i<_DIM_m; i++)
        for (size_t j= 0; j<_DIM_n; j++)
            g.g[i][j]= false;

    int nWays= Traverse(g, 0, 0); // starting point: 0, 0

    cout << nWays << endl;
    system ("pause");

    return 0;
}

矩形网格的结果，从 (0,0) 开始：

  • _DIM= 1: 1
  • _DIM= 2: 6
  • _DIM= 3: 138
  • _DIM= 4: 37948
  • _DIM= 5: 很多...

请注意，从不同的起点开始时，结果会发生变化。

编辑：

原问题已被修改：添加了 pass-through。以下是此情况的解决方案：

const size_t _DIM_m= 4; // cols
const size_t _DIM_n= 4; // rows

typedef struct // we want to pass the array by value (for recursion), so we'll wrap it with a struct
{
    bool g[_DIM_m][_DIM_n];
} Grid;

inline bool InRange(int i, int j)
{
    return (i >= 0) && (i < _DIM_m) && (j >= 0) && (j < _DIM_n);
}

int Traverse(Grid g, int i, int j, int nVisit= 0)
{
    int nWays= 0;

    ++nVisit;        // points visited so far
    g.g[i][j]= true;
    Grid h= g;

    int i1,j1;

    i1= i; j1= j;
    do { --j1;       } while (InRange(i1,j1) && (g.g[i1][j1]));                    // up          (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { ++j1;       } while (InRange(i1,j1) && (g.g[i1][j1]));                    // down        (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { --i1;       } while (InRange(i1,j1) && (g.g[i1][j1]));                    // left        (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { ++i1;       } while (InRange(i1,j1) && (g.g[i1][j1]));                    // right       (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { ++i1; --j1; } while (InRange(i1,j1) && (g.g[i1][j1]));                    // upper right (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { --i1; ++j1; } while (InRange(i1,j1) && (g.g[i1][j1]));                    // lower left  (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { --i1; --j1; } while (InRange(i1,j1) && (g.g[i1][j1]));                    // upper left  (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    i1= i; j1= j;
    do { ++i1; ++j1; } while (InRange(i1,j1) && (g.g[i1][j1]));                    // lower right (pass through)
    if                       (InRange(i1,j1)) nWays+= Traverse(g, i1, j1, nVisit);

    if (_DIM_m * _DIM_n == nVisit) ++nWays; // if all points visited
    return nWays;
}

一个从(0,0)开始的矩形网格的结果如下：

  • _DIM= 1: 1
  • _DIM= 2: 6
  • _DIM= 3: 1020
  • _DIM= 4: 8071182
  • _DIM= 5: 很多...
在Greek-key tours和这个问题之间有一些区别。在这个问题中，你不仅可以移动到八个相邻点，还可以移动到八个相邻点的八个相邻点。(0,0)可以移动到(1,1)。如果(1,1)被访问过，(0,0)可以移动到(2,2)。如果(1,1)和(2,2)都被访问过，(0,0)可以移动到(3,3)... - fanjindou
@fanjindou：好的，我看到你编辑了你的问题...我会相应地编辑我的答案... - Lior Kogan
我认为你的算法是深度优先搜索算法。当m*n非常大时，解决问题需要很长时间。 - fanjindou
@fanjindou：没错，这只是一个概念验证。 - Lior Kogan
0
3
这句话的意思是“字面上与旅行推销员问题没有任何关系，后者是一个优化问题。” - Justin L.
此外，TSP问题可以编码成无环图并存储在ZDD中，ZDD可以返回组合的总数。Donald Knuth的圣诞树讲座专门讨论了这种类型的问题，并给出了一个例子，即汽车通过高速公路一次性访问每个州。这似乎与通过图形表示特别返回计数非常相似。我认为这种关联可能会有所帮助，如果没有其他的话。 - Jeremy Adsitt
1
对不起，我的评论不必要地粗鲁了 :( 那天我不确定自己怎么了。 - Justin L.
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接