python老鼠找迷宫

A*搜索算法实现import heapq # 定义迷宫的结构其中1表示墙0表示通道 maze [ [1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1, 0, 1], [1, 0, 1, 0, 0, 1, 0, 1], [1, 0, 1, 1, 0, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1] ] # 定义起点和终点 start (1, 1) end (len(maze) - 2, len(maze[0]) - 2) # 定义一个函数来计算启发式估值函数曼哈顿距离 def heuristic(node): return abs(node[0] - end[0]) abs(node[1] - end[1]) # 定义一个函数来执行A*搜索 def astar_search(maze, start, end): open_list [] closed_set set() came_from {} # 开始节点(f值, g值, 坐标) start_node (heuristic(start), 0, start) heapq.heappush(open_list, start_node) while open_list: f, g, current heapq.heappop(open_list) if current end: # 找到路径 path reconstruct_path(came_from, current) return path closed_set.add(current) for neighbor in [(current[0] - 1, current[1]), (current[0] 1, current[1]), (current[0], current[1] - 1), (current[0], current[1] 1)]: if (0 neighbor[0] len(maze) and 0 neighbor[1] len(maze[0]) and maze[neighbor[0]][neighbor[1]] 0 and neighbor not in closed_set): g_value g 1 h_value heuristic(neighbor) f_value g_value h_value if neighbor not in [node[2] for node in open_list]: heapq.heappush(open_list, (f_value, g_value, neighbor)) came_from[neighbor] current # 找不到路径 return None # 定义一个函数来重构路径 def reconstruct_path(came_from, current): path [current] while current in came_from: current came_from[current] path.append(current) return list(reversed(path)) # 执行A*搜索 path astar_search(maze, start, end) if path: print(找到路径:) for p in path: print(p) else: print(找不到路径)深度优先算法# 定义迷宫的结构其中1表示墙0表示通道 maze [ [1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1, 0, 1], [1, 0, 1, 0, 0, 1, 0, 1], [1, 0, 1, 1, 0, 1, 1, 1], [1, 0, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1] ] # 定义一个函数来执行深度优先搜索 def dfs(maze, start, end, max_depth, path): if start end: path.append(start) return True if max_depth 0: return False x, y start # 尝试向四个方向移动 for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]: new_x, new_y x dx, y dy if (0 new_x len(maze) and 0 new_y len(maze[0]) and maze[new_x][new_y] 0): path.append((new_x, new_y)) if dfs(maze, (new_x, new_y), end, max_depth - 1, path): return True path.pop() return False # 定义一个函数来执行深度逐渐增加的搜索 def iddfs(maze, start, end): max_depth 0 path [] while not dfs(maze, start, end, max_depth, path): max_depth 1 path [] return path # 执行IDDFS搜索 start (1, 1) end (len(maze) - 2, len(maze[0]) - 2) path iddfs(maze, start, end) if path: print(找到路径:) for p in path: print(p) else: print(找不到路径)