Ex No 4 Implementation of Informed Search Algorithms (AO*)
CLICK HERE PROGRAM
Aim
To implement the informed search algorithm and execute the code for AO* search algorithm.
Algorithm
1.Define the problem determine the problem you want to solve including the start and goal nodes.
2.Add the start node to the open list and set its G score.
3.Calculate the F score for each node on the open list by adding the G score and a heuristic estimate of the
distance to the goal node. The heuristic estimate can be calculated using a variety of method.
4.Choose the node with the lowest F score from the open list and move it to the closed list.
5.Generate the successors of the node selected in step4.
6.If the goal node is on the closed list, the search is complete. Otherwise, repeat steps 4,5 until the goal
node is found.
7.Set a bound for the minimum acceptable F score for the goal node, this allows the algorithm to terminate
early if it is a solution that is close enough to optimal.
8.If the algorithm terminate early, backtrack to the node with the lowest F score that was removed from the
open list and generate its successors.
9.When backtracking nodes that were previously removed from the open list may need to be reinserted if
their now F score is lower than the bound.
PROGRAM:
import heapq
class Node:
def __init__(self, state, node_type, heuristic, parent=None):
self.state = state # The state of the node (e.g., 'A', 'B', etc.)
self.node_type = node_type # 'AND' or 'OR'
self.heuristic = heuristic # Heuristic value to the goal
self.parent = parent # Parent node that led to this state
# Track if the node has been solved
self.solved = False
def __lt__(self, other):
# This is for comparing nodes in the priority queue based on heuristic
return self.heuristic < other.heuristic
class AOStar:
def __init__(self, start_state, goal_state, heuristic_function):
self.start_state = start_state
self.goal_state = goal_state
self.heuristic_function = heuristic_function
self.open_list = [] # Priority queue of nodes to explore
self.closed_list = set() # Explored nodes
def search(self):
# Initialize the starting node as an OR node
start_node = Node(self.start_state, 'OR', self.heuristic_function(self.start_state))
heapq.heappush(self.open_list, start_node)
while self.open_list:
current_node = heapq.heappop(self.open_list)
# If we reached the goal state, reconstruct the path
if current_node.state == self.goal_state:
return self.reconstruct_path(current_node)
# Skip the node if it's already explored
if current_node.state in self.closed_list:
continue
self.closed_list.add(current_node.state)
# Expand the node depending on its type
if current_node.node_type == 'OR':
children = self.expand_or_node(current_node)
for child in children:
heapq.heappush(self.open_list, child)
elif current_node.node_type == 'AND':
children = self.expand_and_node(current_node)
for child in children:
heapq.heappush(self.open_list, child)
return None
def expand_or_node(self, node):
# Generate possible children for an OR node
children = []
possible_children = self.get_possible_children(node.state)
for child_state in possible_children:
child = Node(child_state, 'AND', self.heuristic_function(child_state), node)
children.append(child)
return children
def expand_and_node(self, node):
# Generate possible children for an AND node
children = []
possible_children = self.get_possible_children(node.state)
for child_state in possible_children:
child = Node(child_state, 'OR', self.heuristic_function(child_state), node)
children.append(child)
return children
def get_possible_children(self, state):
# Define a small tree structure for the problem
if state == 'A':
return ['B', 'C', 'D']
elif state == 'B':
return ['E', 'F']
elif state == 'C':
return ['G', 'H']
elif state == 'D':
return ['I', 'J']
elif state == 'E':
return ['K']
elif state == 'F':
return ['L']
elif state == 'G':
return ['Z']
elif state == 'H':
return ['Z']
# Return empty list if no children
return []
def heuristic(self, state):
# Heuristic: distance to goal (Z)
return abs(ord(state) - ord(self.goal_state))
def reconstruct_path(self, node):
# Reconstruct path from start to goal
path = []
while node:
path.append(node.state)
node = node.parent
return path[::-1] # Reverse to get path from start to goal
# Example heuristic function
def simple_heuristic(state):
# Heuristic based on distance from the goal state ('Z')
return abs(ord(state) - ord('Z'))
# Define the start and goal states
start_state = 'A'
goal_state = 'Z'
# Initialize the AO* search algorithm
ao_star = AOStar(start_state, goal_state, simple_heuristic)
# Run the search
path = ao_star.search()
if path:
print("Path from start to goal:", path)
else:
print("No path found.")
No comments:
Post a Comment