### Python 实现带有限制条件的路径查找算法 为了满足特定起点位置选择不同方向路径的需求，可以基于深度优先搜索(DFS)[^1] 或者更高效的A*算法[^3] 进行改进。下面展示了一个使用A*算法并加入限制条件的例子。 #### 代码实现 ```python import heapq def heuristic(a, b): (x1, y1) = a (x2, y2) = b return abs(x1 - x2) + abs(y1 - y2) def astar(maze, start_points, end_point, direction='up'): """ :param maze: 二维列表表示的地图，0为空位，1为障碍物 :param start_points: 起点坐标的元组列表[(x,y),...], 可能有多个起点 :param end_point: 终点坐标元组(x,y) :param direction: 'up' or 'down', 控制初始探索的方向偏好 :return: 返回最短路径列表或 None 如果不存在路径 """ width = len(maze[0]) height = len(maze) open_set = [] came_from = {} g_score = {point: float('inf') for point in start_points} f_score = {point: float('inf') for point in start_points} for sp in start_points: g_score[sp] = 0 f_score[sp] = heuristic(sp, end_point) heapq.heappush(open_set, (f_score[sp], sp)) while open_set: _, current = heapq.heappop(open_set) if current == end_point: path = [] while current in came_from: path.append(current) current = came_from[current] path.reverse() return path neighbors = get_neighbors(maze, current, direction=direction) tentative_g_score = g_score[current] + 1 for neighbor in neighbors: if tentative_g_score < g_score.get(neighbor, float('inf')): came_from[neighbor] = current g_score[neighbor] = tentative_g_score fscore_neighbor = tentative_g_score + heuristic(neighbor, end_point) if not any(n[-1]==neighbor for n in open_set): heapq.heappush(open_set, (fscore_neighbor, neighbor)) f_score[neighbor] = fscore_neighbor return None def get_neighbors(maze, position, direction='up'): """获取邻居节点""" directions = [(0,-1),(0,1),(-1,0),(1,0)] # up down left right if direction=='up': preferred_directions = [(-1,0),(0,-1),(0,1)] elif direction=='down': preferred_directions = [(1,0),(0,-1),(0,1)] result = [] for d in preferred_directions: new_pos = tuple(map(sum, zip(position,d))) if is_valid_position(maze,new_pos): result.append(new_pos) return result def is_valid_position(maze, pos): """验证新位置是否有效""" x, y = pos if x<0 or y<0 or x>=len(maze) or y>=len(maze[0]): return False if maze[x][y]: return False return True ``` 此代码片段定义了`astar()` 函数来执行带有偏好的A*搜索过程，其中考虑到了从上方还是下方开始的影响。通过调整 `get_neighbors()` 中的方向顺序，使得某些情况下会优先尝试向上或向下扩展。当存在多于一个起点时，所有这些起点都将被初始化入队列中参与计算最优解的过程。