**Photo by Christina Morillo**

The A* (A-star) search algorithm in python is an informed search algorithm often used in path finding and graph traversal. It optimizes the search by using a heuristic function to estimate the cost to reach the goal from a given node, combining this with the actual cost from the start node to the current node.

Here’s a simple implementation of the A* algorithm in Python:

```
import heapq
# Define the A* algorithm
def a_star(graph, start, goal):
# Priority queue to store the open nodes
open_list = []
heapq.heappush(open_list, (0, start)) # (priority, node)
# To store the costs and paths
g_costs = {start: 0}
f_costs = {start: heuristic(start, goal)}
came_from = {start: None}
while open_list:
# Get the node with the lowest f_cost
current_f_cost, current_node = heapq.heappop(open_list)
# If we have reached the goal, reconstruct the path
if current_node == goal:
return reconstruct_path(came_from, current_node)
# Explore neighbors
for neighbor, cost in graph[current_node]:
tentative_g_cost = g_costs[current_node] + cost
# If the new path to neighbor is better, update costs and path
if neighbor not in g_costs or tentative_g_cost < g_costs[neighbor]:
g_costs[neighbor] = tentative_g_cost
f_costs[neighbor] = tentative_g_cost + heuristic(neighbor, goal)
came_from[neighbor] = current_node
heapq.heappush(open_list, (f_costs[neighbor], neighbor))
# If the goal was never reached, return failure
return None
# Simple heuristic function (Manhattan distance)
def heuristic(node, goal):
(x1, y1) = node
(x2, y2) = goal
return abs(x1 - x2) + abs(y1 - y2)
# Reconstruct the path from start to goal
def reconstruct_path(came_from, current_node):
path = []
while current_node is not None:
path.append(current_node)
current_node = came_from[current_node]
path.reverse()
return path
# Example graph as a dictionary of nodes with their neighbors and the cost to them
graph = {
(0, 0): [((0, 1), 1), ((1, 0), 1)],
(0, 1): [((0, 0), 1), ((1, 1), 1), ((0, 2), 1)],
(0, 2): [((0, 1), 1), ((1, 2), 1)],
(1, 0): [((0, 0), 1), ((1, 1), 1), ((2, 0), 1)],
(1, 1): [((0, 1), 1), ((1, 0), 1), ((1, 2), 1), ((2, 1), 1)],
(1, 2): [((0, 2), 1), ((1, 1), 1), ((2, 2), 1)],
(2, 0): [((1, 0), 1), ((2, 1), 1)],
(2, 1): [((2, 0), 1), ((1, 1), 1), ((2, 2), 1)],
(2, 2): [((2, 1), 1), ((1, 2), 1)],
}
# Running the A* algorithm
start_node = (0, 0)
goal_node = (2, 2)
path = a_star(graph, start_node, goal_node)
```

# Output the result

`print("Path from start to goal:", path)`

**How It Works:**

**Graph Representation**: The graph is represented as a dictionary where each node has a list of tuples representing its neighbors and the cost to reach them.**Priority Queue**: A priority queue (min-heap) is used to manage the nodes to be explored, prioritized by their f_cost (which is the sum of g_cost and heuristic).**Cost Calculation**:- g_cost is the cost from the start node to the current node.
- heuristic is an estimate of the cost from the current node to the goal (here using Manhattan distance).
- f_cost is the sum of g_cost and the heuristic.

**Path Reconstruction**: Once the goal is reached, the algorithm reconstructs the path by backtracking from the goal node to the start node using the came_from dictionary.

**Example Output:**

Path from start to goal: [(0, 0), (1, 0), (1, 1), (1, 2), (2, 2)]

This code assumes a simple 2D grid where movement costs are uniform. You can adapt it to more complex graphs and heuristic functions depending on your specific needs.

## Leave a Reply