let's take a look at an example implementation of the A* search algorithm in Python:
python
import heapq
def a_star(start, goal, h_func, graph):
"""
Finds the shortest path between start and goal nodes in a graph using the A* search algorithm.
Parameters:
start: The starting node.
goal: The goal node.
h_func: A heuristic function that estimates the distance from a node to the goal.
graph: A dictionary representing the graph, where the keys are the nodes and the values are lists of (neighbor, cost) tuples.
Returns:
A tuple (path, cost) representing the shortest path from start to goal and its cost.
"""
frontier = [(0, start)]
explored = set()
g_scores = {start: 0}
f_scores = {start: h_func(start, goal)}
came_from = {}
while frontier:
_, current = heapq.heappop(frontier)
if current == goal:
return construct_path(came_from, start, goal), g_scores[goal]
explored.add(current)
for neighbor, cost in graph[current]:
if neighbor in explored:
continue
tentative_g_score = g_scores[current] + cost
if neighbor not in g_scores or tentative_g_score < g_scores[neighbor]:
came_from[neighbor] = current
g_scores[neighbor] = tentative_g_score
f_scores[neighbor] = tentative_g_score + h_func(neighbor, goal)
heapq.heappush(frontier, (f_scores[neighbor], neighbor))
return None, float('inf')
def construct_path(came_from, start, goal):
"""
Constructs the shortest path from start to goal using the came_from dictionary.
Parameters:
came_from: A dictionary where the keys are the nodes and the values are the nodes' parents.
start: The starting node.
goal: The goal node.
Returns:
A list representing the shortest path from start to goal.
"""
path = [goal]
while path[-1] != start:
path.append(came_from[path[-1]])
return list(reversed(path))
In this implementation, we start by initializing a priority queue frontier with the starting node and its estimated cost f_score (which is the sum of the actual cost g_score from the start node to the current node and the heuristic cost h from the current node to the goal node). We also initialize an empty set explored to keep track of the nodes that we have already visited, and dictionaries g_scores and f_scores to keep track of the actual and estimated costs for each node. Finally, we initialize an empty dictionary came_from to keep track of the parent node for each node in the path.
We then enter a loop where we pop the node with the lowest estimated cost f_score from the frontier priority queue. If this node is the goal node, we construct the shortest path using the came_from dictionary and return it along with the actual cost g_score of the path. Otherwise, we add the current node to the explored set, and iterate over its neighbors. For each neighbor, we calculate a tentative actual cost tentative_g_score by adding the cost of the edge from the current node to the neighbor to the actual cost of the current node. If the neighbor has not yet been visited or the tentative cost is lower than the current cost, we update its g_score, f_score, and came_from values, and add
No comments:
Post a Comment