ASTAR:
from queue import PriorityQueue
def a_star_algorithm(start, goal, graph, heuristics):
open_list = PriorityQueue()
open_list.put((0, start))
came_from = {}
g_score = {node: float('inf') for node in graph}
g_score[start] = 0
while not open_list.empty():
_, current = open_list.get()
if current == goal:
path = []
while current in came_from:
path.insert(0, current)
current = came_from[current]
path.insert(0, start)
return path
for neighbor, cost in graph[current].items():
tentative_g_score = g_score[current] + cost
if tentative_g_score < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g_score
f_score = tentative_g_score + heuristics[neighbor]
open_list.put((f_score, neighbor))
return None
# Sample Graph and Heuristics
graph = {
'A': {'B': 1, 'C': 4},
'B': {'D': 2, 'E': 5},
'C': {'F': 3},
'D': {},
'E': {'F': 1},
'F': {}
}
heuristics = {
'A': 6,
'B': 4,
'C': 4,
'D': 2,
'E': 1,
'F': 0
}
# Run
start = 'A'
goal = 'F'
path = a_star_algorithm(start, goal, graph, heuristics)
print("A* Path:", path)
AOSTAR:
class AOStar:
def __init__(self, graph, heuristics, start):
self.graph = graph
self.heuristics = heuristics
self.start = start
self.solution = {}
self.status = {}
self.parents = {}
def get_min_cost_successors(self, node):
min_cost = float('inf')
best_successors = None
for successors in self.graph.get(node, []):
cost = 0
for child in successors:
cost += self.heuristics[child] # simple heuristic sum
if cost < min_cost:
min_cost = cost
best_successors = successors
return best_successors
def ao_star(self, node):
print(f"Expanding Node: {node}")
if node not in self.graph or not self.graph[node]:
self.status[node] = 'Solved'
return
min_successors = self.get_min_cost_successors(node)
self.solution[node] = min_successors
for child in min_successors:
self.parents[child] = node
self.ao_star(child)
if all(self.status.get(child) == 'Solved' for child in min_successors):
self.status[node] = 'Solved'
def print_solution(self):
print("AO* Solution Path:")
def recursive_print(node):
if node in self.solution:
children = self.solution[node]
print(f"{node} -> {children}")
for child in children:
recursive_print(child)
recursive_print(self.start)
# Graph and Heuristics for AO*
graph = {
'A': [('B', 'C'), ('D',)],
'B': [('E',)],
'C': [],
'D': [('F',)],
'E': [],
'F': []
}
heuristics = {
'A': 10,
'B': 4,
'C': 3,
'D': 6,
'E': 2,
'F': 1
}
ao = AOStar(graph, heuristics, 'A')
ao.ao_star('A')
ao.print_solution()
ALPHABETAPRUNNING:
def alpha_beta(node, depth, alpha, beta, maximizing_player, tree):
if depth == 0 or node not in tree or isinstance(tree[node], int):
return tree[node] if node in tree else node
if maximizing_player:
max_eval = float('-inf')
for child in tree[node]:
eval = alpha_beta(child, depth - 1, alpha, beta, False, tree)
max_eval = max(max_eval, eval)
alpha = max(alpha, eval)
if beta <= alpha:
break
return max_eval
else:
min_eval = float('inf')
for child in tree[node]:
eval = alpha_beta(child, depth - 1, alpha, beta, True, tree)
min_eval = min(min_eval, eval)
beta = min(beta, eval)
if beta <= alpha:
break
return min_eval
# Example game tree
game_tree = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': 3,
'E': 5,
'F': 6,
'G': 9
}
result = alpha_beta('A', 3, float('-inf'), float('inf'), True, game_tree)
print("Alpha-Beta result:", result)
4QUEENS:
def is_safe(board, row, col):
for i in range(row):
if board[i] == col or \
board[i] - i == col - row or \
board[i] + i == col + row:
return False
return True
def solve_n_queens(n, row=0, board=[]):
if row == n:
print("Solution:", board)
return
for col in range(n):
if is_safe(board, row, col):
solve_n_queens(n, row + 1, board + [col])
# Run
solve_n_queens(4)
8QUEENS:
from collections import deque
def is_goal(state):
return state == ['1','2','3','4','5','6','7','8','0']
def get_neighbors(state):
neighbors = []
index = state.index('0')
moves = []
if index % 3 != 0: moves.append(-1) # left
if index % 3 != 2: moves.append(1) # right
if index - 3 >= 0: moves.append(-3) # up
if index + 3 < 9: moves.append(3) # down
for move in moves:
new = state[:]
new[index], new[index + move] = new[index + move], new[index]
neighbors.append(new)
return neighbors
def bfs_8_puzzle(start):
visited = set()
queue = deque([(start, [])])
while queue:
state, path = queue.popleft()
if tuple(state) in visited:
continue
visited.add(tuple(state))
if is_goal(state):
print("Solved in", len(path), "moves:", path)
return
for neighbor in get_neighbors(state):
queue.append((neighbor, path + [neighbor]))
# Run
start_state = ['1','2','3','4','0','6','7','5','8']
bfs_8_puzzle(start_state)
BFS AND DFS
from collections import deque
def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=' ')
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
print(node, end=' ')
visited.add(node)
stack.extend(reversed(graph.get(node, [])))
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=' ')
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Example graph
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': [],
'F': []
}
print("DFS Recursive:")
dfs_recursive(graph, 'A')
print("\nDFS Iterative:")
dfs_iterative(graph, 'A')
print("\nBFS:")
bfs(graph, 'A')
HILL CLIMBING
import random
def hill_climb(start, func, step_size=0.1, max_iterations=1000):
current_x = start
current_val = func(current_x)
for i in range(max_iterations):
# Check neighbors
next_x1 = current_x + step_size
next_x2 = current_x - step_size
next_val1 = func(next_x1)
next_val2 = func(next_x2)
# Choose the best neighbor
if next_val1 > current_val:
current_x = next_x1
current_val = next_val1
elif next_val2 > current_val:
current_x = next_x2
current_val = next_val2
else:
# No better neighbor found
break
return current_x, current_val
# Define the function to maximize
def f(x):
return -x**2 + 10*x # Max at x = 5
# Start from a random point
start_point = random.uniform(0, 10)
# Run the hill climbing algorithm
solution_x, solution_val = hill_climb(start_point, f)
# Output the result
print("Start at x =", round(start_point, 2))
print("Reached x =", round(solution_x, 2), "with f(x) =", round(solution_val, 2))
MONKEY BANANA
def monkey_banana():
state = {
'monkey': 'floor',
'box': 'corner',
'banana': 'ceiling'
}
print("Initial state:", state)
# Monkey moves box under banana
state['box'] = 'under_banana'
print("Monkey pushes box under banana")
# Monkey climbs on box
state['monkey'] = 'on_box'
print("Monkey climbs on box")
# Monkey grabs banana
if state['monkey'] == 'on_box' and state['box'] == 'under_banana':
print("Monkey grabs the banana!")
else:
print("Monkey cannot reach the banana.")
# Run
monkey_banana()
TIC TAC TOE
def print_board(board):
for row in board:
print(" | ".join(row))
print("-" * 5)
def check_winner(board, player):
for row in board:
if all(cell == player for cell in row): return True
for col in range(3):
if all(board[row][col] == player for row in range(3)): return True
if all(board[i][i] == player for i in range(3)): return True
if all(board[i][2 - i] == player for i in range(3)): return True
return False
def tic_tac_toe():
board = [[" "]*3 for _ in range(3)]
current = "X"
for turn in range(9):
print_board(board)
row = int(input(f"{current}'s turn. Enter row (0-2): "))
col = int(input(f"{current}'s turn. Enter col (0-2): "))
if board[row][col] == " ":
board[row][col] = current
if check_winner(board, current):
print_board(board)
print(f"{current} wins!")
return
current = "O" if current == "X" else "X"
else:
print("Cell already taken. Try again.")
print_board(board)
print("It's a draw!")
# Run game
# tic_tac_toe()
TOWER OF HANOI
def tower_of_hanoi(n, source, target, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
tower_of_hanoi(n - 1, source, auxiliary, target)
print(f"Move disk {n} from {source} to {target}")
tower_of_hanoi(n - 1, auxiliary, target, source)
# Run for 3 disks
tower_of_hanoi(3, 'A', 'C', 'B')
WATER OF HUG
def water_jug():
visited = set()
stack = [(0, 0)] # (4L, 3L)
while stack:
a, b = stack.pop()
if (a, b) in visited:
continue
visited.add((a, b))
print(f"Jug1: {a}L, Jug2: {b}L")
if a == 2:
print("Reached goal state (2L in 4L jug).")
return
# Fill, empty, pour actions
possible = [
(4, b), (a, 3), # Fill
(0, b), (a, 0), # Empty
(max(0, a - (3 - b)), min(3, b + a)), # Pour A->B
(min(4, a + b), max(0, b - (4 - a))) # Pour B->A
]
stack.extend(possible)
# Run
water_jug()
