algorithm - 在给定顶点和一些限制的情况下查找图中的所有路径

Question

我尝试为以下问题提出一个算法，但直到现在我都无法解决它。我猜这个问题属于图形问题的范畴。也许有人可以给我提示正确的关键字/算法。 :)

所以我的问题是:我有一组顶点和一些限制。我尝试根据限制找到顶点之间的所有边。

• 我有一个 nxn 矩阵的顶点
• 我有一个开始 (S) 和一个结束 (E)(听起来像一个网络/流程)
• S和E的列和行中的顶点可以忽略
• S位于矩阵中的(1,1)处，E位于(n,n)处
• 图形是从 S 到 E 的，也就是说，我必须找到一条从左上角到右下角的路。我不能回去。
• 对于通过矩阵的每一步，我都必须增加行和列
• 我必须至少穿过 S 和 E 之间的一个顶点

让我们看一下这个例子:

S - - -
- 1 2 -
- 3 4 -
- - - E

我可以识别路径

• S > 1 > 4 > E
• S > 3 > E
• S > 2 > E
• S > 4 > E(在我们的用例中与 S14E 相同，但这并不重要 rn。如果我们可以通过算法将其过滤掉，那会很好，但不是必须的。)

一个更复杂的例子

S - - - -
- 1 2 3 -
- 4 5 6 -
- - - - E

具有以下路径:

• S > 1 > 5 > E
• S > 1 > 6 > E
• S > 1 > E
• S > 2 > 6 > E
• S > 2 > E(与S26E相同)*
• S > 3 > E
• S > 4 > E
• S > 5 > E(与 S15E 相同)*
• S > 6 > E

*在我们的用例中

也可以想到把一个高B宽T的矩形分成大小相等的矩形的问题。在我们的用例中，B 和 T 的分离次数应该是可以修改的。示例见图片

Answer 1

在评论中我暗示了动态规划，如果只需要一些解决方案，这是解决这个问题的方法。我误读了问题。

要打印所有解决方案，您必须计算所有解决方案，这是通过递归完成的。递归步骤具有属性 gcd(x, y)=1，因为如果不是这种情况，则步骤将“跳过”某些节点。

这是一个简单的 python 解决方案，它以您指定的格式打印结果。

from fractions import gcd

def valid_steps(max_x, max_y):
    for x in xrange(1, max_x+1):
        for y in xrange(1, max_y+1):
            if gcd(x, y) == 1:
                yield x, y

def _solve(n, m, path, xy_2_name):
    x, y = path[-1]
    if x == n and y == m:
        print [xy_2_name[xy] for xy in path]
        return
    for sx, sy in valid_steps(n - x, m - y):
        _solve(n, m, path + [(x+sx, y+sy)], xy_2_name)

def solve(n, m):
    xy_2_name = dict()
    xy_2_name[(1, 1)] = 'S'
    xy_2_name[(n, m)] = 'E'
    c = 1
    for y in xrange(2, m):
        for x in xrange(2, n):
            xy_2_name[(x, y)] = c
            c += 1
    _solve(n, m, [(1, 1)], xy_2_name)

solve(5, 4)