python迷宫问题深度优先遍历实例

1. Python迷宫问题深度优先遍历实例

深度优先遍历（Depth First Search，DFS）是经典的图论遍历算法，用于遍历或搜索树或图的数据结构。在本文中，我们将使用Python语言编写一个迷宫问题求解程序，使用深度优先遍历算法寻找从迷宫起点到终点的所有可能路径。

2. 迷宫问题

迷宫问题是经典的搜索问题，通过从起点到终点的路径，找到解决问题的方法。在本例中，我们使用一个4 x 5的迷宫，其中0表示表示可以移动的位置，1表示阻碍物，S表示起点，E表示终点。如下所示：

maze = [

    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
]

2.1 迷宫问题解决方案

对于这个迷宫问题，我们可以使用深度优先遍历算法。在深度优先遍历中，我们沿着一条路径一直走到终点或者不能再走为止。当我们返回时，我们回溯到上一个节点查找其他可能的路径。我们用一个二维数组visited记录已经被访问的节点。

def dfs(x, y, path, visited):

    if x == end_x and y == end_y:
        paths.append(path)
        return
    
    for i in range(4):
        x_new = x + dx[i]
        y_new = y + dy[i]
        if 0 <= x_new < n and 0 <= y_new < m and not visited[x_new][y_new] and maze[x_new][y_new] == 0:
            visited[x_new][y_new] = True
            dfs(x_new, y_new, path + moves[i], visited)
            visited[x_new][y_new] = False

2.2 迷宫问题代码解释

代码中，我们定义了一个函数dfs(x, y, path, visited)，其中x和y表示当前节点的位置，path表示从起点到当前节点需要经过的路径，visited表示已经访问过的节点。

在dfs函数中，我们首先进行终止条件的判断。如果当前节点是终点，我们就将path添加到paths数组中。然后返回。

if x == end_x and y == end_y:

    paths.append(path)
    return

否则，我们进行四个方向尝试：向上、向下、向左、向右。我们定义dx和dy数组，记录四个方向的坐标变化。如果变化后的坐标不越界、没被访问过并且是0（不是阻碍物），我们就可以继续往下进行深度优先遍历。在遍历之前，我们将当前节点标记为已经访问，遍历完之后再重置为未访问。

for i in range(4):

    x_new = x + dx[i]
    y_new = y + dy[i]
    if 0 <= x_new < n and 0 <= y_new < m and not visited[x_new][y_new] and maze[x_new][y_new] == 0:
        visited[x_new][y_new] = True
        dfs(x_new, y_new, path + moves[i], visited)
        visited[x_new][y_new] = False

在程序中，我们使用了两个全局变量：paths和moves。paths保存已经找到的路径，moves保存从起点到当前节点的移动方向。在程序的开始和结束处初始化和清空。

paths = []

moves = ['U', 'D', 'L', 'R']

3. 完整代码

以下是完整代码实现。

maze = [

    [0, 1, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
]
start_x, start_y, end_x, end_y = 0, 0, 4, 3
n, m = len(maze), len(maze[0])
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
paths = []
moves = ['U', 'D', 'L', 'R']
def dfs(x, y, path, visited):
    if x == end_x and y == end_y:
        paths.append(path)
        return
    
    for i in range(4):
        x_new = x + dx[i]
        y_new = y + dy[i]
        if 0 <= x_new < n and 0 <= y_new < m and not visited[x_new][y_new] and maze[x_new][y_new] == 0:
            visited[x_new][y_new] = True
            dfs(x_new, y_new, path + moves[i], visited)
            visited[x_new][y_new] = False
visited = [[False] * m for _ in range(n)]
visited[start_x][start_y] = True
dfs(start_x, start_y, '', visited)
print(paths)

4. 总结

本文介绍了如何使用深度优先遍历算法解决迷宫问题。代码实现简单明了，易于理解，适合初学者参考学习。