问题描述
一只老鼠位于迷宫左下角(0,0)，迷宫中的数字9处有块大奶酪。0表示墙，1表示可通过路径。试给出一条可行的吃到奶酪的路径；若没有返回空。
假定迷宫是4连通的，即：老鼠只能上下左右走，不能斜着走。
算法描述
假定当前位于(i,j)处，尝试4个相邻位置，如果相邻位置不是墙，则可以通过。然后递归该过程。
代码如下：
import numpy as np import matplotlib.pyplot as plt # 常量 W = 4 H = 6 CHEESE = 9 # 深度优先搜索（迷宫，开始位置，路线存储变量，访问标志变量） def search(maze, i, j, path, visit): # 找到奶酪，返回ture if maze[i][j] == CHEESE: print(path) return True # 邻居方向向量 # 通过该向量，可以确定下一次从哪一个邻居开始搜索（左->右->下->上 或 上->下->右->左 等等），4个方向 # 向量元素顺序的不同，有可能形成不同的最终路线 i_next = [0, 0, -1, 1] j_next = [-1, 1, 0, 0] # i_next = [1, -1, 0, 0] # j_next = [0, 0, 1, -1] # i_next = [0, 0, -1, 1] # j_next = [1, -1, 0, 0] # 迷宫高度 m = len(maze) # 迷宫宽度 n = len(maze[0]) # 4 连通，只能上下左右步进 for k in range(4): # 从当前位置(i,j)偏移一位 i_cur = i + i_next[k] j_cur = j + j_next[k] # 超出边界则搜索其他方向 if i_cur < 0 or i_cur >= m or j_cur < 0 or j_cur >= n: continue # 新位置没有被访问过并且不是墙 if (not visit[i_cur][j_cur]) and (maze[i_cur][j_cur] != 0): # 把iCur和jCur放置在路径中 path.append((i_cur, j_cur)) # 把iCur和jCur设置为已访问 visit[i_cur][j_cur] = True # 递归搜索 if search(maze, i_cur, j_cur, path, visit): return True # 从(iCur,jCur)找不到可行路径，把iCur和jCur弹出，然后回溯，搜索其他方向 path.pop() visit[i_cur][j_cur] = False # 所有方向均找不到可行路径，返回False return False # 绘制结果 def draw(maze, path): fig = plt.figure() plt.axis("off") ax = fig.add_subplot(111, aspect='equal') ax.set_xlim(0, W * len(maze[0])) ax.set_ylim(0, H * len(maze)) # 迷宫上节点的位置坐标信息，用于绘图 path_pos = dict() y = -H # 绘制迷宫和路线 for r in range(len(maze)): row = maze[r] y += H x = -W for s in range(len(row)): x += W if (r, s) in path: print((r, s)) path_pos[(r, s)] = (x, y) ax.add_patch( plt.Rectangle( (x, y), # 矩形左下角 W, # 长 H, # 宽 color='green', ) ) else: ax.add_patch( plt.Rectangle( (x, y), # 矩形左下角 W, # 长 H, # 宽 edgecolor='black', fill=False, linewidth=1 ) ) # 绘制0,1标记 ax.text(x + W / 2 - 0.5, y + H / 2 - 0.5, "{}".format(row[s]), transform=ax.transData) # 绘制路径方向箭头 if len(path) > 2: for k in range(len(path) - 1): # 箭头开始坐标 start = path_pos[path[k]] # 箭头结束坐标 end = path_pos[path[k + 1]] plt.arrow(start[0] + W / 2 - 0.7, start[1] + W / 2 - 0.7, end[0]-start[0], end[1]-start[1], head_width=1, lw=1, length_includes_head=True) plt.show() # plt.savefig('mouse_path.png', dpi=800) # 主算法 def main(): # 初始化迷宫 maze = [] maze.append([1, 1, 0, 0, 0, 0, 0, 1]) maze.append([1, 1, 1, 1, 1, 1, 1, 1]) maze.append([1, 0, 0, 0, 1, 0, 0, 1]) maze.append([1, 1, 1, 0, 1, 0, 0, 1]) maze.append([0, 1, 0, 0, 1, 1, 1, 1]) maze.append([0, 1, 0, 0, 0, 0, 0, 1]) maze.append([0, 1, 0, 9, 1, 1, 1, 1]) maze.append([0, 1, 1, 1, 0, 0, 1, 0]) maze = np.array(maze) # 初始化路线 path = [(0, 0)] # 初始化访问标记 visit = np.full_like(maze, False) visit[0][0] = True # 开始搜索 search(maze, 0, 0, path, visit) # 绘制结果 draw(maze, path) if __name__ == "__main__": main()
运行结果如下图所示：
算法搜索过程如下：
注意事项
代码中特别要注意的是“邻居方向向量”，通过该向量，可以确定下一次从哪一个邻居开始搜索，是按照左->右->下->上 的顺序还是按 上->下->右->左 或其他顺序对四个方向进行搜索，顺序的不同，有可能形成不同的最终路线，例如若按照 右->左->下->上 的顺序对四个方向进行搜索 ，最终得到的路线如下
本文参考了邹博老师的算法课程
笔者水平有限，若有不对的地方欢迎评论指正
