在网格中寻找路径

Question

我试图打印 mxm 矩阵中的所有路径，如果我访问已经访问过的节点，这些路径就会终止。我尝试过递归解决方案，但我不确定如何处理基本情况

def is_valid_move(x, y): 返回 0 <= x < m and 0 <= y < m def find_paths(G, x, y, visited, path): visited.add((x, y)) path.append((x, y))

    if len(visited) == m:
        return [path]# Print the path when all nodes are visited
    else:
        paths = []
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if is_valid_move(nx, ny) and (nx, ny) not in visited:
                new_paths = find_paths(G, nx, ny, set(visited), list(path))
                paths.append(new_paths)

            if is_valid_move(nx, ny) and (nx, ny) in visited:
                completed_path = [vertex for vertex in path]
                paths.append(completed_path.append((nx, ny)))
        return paths

G = [['ghargh', 'drwtex', 'qdgeun'], ['xmhjkl', 'kmswji', 'cvjosd'], ['vbrmwq', 'fgdhey', 'eyuite']] 结果路径 = find_paths(G, 0, 0, set(), []) 这段代码将给出长度为 m 的路径。但我也想要更早终止的路径。 例如，如果我从 (0,0) 开始，则以下路径也应该出现在所有可能的路径 (0,0)->(0,1)->(0,2)->(1,2)- 中>(2,2)->(2,1)->(1,1)->(0,0)

Answer 1

你的问题就在这里：

if is_valid_move(nx, ny) and (nx, ny) in visited:
    completed_path = [vertex for vertex in path]
    paths.append(completed_path.append((nx, ny)))

首先，无需多言

[vertex for vertex in path]

；这只是创建

path

的副本，因此请使用

path

。其次，由于

(nx, ny)

已经被访问过，所以你不应该将其附加到

completed_path

（否则它就不是路径）。最后，您应该知道

foo.append(bar)

在 Python 中返回

None

。因此，在上面代码块的最后一行中，您将

None

附加到

paths

（然后在 if 语句之后返回

paths

）。上面的代码块应更改如下：

if is_valid_move(nx, ny) and (nx, ny) in visited:
    paths.append(path)