编程导航算法村第二关 | 白银挑战

**编程导航算法村第二关 | 白银挑战**

在前一关中，我们学习了基本的A*搜索算法。然而，在实际应用中，A*搜索可能会遇到一些问题，如计算成本过高、优先级不明确等。在本关中，我们将学习如何改进A*搜索算法以适应更复杂的场景。

**第二关 | 白银挑战**

在这个关卡中，我们需要实现一个名为"最短路径寻找器"(Shortest Path Finder)的功能。该功能应该能够找到从起点到终点的最短路径，考虑到地图中的障碍和权重。

### 地图结构我们使用一个二维数组来表示地图，其中每个元素代表一个格子。格子的值可以是：

*0：空白格子*1：障碍格子（不可穿越）
*2：起点格子*3：终点格子### 算法实现我们将使用A*搜索算法来寻找最短路径。然而，我们需要对其进行一些改进以适应我们的场景。

####1.启发函数在A*搜索中，启发函数是用来估计从当前位置到目标位置的距离的。我们可以使用曼哈顿距离（Manhattan Distance）作为启发函数：

import mathdef heuristic(node, goal):
 """
 Manhattan distance heuristic function.
 Args:
 node (tuple): Current node coordinates.
 goal (tuple): Goal node coordinates.
 Returns:
 int: Estimated distance from current node to goal node.
 """
 return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

import heapqdef a_star_search(grid, start, goal):
 """
 A* search algorithm implementation.
 Args:
 grid (list):2D grid representing the map.
 start (tuple): Start node coordinates.
 goal (tuple): Goal node coordinates.
 Returns:
 list: Shortest path from start to goal if found, otherwise None.
 """
 # Initialize open and closed sets open_set = []
 closed_set = set()
 # Add start node to open set with priority0 heapq.heappush(open_set, (0, start))
 # Initialize came_from dictionary to store parent nodes came_from = {}
 # Initialize cost_so_far dictionary to store costs cost_so_far = {start:0}
 while open_set:
 # Get node with lowest priority from open set current_cost, current_node = heapq.heappop(open_set)
 # Check if node is in closed set, skip if so if current_node in closed_set:
 continue # Add node to closed set closed_set.add(current_node)
 # Check if node is goal, return path if so if current_node == goal:
 # Reconstruct path by backtracking from goal to start path = []
 while current_node in came_from:
 path.append(current_node)
 current_node = came_from[current_node]
 path.append(start)
 path.reverse()
 return path # Get neighbors of current node neighbors = get_neighbors(grid, current_node)
 # Calculate costs and priorities for each neighbor for neighbor in neighbors:
 new_cost = cost_so_far[current_node] + grid[neighbor[0]][neighbor[1]]
 priority = new_cost + heuristic(neighbor, goal)
 # Check if neighbor is already in open set with lower priority, skip if so if neighbor in cost_so_far and cost_so_far[neighbor] <= new_cost:
 continue # Add neighbor to open set with updated priority and cost heapq.heappush(open_set, (priority, neighbor))
 # Update came_from dictionary with parent node came_from[neighbor] = current_node # Update cost_so_far dictionary with new cost cost_so_far[neighbor] = new_cost # Return None if no path found return Nonedef get_neighbors(grid, node):
 """
 Get neighbors of a given node.
 Args:
 grid (list):2D grid representing the map.
 node (tuple): Node coordinates.
 Returns:
 list: List of neighboring nodes.
 """
 neighbors = []
 directions = [(0,1), (0, -1), (1,0), (-1,0)]
 for direction in directions:
 x, y = node[0] + direction[0], node[1] + direction[1]
 if0 <= x < len(grid) and0 <= y < len(grid[0]) and grid[x][y] !=1:
 neighbors.append((x, y))
 return neighbors

grid = [
 [0,0,1,0],
 [0,0,1,0],
 [0,0,2,3]
]

start_node = (0,0)
goal_node = (2,3)

path = a_star_search(grid, start_node, goal_node)

if path:
 print("Shortest path found:", path)
else:
 print("No path found")