#To Implement A* algorithm.
import heapq
class Node:
def __init__(self, name, x, y):
[Link] = name
self.x = x
self.y = y
self.g = float('inf')
self.h = float('inf')
self.f = float('inf')
[Link] = None
def __lt__(self, other):
return self.f < other.f
def heuristic(a, b):
return abs(a.x - b.x) + abs(a.y - b.y)
def a_star(start, goal, neighbors):
open_list = []
closed_list = set()
start.g = 0
start.h = heuristic(start, goal)
start.f = start.h
[Link](open_list, start)
while open_list:
current = [Link](open_list)
if current == goal:
path = []
while current:
[Link]([Link])
current = [Link]
return path[::-1]
closed_list.add(current)
for neighbor in neighbors[current]:
if neighbor in closed_list:
continue
tentative_g = current.g + 1 # Assuming uniform cost
if tentative_g < neighbor.g:
neighbor.g = tentative_g
neighbor.h = heuristic(neighbor, goal)
neighbor.f = neighbor.g + neighbor.h
[Link] = current
if neighbor not in open_list:
[Link](open_list, neighbor)
return None
# Example usage:
nodes = {name: Node(name, x, y) for name, x, y in [('A', 0, 0), ('B', 1, 0), ('C', 1, 1), ('D', 2, 1), ('E', 2,
2)]}
neighbors = {
nodes['A']: [nodes['B']],
nodes['B']: [nodes['A'], nodes['C']],
nodes['C']: [nodes['B'], nodes['D']],
nodes['D']: [nodes['C'], nodes['E']],
nodes['E']: [nodes['D']],
start_node = nodes['A']
goal_node = nodes['E']
path = a_star(start_node, goal_node, neighbors)
print("Path found:", path)
Output:
Path found: ['A', 'B', 'C', 'D', 'E']
A* Algorithm
A* (A-star) is a graph traversal and path search algorithm that finds the shortest path from a
start node to a goal node while using heuristics to guide its search. It combines Dijkstra’s
Algorithm and Greedy Best-First Search.
The algorithm uses a priority queue to explore the most promising nodes first. It maintains
two lists:
Open List: Nodes to be evaluated.
Closed List: Nodes already evaluated.
Each node has:
G cost: The cost to get from the start node to this node.
H cost: The estimated cost to get from this node to the goal node (heuristic).
F cost: The sum of G and H costs (F = G + H).
A Algorithm*:
Uses an open list to store nodes to be evaluated.
Does not have a strict memory limit.
Memory Bounded A (MBA) Algorithm**:
Limits the size of the open list.
Uses a mechanism (like a deque) to manage nodes that are removed from the open list
but may need to be revisited.
example of the A* algorithm in Python. This example will use a grid-based representation of
the environment, which is a common scenario for pathfinding problems. In this example,
we'll create a grid where some cells are walkable and some are obstacles.
Problem Setup
Grid: A 2D grid where each cell can be walkable or blocked.
Start and Goal: Specify start and goal positions on the grid.
Neighbors: The neighbors of each cell are the cells directly adjacent (up, down, left,
right).
Explanation:
1. Node Class: Represents each cell in the grid. It includes properties for the cost
calculations and parent tracking.
o __init__: Initializes node with position and walkability.
o __lt__: Allows comparison of nodes based on f cost for priority queue
operations.
2. Heuristic Function: Uses Manhattan distance to estimate the cost from the current
node to the goal.
3. Get Neighbors: Returns walkable neighbors of the current node (up, down, left,
right).
4. A Algorithm*:
o Initializes the start node.
o Uses a priority queue to explore nodes based on the lowest f cost.
o Updates node costs and paths as it explores.
o Returns the path from the start to the goal if found.
In this example, the grid is represented as a list of lists of Node objects, and obstacles are
defined as blocked cells. The A* algorithm is used to find the shortest path from the start
node to the goal node, avoiding obstacles.
#sample program for A* Algorithm
import heapq
class Node:
def __init__(self, x, y, walkable=True):
self.x = x
self.y = y
[Link] = walkable
self.g = float('inf') # Cost from start to this node
self.h = float('inf') # Heuristic cost to goal
self.f = float('inf') # Total cost
[Link] = None
def __lt__(self, other):
return self.f < other.f
def heuristic(a, b):
return abs(a.x - b.x) + abs(a.y - b.y) # Manhattan distance
def get_neighbors(node, grid):
neighbors = []
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # Up, Down, Left, Right
for direction in directions:
nx, ny = node.x + direction[0], node.y + direction[1]
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]):
if grid[nx][ny].walkable:
[Link](grid[nx][ny])
return neighbors
def a_star(start, goal, grid):
open_list = []
closed_list = set()
start.g = 0
start.h = heuristic(start, goal)
start.f = start.h
[Link](open_list, start)
while open_list:
current = [Link](open_list)
if (current.x, current.y) == (goal.x, goal.y):
path = []
while current:
[Link]((current.x, current.y))
current = [Link]
return path[::-1] # Return reversed path
closed_list.add((current.x, current.y))
for neighbor in get_neighbors(current, grid):
if (neighbor.x, neighbor.y) in closed_list:
continue
tentative_g = current.g + 1 # Assuming uniform cost (1 for each step)
if tentative_g < neighbor.g:
neighbor.g = tentative_g
neighbor.h = heuristic(neighbor, goal)
neighbor.f = neighbor.g + neighbor.h
[Link] = current
if neighbor not in open_list:
[Link](open_list, neighbor)
return None
# Example usage:
# Create a 5x5 grid
grid = [[Node(x, y) for y in range(5)] for x in range(5)]
# Define some obstacles
obstacles = [(1, 1), (1, 2), (1, 3), (2, 1), (3, 1)]
for (x, y) in obstacles:
grid[x][y].walkable = False
# Define start and goal nodes
start_node = grid[0][0]
goal_node = grid[4][4]
# Find the path
path = a_star(start_node, goal_node, grid)
if path:
print("Path found:", path)
else:
print("No path found")
Output:
Path found: [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (4, 1), (4, 2),
(4, 3), (4, 4)]