This notebook provides complete Python implementations of all search algorithms with a real-world routing application.
Contents¶
1. Setup and Imports {#setup}¶
# Essential imports
from collections import deque, defaultdict
from typing import List, Set, Optional, Callable, Tuple, Any, Dict
import heapq
import random
import math
import time
from abc import ABC, abstractmethod
from copy import deepcopy
print('Libraries imported successfully')2. Framework Classes {#framework}¶
Abstract base classes for search problems and nodes.
class SearchProblem(ABC):
def __init__(self, initial_state, goal_state=None):
self.initial_state = initial_state
self.goal_state = goal_state
@abstractmethod
def is_goal(self, state) -> bool:
pass
@abstractmethod
def get_actions(self, state) -> List[Any]:
pass
@abstractmethod
def get_successor(self, state, action) -> Any:
pass
def action_cost(self, state, action, next_state) -> float:
return 1.0
def get_successors(self, state) -> List[Tuple[Any, Any, float]]:
successors = []
for action in self.get_actions(state):
next_state = self.get_successor(state, action)
cost = self.action_cost(state, action, next_state)
successors.append((action, next_state, cost))
return successors
class SearchNode:
def __init__(self, state, parent=None, action=None, path_cost=0.0, depth=0):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
self.depth = depth
def expand(self, problem):
children = []
for action, next_state, cost in problem.get_successors(self.state):
child = SearchNode(
state=next_state,
parent=self,
action=action,
path_cost=self.path_cost + cost,
depth=self.depth + 1
)
children.append(child)
return children
def get_path(self):
path = []
node = self
while node:
path.append(node.state)
node = node.parent
return list(reversed(path))
def __lt__(self, other):
return self.path_cost < other.path_cost
print('Framework classes defined')3. Uninformed Search {#uninformed}¶
Breadth-First Search¶
def breadth_first_search(problem: SearchProblem, verbose: bool = True):
start_time = time.time()
initial_node = SearchNode(problem.initial_state)
frontier = deque([initial_node])
visited = {problem.initial_state}
nodes_expanded = 0
max_frontier_size = 1
while frontier:
max_frontier_size = max(max_frontier_size, len(frontier))
node = frontier.popleft()
nodes_expanded += 1
if problem.is_goal(node.state):
if verbose:
elapsed = time.time() - start_time
print(f'BFS: Solution found!')
print(f' Path length: {node.depth}')
print(f' Nodes expanded: {nodes_expanded}')
print(f' Max frontier: {max_frontier_size}')
print(f' Time: {elapsed:.4f}s')
return node.get_path()
for child in node.expand(problem):
if child.state not in visited:
visited.add(child.state)
frontier.append(child)
if verbose:
print('BFS: No solution exists')
return None
print('BFS implemented')Depth-First Search¶
def depth_first_search(problem: SearchProblem, verbose: bool = True):
start_time = time.time()
initial_node = SearchNode(problem.initial_state)
frontier = [initial_node]
visited = {problem.initial_state}
nodes_expanded = 0
while frontier:
node = frontier.pop()
nodes_expanded += 1
if problem.is_goal(node.state):
if verbose:
elapsed = time.time() - start_time
print(f'DFS: Solution found!')
print(f' Path length: {node.depth}')
print(f' Nodes expanded: {nodes_expanded}')
print(f' Time: {elapsed:.4f}s')
return node.get_path()
for child in node.expand(problem):
if child.state not in visited:
visited.add(child.state)
frontier.append(child)
if verbose:
print('DFS: No solution exists')
return None
print('DFS implemented')Uniform-Cost Search¶
def uniform_cost_search(problem: SearchProblem, verbose: bool = True):
start_time = time.time()
initial_node = SearchNode(problem.initial_state)
frontier = [(0, 0, initial_node)]
counter = 1
best_g = {problem.initial_state: 0.0}
nodes_expanded = 0
while frontier:
cost, _, node = heapq.heappop(frontier)
if cost > best_g.get(node.state, float('inf')):
continue
nodes_expanded += 1
if problem.is_goal(node.state):
if verbose:
elapsed = time.time() - start_time
print(f'UCS: Optimal solution found!')
print(f' Path length: {node.depth}')
print(f' Cost: {node.path_cost:.2f}')
print(f' Nodes expanded: {nodes_expanded}')
print(f' Time: {elapsed:.4f}s')
return node.get_path()
for child in node.expand(problem):
if child.path_cost < best_g.get(child.state, float('inf')):
best_g[child.state] = child.path_cost
heapq.heappush(frontier, (child.path_cost, counter, child))
counter += 1
if verbose:
print('UCS: No solution exists')
return None
print('UCS implemented')4. Informed Search {#informed}¶
A* Search¶
def a_star_search(problem: SearchProblem, heuristic: Callable, verbose: bool = True):
start_time = time.time()
initial_node = SearchNode(problem.initial_state)
h_init = heuristic(problem.initial_state)
frontier = [(h_init, 0, 0.0, initial_node)]
counter = 1
best_g = {problem.initial_state: 0.0}
nodes_expanded = 0
while frontier:
f_val, _, g_val, node = heapq.heappop(frontier)
if g_val > best_g.get(node.state, float('inf')):
continue
nodes_expanded += 1
if problem.is_goal(node.state):
if verbose:
elapsed = time.time() - start_time
print(f'A*: Optimal solution found!')
print(f' Path length: {node.depth}')
print(f' Cost: {node.path_cost:.2f}')
print(f' Nodes expanded: {nodes_expanded}')
print(f' Time: {elapsed:.4f}s')
return node.get_path()
for child in node.expand(problem):
if child.path_cost < best_g.get(child.state, float('inf')):
best_g[child.state] = child.path_cost
h_child = heuristic(child.state)
f_child = child.path_cost + h_child
heapq.heappush(frontier, (f_child, counter, child.path_cost, child))
counter += 1
if verbose:
print('A*: No solution exists')
return None
print('A* implemented')5. Local Search {#local}¶
Hill Climbing¶
def hill_climbing(initial_state, get_neighbors, evaluate, max_iter=1000, verbose=True):
current = initial_state
current_value = evaluate(current)
iterations = 0
while iterations < max_iter:
neighbors = get_neighbors(current)
if not neighbors:
break
best_neighbor = min(neighbors, key=evaluate)
best_value = evaluate(best_neighbor)
if best_value >= current_value:
break
current = best_neighbor
current_value = best_value
iterations += 1
if verbose:
print(f'Hill Climbing: {iterations} iterations, value={current_value:.4f}')
return current, current_value
print('Hill Climbing implemented')Simulated Annealing¶
def simulated_annealing(initial_state, get_neighbor, evaluate,
temp=100.0, cooling=0.95, min_temp=0.01, verbose=True):
current = initial_state
current_value = evaluate(current)
best = current
best_value = current_value
T = temp
iterations = 0
while T > min_temp:
neighbor = get_neighbor(current)
neighbor_value = evaluate(neighbor)
delta = neighbor_value - current_value
if delta < 0 or random.random() < math.exp(-delta / T):
current = neighbor
current_value = neighbor_value
if current_value < best_value:
best = current
best_value = current_value
T *= cooling
iterations += 1
if verbose:
print(f'Simulated Annealing: {iterations} iterations, best={best_value:.4f}')
return best, best_value
print('Simulated Annealing implemented')6. 8-Puzzle Example {#puzzle}¶
class EightPuzzle(SearchProblem):
def __init__(self, initial, goal=None):
if goal is None:
goal = tuple(range(1, 9)) + (0,)
super().__init__(tuple(initial), tuple(goal))
def find_blank(self, state):
return state.index(0)
def get_actions(self, state):
blank = self.find_blank(state)
row, col = blank // 3, blank % 3
actions = []
if row > 0: actions.append('UP')
if row < 2: actions.append('DOWN')
if col > 0: actions.append('LEFT')
if col < 2: actions.append('RIGHT')
return actions
def get_successor(self, state, action):
blank = self.find_blank(state)
row, col = blank // 3, blank % 3
moves = {'UP': (-1, 0), 'DOWN': (1, 0), 'LEFT': (0, -1), 'RIGHT': (0, 1)}
dr, dc = moves[action]
new_row, new_col = row + dr, col + dc
new_blank = new_row * 3 + new_col
state_list = list(state)
state_list[blank], state_list[new_blank] = state_list[new_blank], state_list[blank]
return tuple(state_list)
def is_goal(self, state):
return state == self.goal_state
def manhattan_distance(state, goal=(1,2,3,4,5,6,7,8,0)):
distance = 0
for i in range(9):
if state[i] != 0:
goal_idx = goal.index(state[i])
curr_row, curr_col = i // 3, i % 3
goal_row, goal_col = goal_idx // 3, goal_idx % 3
distance += abs(curr_row - goal_row) + abs(curr_col - goal_col)
return distance
print('8-Puzzle implementation complete')Test 8-Puzzle¶
print('=== 8-Puzzle: Algorithm Comparison ===')
print()
initial = (1, 2, 3, 4, 0, 5, 7, 8, 6)
goal = (1, 2, 3, 4, 5, 6, 7, 8, 0)
puzzle = EightPuzzle(initial, goal)
print('BFS:')
solution_bfs = breadth_first_search(puzzle)
print('\nA* with Manhattan Distance:')
solution_astar = a_star_search(puzzle, lambda s: manhattan_distance(s, goal))7. Real-World: City Routing {#routing}¶
class CityRoutingProblem(SearchProblem):
def __init__(self, graph, start, goal, coords=None):
super().__init__(start, goal)
self.graph = graph
self.coordinates = coords or {}
def is_goal(self, state):
return state == self.goal_state
def get_actions(self, state):
if state in self.graph:
return [neighbor for neighbor, _ in self.graph[state]]
return []
def get_successor(self, state, action):
return action
def action_cost(self, state, action, next_state):
for neighbor, dist in self.graph[state]:
if neighbor == next_state:
return dist
return float('inf')
def straight_line_distance(self, city1, city2):
if city1 not in self.coordinates or city2 not in self.coordinates:
return 0
lat1, lon1 = self.coordinates[city1]
lat2, lon2 = self.coordinates[city2]
return math.sqrt((lat2 - lat1)**2 + (lon2 - lon1)**2)
# Romanian cities graph
romanian_graph = {
'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 Vilcea', 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 Vilcea', 146), ('Pitesti', 138)],
'Rimnicu Vilcea': [('Sibiu', 80), ('Craiova', 146), ('Pitesti', 97)],
'Fagaras': [('Sibiu', 99), ('Bucharest', 211)],
'Pitesti': [('Rimnicu Vilcea', 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)]
}
romanian_coords = {
'Arad': (46.17, 21.32), 'Bucharest': (44.43, 26.10),
'Craiova': (44.33, 23.79), 'Drobeta': (44.63, 22.67),
'Eforie': (44.06, 28.63), 'Fagaras': (45.84, 24.97),
'Giurgiu': (43.90, 25.97), 'Hirsova': (44.69, 27.95),
'Iasi': (47.16, 27.60), 'Lugoj': (45.69, 21.90),
'Mehadia': (44.91, 22.36), 'Neamt': (46.93, 26.38),
'Oradea': (47.05, 21.92), 'Pitesti': (44.86, 24.87),
'Rimnicu Vilcea': (45.10, 24.37), 'Sibiu': (45.80, 24.13),
'Timisoara': (45.75, 21.21), 'Urziceni': (44.72, 26.64),
'Vaslui': (46.64, 27.73), 'Zerind': (46.63, 21.52)
}
print('City routing problem defined')Compare Routing Algorithms¶
print('=== Routing: Arad to Bucharest ===')
print()
routing = CityRoutingProblem(romanian_graph, 'Arad', 'Bucharest', romanian_coords)
print('Uniform-Cost Search:')
solution_ucs = uniform_cost_search(routing)
print('\nA* Search:')
solution_astar = a_star_search(
routing,
lambda city: routing.straight_line_distance(city, 'Bucharest')
)
if solution_astar:
print(f'\nOptimal route: {" -> ".join(solution_astar)}')
total_dist = 0
for i in range(len(solution_astar) - 1):
current = solution_astar[i]
next_city = solution_astar[i + 1]
for neighbor, dist in romanian_graph[current]:
if neighbor == next_city:
total_dist += dist
break
print(f'Total distance: {total_dist} km')Summary¶
This implementation notebook demonstrates:
Implementations¶
Uninformed Search: BFS, DFS, UCS
Informed Search: A* with admissible heuristics
Local Search: Hill Climbing, Simulated Annealing
Examples¶
8-Puzzle with Manhattan distance heuristic
City routing with real geographic data
Key Insights¶
A* dramatically outperforms uninformed search
Good heuristics reduce nodes expanded
Admissibility ensures optimality
For theoretical details, see the main chapter: Chapter 2: Searching State Spaces