Notes

import heapq

class Node:
def __init__(self, state, parent=None, cost=0, heuristic=0):
self.state = state
self.parent = parent
self.cost = cost
self.heuristic = heuristic

def __lt__(self, other):
return (self.cost + self.heuristic) < (other.cost + other.heuristic)

def greedy_best_first_search(initial_state, goal_state, get_neighbors, heuristic):
start_node = Node(state=initial_state)
goal_node = Node(state=goal_state)
frontier = [start_node]
explored = set()

while frontier:
current_node = heapq.heappop(frontier)
if current_node.state == goal_state:
return reconstruct_path(current_node)

explored.add(current_node.state)

for neighbor_state in get_neighbors(current_node.state):
if neighbor_state not in explored:
neighbor_node = Node(state=neighbor_state, parent=current_node)
heapq.heappush(frontier, neighbor_node)

return None

def a_star_search(initial_state, goal_state, get_neighbors, heuristic):
start_node = Node(state=initial_state, heuristic=heuristic(initial_state, goal_state))
goal_node = Node(state=goal_state)
frontier = [start_node]
explored = set()

while frontier:
current_node = heapq.heappop(frontier)
if current_node.state == goal_state:
return reconstruct_path(current_node)

explored.add(current_node.state)

for neighbor_state in get_neighbors(current_node.state):
if neighbor_state not in explored:
neighbor_cost = current_node.cost + 1
neighbor_heuristic = heuristic(neighbor_state, goal_state)
neighbor_node = Node(state=neighbor_state, parent=current_node, cost=neighbor_cost, heuristic=neighbor_heuristic)
heapq.heappush(frontier, neighbor_node)

return None

def reconstruct_path(node):
path = []
while node:
path.append(node.state)
node = node.parent
return list(reversed(path))

def get_neighbors(state):
x, y = state
neighbors = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
return [(nx, ny) for nx, ny in neighbors if 0 <= nx < 5 and 0 <= ny < 5]

def heuristic(state, goal_state):
return abs(state[0] - goal_state[0]) + abs(state[1] - goal_state[1])

initial_state = (0, 0)
goal_state = (4, 2)

gbfs_path = greedy_best_first_search(initial_state, goal_state, get_neighbors, heuristic)
print("Greedy Best-First Search Path:", gbfs_path)

a_star_path = a_star_search(initial_state, goal_state, get_neighbors, heuristic)
print("A* Search Path:", a_star_path)