Chapter 2 Lab: Search Algorithms

# Romania map from the textbook
romania_map = {
    'Arad': [('Zerind', 75), ('Sibiu', 140), ('Timisoara', 118)],
    'Zerind': [('Arad', 75), ('Oradea', 71)],
    'Oradea': [('Zerind', 71), ('Sibiu', 151)],
    'Sibiu': [('Arad', 140), ('Oradea', 151), ('Fagaras', 99), ('Rimnicu', 80)],
    'Timisoara': [('Arad', 118), ('Lugoj', 111)],
    'Lugoj': [('Timisoara', 111), ('Mehadia', 70)],
    'Mehadia': [('Lugoj', 70), ('Drobeta', 75)],
    'Drobeta': [('Mehadia', 75), ('Craiova', 120)],
    'Craiova': [('Drobeta', 120), ('Rimnicu', 146), ('Pitesti', 138)],
    'Rimnicu': [('Sibiu', 80), ('Craiova', 146), ('Pitesti', 97)],
    'Fagaras': [('Sibiu', 99), ('Bucharest', 211)],
    'Pitesti': [('Rimnicu', 97), ('Craiova', 138), ('Bucharest', 101)],
    'Bucharest': [('Fagaras', 211), ('Pitesti', 101), ('Giurgiu', 90), ('Urziceni', 85)],
    'Giurgiu': [('Bucharest', 90)],
    'Urziceni': [('Bucharest', 85), ('Vaslui', 142), ('Hirsova', 98)],
    'Hirsova': [('Urziceni', 98), ('Eforie', 86)],
    'Eforie': [('Hirsova', 86)],
    'Vaslui': [('Urziceni', 142), ('Iasi', 92)],
    'Iasi': [('Vaslui', 92), ('Neamt', 87)],
    'Neamt': [('Iasi', 87)]
}

# Straight-line distances to Bucharest (heuristic)
h_bucharest = {
    'Arad': 366, 'Bucharest': 0, 'Craiova': 160, 'Drobeta': 242,
    'Eforie': 161, 'Fagaras': 176, 'Giurgiu': 77, 'Hirsova': 151,
    'Iasi': 226, 'Lugoj': 244, 'Mehadia': 241, 'Neamt': 234,
    'Oradea': 380, 'Pitesti': 100, 'Rimnicu': 193, 'Sibiu': 253,
    'Timisoara': 329, 'Urziceni': 80, 'Vaslui': 199, 'Zerind': 374
}

def bfs_search(graph, start, goal):
    """
    TODO: Implement Breadth-First Search
    Return: (path, nodes_expanded)
    """
    pass

def dfs_search(graph, start, goal):
    """
    TODO: Implement Depth-First Search
    Return: (path, nodes_expanded)
    """
    pass

def a_star_search(graph, start, goal, heuristic):
    """
    TODO: Implement A* Search
    Return: (path, cost, nodes_expanded)
    """
    pass

# Test implementations
start, goal = 'Arad', 'Bucharest'
print(f'Finding path from {start} to {goal}\n')

# Compare algorithms
print('BFS:', bfs_search(romania_map, start, goal))
print('DFS:', dfs_search(romania_map, start, goal))
print('A*:', a_star_search(romania_map, start, goal, h_bucharest))

import heapq
from typing import Tuple

class PuzzleState:
    def __init__(self, board, parent=None, action=None, cost=0):
        self.board = board
        self.parent = parent
        self.action = action
        self.cost = cost
        
    def __lt__(self, other):
        return self.cost < other.cost

def manhattan_distance(state, goal):
    """
    TODO: Calculate Manhattan distance heuristic
    For each tile, sum the distances from its current position to goal position
    """
    pass

def misplaced_tiles(state, goal):
    """
    TODO: Count number of misplaced tiles
    """
    pass

def linear_conflict(state, goal):
    """
    CHALLENGE: Implement linear conflict heuristic
    Manhattan distance + 2 * (number of linear conflicts)
    """
    pass

def get_successors(state):
    """Generate all valid successor states"""
    # YOUR CODE HERE
    pass

def solve_puzzle(initial, goal, heuristic):
    """
    TODO: Solve 8-puzzle using A* with given heuristic
    Return: (solution_path, nodes_expanded, max_frontier_size)
    """
    pass

# Test cases
initial = (1, 2, 3, 4, 0, 5, 7, 8, 6)  # Easy
goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)

print('Comparing heuristics on 8-puzzle:\n')
for name, heuristic in [('Manhattan', manhattan_distance), 
                         ('Misplaced', misplaced_tiles)]:
    result = solve_puzzle(initial, goal, heuristic)
    print(f'{name:12s}: {result}')

def is_safe(board, row, col, n):
    """Check if placing queen at (row, col) is safe"""
    # YOUR CODE HERE
    pass

def solve_n_queens_backtrack(n):
    """
    TODO: Solve N-Queens using backtracking
    Return: List of all solutions
    """
    pass

def solve_n_queens_forward_checking(n):
    """
    TODO: Solve N-Queens with forward checking
    Track remaining valid positions for each unplaced queen
    """
    pass

# Test and compare
for n in [4, 8]:
    print(f'\n{n}-Queens Problem:')
    solutions = solve_n_queens_backtrack(n)
    print(f'Found {len(solutions)} solutions')
    if solutions:
        print(f'First solution: {solutions[0]}')

import random
import math

def hill_climbing(problem, max_iterations=1000):
    """
    TODO: Implement hill climbing
    problem should have: random_state(), neighbors(state), value(state)
    """
    pass

def simulated_annealing(problem, schedule, max_iterations=10000):
    """
    TODO: Implement simulated annealing
    schedule(t) returns temperature at time t
    """
    pass

# Test on N-Queens (minimize conflicts)
class NQueensLocalSearch:
    def __init__(self, n):
        self.n = n
        
    def random_state(self):
        # Random queen placement (one per column)
        return [random.randint(0, self.n-1) for _ in range(self.n)]
        
    def conflicts(self, state):
        """Count number of queen conflicts"""
        # YOUR CODE HERE
        pass
        
    def value(self, state):
        return -self.conflicts(state)  # Negative for minimization
        
    def neighbors(self, state):
        """Generate neighbor states"""
        # YOUR CODE HERE
        pass

# Test both algorithms
problem = NQueensLocalSearch(8)
print('Hill Climbing:', hill_climbing(problem))
print('Simulated Annealing:', simulated_annealing(problem, lambda t: 100*(0.95**t)))

import time
import matplotlib.pyplot as plt
import pandas as pd

def benchmark_search(algorithm, problem_set, name):
    """Run algorithm on multiple problems and collect metrics"""
    results = []
    for problem in problem_set:
        start_time = time.time()
        path, nodes, cost = algorithm(problem)
        elapsed = time.time() - start_time
        results.append({
            'algorithm': name,
            'nodes_expanded': nodes,
            'solution_cost': cost,
            'time': elapsed,
            'path_length': len(path) if path else 0
        })
    return results

# Generate test problems
test_problems = []  # YOUR CODE: Create varied difficulty problems

# Benchmark all algorithms
all_results = []
for algo, name in [(bfs_search, 'BFS'), 
                    (dfs_search, 'DFS'),
                    (a_star_search, 'A*')]:
    results = benchmark_search(algo, test_problems, name)
    all_results.extend(results)

# Create comparison DataFrame
df = pd.DataFrame(all_results)

# Visualizations
fig, axes = plt.subplots(2, 2, figsize=(12, 10))

# Plot 1: Nodes expanded
df.groupby('algorithm')['nodes_expanded'].mean().plot(kind='bar', ax=axes[0,0])
axes[0,0].set_title('Average Nodes Expanded')

# Plot 2: Solution cost
df.groupby('algorithm')['solution_cost'].mean().plot(kind='bar', ax=axes[0,1])
axes[0,1].set_title('Average Solution Cost')

# Plot 3: Time
df.groupby('algorithm')['time'].mean().plot(kind='bar', ax=axes[1,0])
axes[1,0].set_title('Average Time (seconds)')

# Plot 4: Path length
df.groupby('algorithm')['path_length'].mean().plot(kind='bar', ax=axes[1,1])
axes[1,1].set_title('Average Path Length')

plt.tight_layout()
plt.show()

print('\nSummary Statistics:')
print(df.groupby('algorithm').agg({
    'nodes_expanded': ['mean', 'std'],
    'solution_cost': ['mean', 'std'],
    'time': ['mean', 'std']
}))

def bidirectional_search(graph, start, goal):
    """
    CHALLENGE: Implement bidirectional BFS
    Search from both start and goal simultaneously
    Stop when frontiers meet
    """
    pass

# Test and compare with standard BFS
print('Bidirectional vs Standard BFS:')
print('Bidirectional:', bidirectional_search(romania_map, 'Arad', 'Bucharest'))
print('Standard BFS:', bfs_search(romania_map, 'Arad', 'Bucharest'))