Program 3: Implement A* Search algorithm
def aStarAlgo(start_node, stop_node):
open_set = {start_node} # Use a set for open nodes
closed_set = set() # Set to keep track of visited nodes
g = {} # Store distances from the start node
parents = {} # Store parent nodes for path reconstruction
# Distance of the starting node from itself is 0
g[start_node] = 0
# The start_node is the root node, so it has no parent
parents[start_node] = start_node
while len(open_set) > 0:
n = None
# Find the node with the lowest f() value
for v in open_set:
if n is None or g[v] + heuristic(v) < g[n] + heuristic(n):
n=v
if n is None:
print('Path does not exist!')
return None
# If the goal node is reached, reconstruct the path
if n == stop_node:
path = []
while parents[n] != n:
[Link](n)
n = parents[n]
[Link](start_node)
[Link]()
print('Path found: {}'.format(path))
return path
# Move the current node from open_set to closed_set
open_set.remove(n)
closed_set.add(n)
if n not in Graph_nodes or Graph_nodes[n] is None:
continue # Skip if there are no neighbors
for (m, weight) in get_neighbors(n):
if m not in open_set and m not in closed_set:
open_set.add(m)
parents[m] = n
g[m] = g[n] + weight
else:
if g[m] > g[n] + weight:
g[m] = g[n] + weight
parents[m] = n
if m in closed_set:
closed_set.remove(m)
open_set.add(m)
print('Path does not exist!')
return None
# Function to return neighbors and their distances
def get_neighbors(v):
return Graph_nodes.get(v, None)
# Heuristic function (predefined heuristic values for each node)
def heuristic(n):
H_dist = {
'A': 11, 'B': 6, 'C': 99, 'D': 1, 'E': 7, 'G': 0
}
return H_dist.get(n, float('inf')) # Return inf if heuristic is not defined
# Graph representation
Graph_nodes = {
'A': [('B', 2), ('E', 3)],
'B': [('C', 1), ('G', 9)],
'C': None,
'E': [('D', 6)],
'D': [('G', 1)]
}
# Run A* Algorithm
aStarAlgo('A', 'G')
--------------------------OUTPUT--------------------------
Path found: ['A', 'E', 'D', 'G']
aStarAlgo('B', 'D')
output: Path found: ['B', 'C', 'D']
Program 4 Implement AO* Search algorithm
import heapq
class Node:
def __init__(self, state, parent=None, action=None, cost=0, heuristic=0):
[Link] = state # Current state in the search space
[Link] = parent # Parent node
[Link] = action # Action that led to this node from the parent node
[Link] = cost # Cost to reach this node from the start node
[Link] = heuristic # Heuristic estimate of the cost to reach the goal
def __lt__(self, other):
return ([Link] + [Link]) < ([Link] + [Link])
def parse_graph_input():
graph = {}
num_edges = int(input("Enter the number of edges: "))
for _ in range(num_edges):
u, v, cost = input("Enter an edge (format: u v cost): ").split()
cost = float(cost)
if u not in graph:
graph[u] = []
if v not in graph:
graph[v] = []
graph[u].append((v, cost))
return graph
def ao_star_search(start_state, goal_state, graph):
frontier = []
[Link](frontier, Node(start_state, None, None, 0, heuristic(start_state,
goal_state)))
explored = {}
while frontier:
current_node = [Link](frontier)
current_state = current_node.state
if current_state == goal_state:
# Reconstruct the path from the goal node to the start node
path = []
while current_node.parent is not None:
[Link]((current_node.action, current_node.state))
current_node = current_node.parent
[Link]()
return path
if current_state not in explored or current_node.cost < explored[current_state]:
explored[current_state] = current_node.cost
for neighbor, step_cost in [Link](current_state, []):
new_cost = current_node.cost + step_cost
new_node = Node(neighbor, current_node, f"Move to {neighbor}", new_cost,
heuristic(neighbor, goal_state))
[Link](frontier, new_node)
return None # No path found
def heuristic(state, goal_state):
# Simple heuristic function (e.g., straight-line distance)
heuristic_values = {'A': 5, 'B': 3, 'C': 2, 'D': 1, 'E': 2, 'G': 0} # Custom heuristic values
based on problem domain
return heuristic_values.get(state, float('inf')) # Default to infinity if state not found
if __name__ == "__main__":
# Get user input to define the graph
print("Define the graph:")
graph = parse_graph_input()
start_state = input("Enter the start state: ")
goal_state = input("Enter the goal state: ")
# Perform AO* search using the defined graph, start state, and goal state
path = ao_star_search(start_state, goal_state, graph)
# Print the resulting path found by AO* search
if path:
print("Path found:")
for action, state in path:
print(f"Action: {action}, State: {state}")
else:
print("No path found.")
"""
$ p3 04AOstar_search.py
Define the graph:
Enter the number of edges: 8
Enter an edge (format: u v cost): S A 3
Enter an edge (format: u v cost): S B 2
Enter an edge (format: u v cost): A C 4
Enter an edge (format: u v cost): A D 2
Enter an edge (format: u v cost): B E 3
Enter an edge (format: u v cost): C G 2
Enter an edge (format: u v cost): D G 5
Enter an edge (format: u v cost): E G 4
Enter the start state: S
Enter the goal state: G
Path found:
Action: Move to B, State: B
Action: Move to E, State: E
Action: Move to G, State: G
Program 5: Solve 8-Queens Problem with suitable assumptions
N = 8 # Size of the chessboard
board = [[0] * N for _ in range(N)] # Initialize board with 0s
# Function to print the board
def print_solution(board):
for row in board:
print(" ".join('Q' if x else '.' for x in row))
print("\n")
# Function to check if it's safe to place a queen at board[row][col]
def is_safe(board, row, col):
# Check left side of current row
for i in range(col):
if board[row][i] == 1:
return False
# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i][j] == 1:
return False
# Check lower diagonal on left side
for i, j in zip(range(row, N, 1), range(col, -1, -1)):
if board[i][j] == 1:
return False
return True # It's safe to place a queen
# Function to solve the N-Queens problem using backtracking
def solve_nq_util(board, col):
if col >= N: # Base condition: all queens placed
return True
for i in range(N):
if is_safe(board, i, col):
board[i][col] = 1 # Place queen
if solve_nq_util(board, col + 1): # Recursive step
return True # Solution found
board[i][col] = 0 # Backtrack if needed
return False # No solution found for this configuration
# Function to initiate the solving process
def solve_nq():
if not solve_nq_util(board, 0):
print("Solution does not exist")
return False
print_solution(board) # Print the solution
return True
# Run the solver
solve_nq()