An exhaustive engineering treatment of goal-based rational problem solving: state-space graph formulations, uninformed tree and graph search strategies, heuristic evaluation with A* admissibility and consistency, local optimization landscapes, and constraint satisfaction problems (CSPs).
In modern Artificial Intelligence, reflex agents act purely on immediate perceptual inputs using condition-action mappings. When environments require multi-step planning over long horizons, rational action requires a Problem-Solving Agent: an agent architecture that adopts a goal, explores plausible future action sequences within an internal model, and executes the discovered optimal trajectory.
+------------------+ Percepts +---------------------+
| Environment | -----------------------> | Goal Formulation |
+------------------+ +---------------------+
^ |
| Formulated Goal
| v
| Action +---------------------+
| Sequence | Problem Formulation |
| +---------------------+
| |
| States, Actions, Cost
| v
+------------------+ +---------------------+
| Execution Phase | <----------------------- | Search Phase |
| (Online Action) | Solution Path | (Offline Simulation)|
+------------------+ +---------------------+
If an environment is deterministic and fully observable, an agent plans offline once and blindly executes the resulting action sequence (open-loop). If the environment is stochastic, dynamic, or partially observable, unexpected events can invalidate the plan. Such agents must interleave search and execution via closed-loop control (continually re-perceiving and re-planning at each intermediate step).
To allow algorithmic search, every classical AI problem must be formally specified by five well-defined mathematical components. These five components define the State Space: the set of all possible configurations reachable from the initial state by any sequence of legal actions.
The exact world configuration where the agent begins its operation. For example, in the Romania route finding problem, the initial state is represented as In(Arad). In the 8-puzzle, it is the initial 3 by 3 arrangement of numbered tiles.
Given a particular state s, the function Actions(s) returns the set of legal actions the agent can execute. For example, when in Arad, Actions(In(Arad)) = {Go(Zerind), Go(Sibiu), Go(Timisoara)}.
A formal description of what each action does. The function Result(s, a) returns the resulting state when action a is executed in state s. Together, the initial state, actions, and transition model implicitly define the directed graph of the state space.
A boolean test that evaluates whether a given state s is a goal state. This test can be explicit (e.g., checking if state == In(Bucharest)) or implicit (e.g., checking if no two queens attack each other on an 8-Queens board).
A numeric function that assigns a cost to a path. The step cost of taking action a in state s to reach state s' is denoted as StepCost(s, a, s'). The total path cost g(n) is the sum of the step costs along the path from the root to node n.
| Problem Domain | States Representation | Actions Available | Goal Test Condition | Path Cost Function |
|---|---|---|---|---|
| 8-Puzzle (Sliding Tiles) | Location of each of the 8 numbered tiles and the blank square in a 3 by 3 grid. Total reachable states: 181,440 (9! / 2). | Move the blank space: Up, Down, Left, or Right (subject to grid boundaries). | Grid matches the exact goal configuration: tiles 1 to 8 in clockwise order with center blank. | Each step costs 1 unit (path cost equals number of moves taken). |
| Romania Road Map | Current city: e.g., In(Arad), In(Oradea), In(Sibiu), etc. Total: 20 Romanian cities. |
Drive along an existing highway connecting current city to an adjacent neighbor. | Current city equals In(Bucharest). |
Sum of road segment distances in kilometers (e.g., Arad to Zerind is 75 km). |
| 8-Queens Problem | Arrangement of 0 to 8 queens on an 8 by 8 chessboard with no two queens sharing a row, column, or diagonal. | Place a new queen in an empty column, or slide an existing queen within its column. | All 8 queens are placed on the board with zero mutual attacks. | 0 for finding any valid state; or number of moves taken in iterative repair. |
| Traveling Salesperson (TSP) | Sequence of visited cities and current location. | Visit an unvisited city from current city. | All cities visited exactly once and agent has returned to the origin city. | Total distance or travel time summed over the entire tour. |
A critical conceptual distinction in AI problem solving is the difference between a State (a physical configuration of the world) and a Search Node (a book-keeping data structure instantiated during the search process).
A search node n contains five essential bookkeeping fields:
n.State: The world state corresponding to this node.n.Parent: Pointer to the node that generated this node.n.Action: The specific action applied to the parent to yield this node.n.PathCost g(n): The total cost of the path from the root to this node.n.Depth: The number of steps along the path from the root (root depth is 0).In many problem graphs, actions are reversible (e.g., Arad → Sibiu → Arad). If an algorithm does not remember where it has been, a Tree Search will traverse the same loop endlessly, building an infinite tree over a small finite state space.
To prevent infinite cycling and catastrophic exponential duplication, Graph Search maintains an explicit Explored Set (often called the Closed List) of all states whose successors have already been expanded.
Physical State Graph (Loopy) Expanded Search Tree (Without Closed List)
+---------+ [Arad]
| Arad | / \
+---------+ [Sibiu] [Zerind]
/ \ / \ \
v v [Arad] [Fagaras] [Arad]
+-------+ +--------+ / \ \ / \
| Sibiu |<->| Zerind | ... ... ... ... ...
+-------+ +--------+ (Trapped in Infinite Redundancy)
--------------------------------------------------------------------------------------
Graph Search Rule: Before expanding a node, check if node.State is in Explored Set
or Frontier. If already present with lower or equal cost, discard immediately!
Every search algorithm is evaluated rigorously against four mathematical dimensions:
g(n) among all possible solution paths?b: Branching factor (maximum number of successor nodes generated by any state).d: Depth of the shallowest goal node in the search tree.m: Maximum depth of any path in the state space (can be infinite).Uninformed Search (also known as blind search) strategies have no information about the number of steps or path cost from the current state to the goal. They can only generate successors, compute path costs so far, and recognize whether a state is a goal state.
Exploration Strategy: Explores the shallowest unexpanded node first. The frontier is implemented as a First-In, First-Out (FIFO) queue. Successors are added to the back of the queue, ensuring all nodes at depth k are expanded before any node at depth k + 1.
Goal Test Timing: In BFS, the goal test is applied at the moment a node is generated (before adding to frontier), rather than when it is popped for expansion. This early goal test saves generating the entire level d + 1.
b is finite.1 + b + b^2 + ... + b^d = O(b^d).O(b^d). Retains all generated nodes in memory. At b = 10 and depth d = 10, BFS requires storage for over 10 billion nodes (~10 Terabytes of RAM), making pure BFS impractical for deep search problems.Exploration Strategy: Explores the deepest unexpanded node first. The frontier is implemented as a Last-In, First-Out (LIFO) stack (or through recursive call stacks). The search immediately dives down one branch of the tree until it reaches a node with no successors or hits a dead end, then backtracks.
O(b^m) where m is the maximum depth of the state space. Terrible if m is much larger than d.O(b * m). Linear Space! DFS only needs to store the current path from the root to the leaf along with the unexpanded siblings at each level. This low memory consumption is DFS's massive computational advantage.
Exploration Strategy: DFS augmented with a predetermined depth limit l. Nodes at depth l are treated as leaf nodes with zero successors. This terminates infinite paths and prevents DFS from wandering forever down unbounded branches.
l has been exhausted with no solution, or a cutoff failure if a node was halted purely due to the depth limit.d > l).l > d because it retains DFS's left-branch bias.O(b^l); Space is O(b * l).
Exploration Strategy: Solves the challenge of choosing the unknown depth limit l by running Depth-Limited Search iteratively for l = 0, 1, 2, 3, ... until a goal is found.
Why Repeated Generation is Extremely Cheap: Students often worry that re-generating nodes from earlier levels is wasteful. However, in an exponential tree with branching factor b, the vast majority of nodes reside at the bottom level.
b = 10 and d = 5: BFS generates 111,110 nodes. IDS generates 123,450 nodes—an overhead of only 11%, while using orders of magnitude less memory!
b.O(b^d).O(b * d). Retains the linear memory of DFS! IDS is the gold standard uninformed search method when the search space is large and the goal depth is unknown.
Exploration Strategy: Expands the node n with the lowest path cost g(n) so far. The frontier is stored in a Priority Queue ordered by path cost g(n). While BFS explores along contour lines of equal depth, UCS spreads along contour lines of equal cumulative path cost.
Unlike BFS, UCS must never apply the goal test when a node is generated. A goal node might initially be generated via an expensive sub-optimal route. UCS must wait until the goal node is popped from the priority queue for expansion. Only then is it mathematically guaranteed that no cheaper path to that goal exists in the frontier.
StepCost >= epsilon > 0), preventing infinite cycles of zero-cost actions.O(b^(1 + floor(C* / epsilon))) where C* is the cost of the optimal solution and epsilon is the minimum edge cost. When all step costs are equal, UCS behaves identically to BFS.| Search Algorithm | Frontier Structure | Completeness | Optimality | Time Complexity | Space Complexity |
|---|---|---|---|---|---|
| Breadth-First (BFS) | FIFO Queue | Yes (if b is finite) | Yes (if step costs equal) | O(b^d) | O(b^d) [Exponential!] |
| Depth-First (DFS) | LIFO Stack | No (infinite trees) / Yes (finite graph) | No | O(b^m) | O(b * m) [Linear!] |
| Depth-Limited (DLS) | LIFO Stack with limit l | No if d > l | No | O(b^l) | O(b * l) [Linear!] |
| Iterative Deepening (IDS) | LIFO Stack (iterative limit) | Yes (if b is finite) | Yes (if step costs equal) | O(b^d) | O(b * d) [Linear!] |
| Uniform-Cost (UCS) | Priority Queue on g(n) | Yes (if step cost >= epsilon) | Yes (optimal cost) | O(b^(1 + floor(C* / epsilon))) | O(b^(1 + floor(C* / epsilon))) |
Uninformed search algorithms blindly wander through state spaces. In contrast, Informed Search (heuristic search) incorporates problem-specific knowledge via a Heuristic Function h(n) to guide the search towards promising areas of the state space.
h(n) = Estimated cost of the cheapest path from the state at node n to a goal state.n is a goal state, then h(n) = 0. Heuristics are always non-negative: h(n) >= 0.
Evaluation Function: f(n) = h(n). Expands the node that appears closest to the goal based solely on the heuristic estimate.
Vulnerabilities: Greedy search acts like a short-sighted local optimizer. It can be easily misled by false downhill heuristic gradients (e.g., heading directly toward a mountain pass that ends in a dead-end cliff).
g(n).O(b^m).Evaluation Function: Combines the past cost to reach the node and the estimated future cost to the goal:
g(n) = exact cumulative path cost from root to node n.h(n) = estimated cost from node n to the closest goal.f(n) = estimated total cost of the cheapest solution path through node n.
A* evaluates paths holistically. It expands the node in the frontier with minimum f(n). If h(n) satisfies certain mathematical conditions, A* is both complete and strictly optimal!
Uniform-Cost Search Contours A* Search Contours
(Spreads equally in all directions) (Elongated oval focused toward Goal)
...... ..
.:' ':. .:' ':.
.' '. .' '.
: [Start] : : [Start] :
'. .' '. .'
':. .:' ':. [Goal]
'''''' ''''
(High waste; explores in all directions) (Directed search guided by heuristic)
To ensure that A* returns an optimal solution, the heuristic function h(n) must satisfy rigorous mathematical constraints depending on whether Tree Search or Graph Search is utilized.
An admissible heuristic is one that never overestimates the true cost to reach the goal. It is an inherently optimistic estimator.
h*(n) represents the true, actual minimal cost required to travel from node n to the goal.
Intuition: If a heuristic were to overestimate a node's true cost, A* might prematurely dismiss an optimal path because it looked falsely expensive, returning a sub-optimal alternative instead.
A heuristic is consistent (or monotonic) if, for every node n and every successor n' generated by an action a, the estimated cost of reaching the goal from n is no greater than the step cost to reach n' plus the estimated cost to reach the goal from n'.
f(n') = g(n') + h(n') = g(n) + StepCost(n, a, n') + h(n') >= g(n) + h(n) = f(n).f(n) along any path are monotonically non-decreasing!
When h(n) is consistent, the first time A* expands a state, the path cost to that state is guaranteed to be optimal! This eliminates the need to ever reopen or update states in the Explored Set, guaranteeing optimal graph search with maximum efficiency.
Theorem: Every consistent heuristic is admissible. (However, an admissible heuristic is not necessarily consistent, though almost all natural admissible heuristics are).
Consider the 8-puzzle. How do we create admissible heuristics?
h1 never overestimates: h1(n) <= h*(n). (Admissible and consistent).n, h2(n) >= h1(n).h2 gives larger (closer to actual) estimates, h2 dominates h1. In practice, A* using h2 will expand significantly fewer nodes than A* using h1 to find the exact same optimal solution!
In many real-world problems (such as VLSI chip layout, telecommunication network design, factory job scheduling, or N-Queens placement), the path taken to reach the goal is completely irrelevant. Only the final configuration matters.
Local Search Algorithms operate on a single current state (or a small set of states) and move exclusively to immediate neighbors. They use virtually zero memory (O(1) space) and can find good solutions in gigantic or continuous state spaces where systematic tree search is intractable.
Objective
Function ^ Global Maximum
| /\
| / \ Plateau (Flat Local Max)
| Local Max / \ _______________
| /\ / \ / \
| / \ / \ / \
| / \_____/ \_/ \
| / Shoulder
|_____/__________________________________________________>
State Space
Known as Greedy Local Search or steepest-ascent. The algorithm moves continually in the direction of increasing elevation (or decreasing cost). It terminates when no neighbor has higher value.
Pathological Pitfalls:
Inspired by metallurgy (heating metal to high temperature and slowly cooling it to allow atoms to settle into a defect-free, minimum-energy crystal lattice).
Core Principle: Escape local extrema by occasionally accepting downhill (worse) moves with a probability that decreases over time:
At high temperature T, almost all moves are accepted (random walk exploration). As T cools towards zero, bad moves are rejected (pure hill-climbing convergence).
Inspired by Darwinian natural selection. Operates on a population of candidate states encoded as strings (chromosomes).
Evolutionary Cycle:
k candidate solutions.In standard search, states are atomic "black boxes" with no internal structure accessible to the algorithm. A Constraint Satisfaction Problem (CSP) uses a factored representation where states are composed of variables, each with a domain of values, and a set of explicit constraints that values must satisfy.
{X1, X2, ..., Xn} — The variables to be assigned values (e.g., Australian territories: WA, NT, SA, Q, NSW, V, T).{D1, D2, ..., Dn} — The set of allowable values for each variable (e.g., colors: {Red, Green, Blue}).{C1, C2, ..., Cm} — Pairwise or group restrictions specifying legal combinations of values (e.g., SA != WA, SA != NT).A state is a partial assignment of values to variables. An assignment is consistent if it violates no constraints. A complete assignment assigns a value to every variable. The goal of a CSP is to find a complete, consistent assignment.
Because variable assignments are commutative (assigning WA = Red then NT = Green is identical to assigning NT = Green then WA = Red), a basic CSP search only needs to consider assignments for a single variable at each step.
Backtracking Search is a specialized depth-first search that chooses values for one variable at a time, checks consistency, and backtracks immediately when a variable has no legal values left.
Rather than merely searching, CSP solvers use Constraint Propagation: reasoning forward to prune impossible values from variable domains before search explores them.
Whenever variable X is assigned value v, examine each unassigned neighbor Y connected to X by a constraint and delete from Y's domain any value inconsistent with v. If any domain becomes empty, backtrack immediately.
Limitation: It only checks forward from the newly assigned variable to its immediate neighbors. It does not detect indirect inconsistencies between unassigned neighbors.
A directed arc (Xi, Xj) is arc-consistent if for every value x in domain Di, there exists at least one value y in Dj that satisfies the constraint.
AC-3 Workflow: Maintains a queue of all directed arcs. When an arc (Xi, Xj) has values pruned from Di, all incoming arcs (Xk, Xi) must be re-added to the queue because pruning Di might make Xk arc-inconsistent! AC-3 propagates constraints transitively across the entire network.
Below is a complete, production-grade Python script demonstrating: Graph Search with Breadth-First Search (BFS), Uniform-Cost Search (UCS), and A* Search on Romania's road map, followed by a Constraint Satisfaction Backtracking Solver for Map Coloring with the MRV heuristic and Forward Checking.
"""
AI Track Unit 3: Classical Search Algorithms and CSP Solver
Russell & Norvig AIMA 4th Edition Compliant
Author: DevAscent Engineering Team
"""
import heapq
from collections import deque
from typing import Dict, List, Tuple, Optional, Set
# =====================================================================
# 1. ROMANIA ROAD MAP GRAPH DEFINITION
# =====================================================================
ROMANIA_MAP: Dict[str, List[Tuple[str, int]]] = {
'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)]
}
# Straight-Line Distance Heuristic h(n) to Bucharest (Admissible and Consistent)
SLD_TO_BUCHAREST: Dict[str, int] = {
'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 Vilcea': 193, 'Sibiu': 253,
'Timisoara': 329, 'Urziceni': 80, 'Vaslui': 199, 'Zerind': 374
}
# =====================================================================
# 2. BREADTH-FIRST SEARCH (BFS)
# =====================================================================
def breadth_first_search(graph: Dict[str, List[Tuple[str, int]]], start: str, goal: str):
"""
Standard BFS using a FIFO queue.
Early goal test is applied on child generation.
"""
if start == goal:
return [start], 0
frontier = deque([start])
explored: Set[str] = {start}
parent_map: Dict[str, str] = {}
path_cost_map: Dict[str, int] = {start: 0}
while frontier:
current = frontier.popleft()
for neighbor, weight in graph.get(current, []):
if neighbor not in explored and neighbor not in frontier:
parent_map[neighbor] = current
path_cost_map[neighbor] = path_cost_map[current] + weight
# Early Goal Test for BFS
if neighbor == goal:
path = []
curr = goal
while curr in parent_map:
path.append(curr)
curr = parent_map[curr]
path.append(start)
path.reverse()
return path, path_cost_map[goal]
frontier.append(neighbor)
explored.add(neighbor)
return None, float('inf')
# =====================================================================
# 3. UNIFORM-COST SEARCH (UCS) / DIJKSTRA
# =====================================================================
def uniform_cost_search(graph: Dict[str, List[Tuple[str, int]]], start: str, goal: str):
"""
Uniform-Cost Search using priority queue ordered by path cost g(n).
Goal test applied on POPPING node for expansion.
"""
# Priority queue stores tuples: (cumulative_g, node_state, path_list)
pq = [(0, start, [start])]
explored: Dict[str, int] = {}
while pq:
cost, current, path = heapq.heappop(pq)
# Goal Test on Removal (Guarantees Optimality)
if current == goal:
return path, cost
if current in explored and explored[current] <= cost:
continue
explored[current] = cost
for neighbor, weight in graph.get(current, []):
new_cost = cost + weight
if neighbor not in explored or new_cost < explored[neighbor]:
heapq.heappush(pq, (new_cost, neighbor, path + [neighbor]))
return None, float('inf')
# =====================================================================
# 4. A* SEARCH (A-STAR)
# =====================================================================
def a_star_search(graph: Dict[str, List[Tuple[str, int]]],
heuristic: Dict[str, int],
start: str,
goal: str):
"""
A* Graph Search using f(n) = g(n) + h(n).
Optimal with consistent heuristic (SLD).
"""
# Priority queue stores: (f_score, g_cost, state, path)
initial_f = 0 + heuristic[start]
pq = [(initial_f, 0, start, [start])]
best_g: Dict[str, int] = {start: 0}
nodes_expanded = 0
while pq:
f, g, current, path = heapq.heappop(pq)
nodes_expanded += 1
# Goal test when popped
if current == goal:
return path, g, nodes_expanded
# If we already found a cheaper route to this state, skip
if g > best_g.get(current, float('inf')):
continue
for neighbor, weight in graph.get(current, []):
new_g = g + weight
if new_g < best_g.get(neighbor, float('inf')):
best_g[neighbor] = new_g
new_f = new_g + heuristic[neighbor]
heapq.heappush(pq, (new_f, new_g, neighbor, path + [neighbor]))
return None, float('inf'), nodes_expanded
# =====================================================================
# 5. CONSTRAINT SATISFACTION PROBLEM (CSP) SOLVER
# Map Coloring with Minimum Remaining Values (MRV) & Forward Checking
# =====================================================================
class MapColoringCSP:
def __init__(self, variables: List[str], domains: Dict[str, List[str]], neighbors: Dict[str, List[str]]):
self.variables = variables
self.domains = {var: list(domains[var]) for var in variables}
self.neighbors = neighbors
def is_consistent(self, var: str, value: str, assignment: Dict[str, str]) -> bool:
"""Check if assigning value to var violates any constraint with already assigned neighbors."""
for neighbor in self.neighbors.get(var, []):
if neighbor in assignment and assignment[neighbor] == value:
return False
return True
def select_unassigned_variable_mrv(self, assignment: Dict[str, str]) -> str:
"""Minimum Remaining Values (MRV): Pick variable with smallest legal domain."""
unassigned = [v for v in self.variables if v not in assignment]
return min(unassigned, key=lambda var: len(self.domains[var]))
def forward_check(self, var: str, value: str, assignment: Dict[str, str]) -> Optional[Dict[str, List[str]]]:
"""
Prune 'value' from unassigned neighbors.
Returns pruned dictionary snapshot or None if domain wipeout occurs.
"""
pruned = {}
for neighbor in self.neighbors.get(var, []):
if neighbor not in assignment:
if value in self.domains[neighbor]:
if len(self.domains[neighbor]) == 1:
# Domain wipeout!
return None
self.domains[neighbor].remove(value)
pruned.setdefault(neighbor, []).append(value)
return pruned
def restore_domains(self, pruned: Dict[str, List[str]]):
"""Restore pruned values upon backtracking."""
for var, values in pruned.items():
self.domains[var].extend(values)
def backtrack(self, assignment: Dict[str, str]) -> Optional[Dict[str, str]]:
"""Backtracking search with MRV and Forward Checking."""
if len(assignment) == len(self.variables):
return assignment
var = self.select_unassigned_variable_mrv(assignment)
for value in list(self.domains[var]):
if self.is_consistent(var, value, assignment):
assignment[var] = value
pruned = self.forward_check(var, value, assignment)
if pruned is not None:
result = self.backtrack(assignment)
if result is not None:
return result
self.restore_domains(pruned)
del assignment[var]
return None
# =====================================================================
# DEMONSTRATION HARNESS
# =====================================================================
if __name__ == "__main__":
print("=" * 68)
print("DEMO 1: CLASSICAL PATH SEARCH ON ROMANIA ROAD NETWORK")
print("Origin: Arad --> Destination: Bucharest")
print("=" * 68)
# 1. Breadth-First Search
bfs_path, bfs_cost = breadth_first_search(ROMANIA_MAP, 'Arad', 'Bucharest')
print(f"[BFS] Path: {' -> '.join(bfs_path)}")
print(f"[BFS] Cumulative Cost: {bfs_cost} km (Note: Sub-optimal! BFS minimizes hops, not cost)\n")
# 2. Uniform-Cost Search
ucs_path, ucs_cost = uniform_cost_search(ROMANIA_MAP, 'Arad', 'Bucharest')
print(f"[UCS] Path: {' -> '.join(ucs_path)}")
print(f"[UCS] Cumulative Cost: {ucs_cost} km (Guaranteed Optimal!)\n")
# 3. A* Search
astar_path, astar_cost, expanded = a_star_search(ROMANIA_MAP, SLD_TO_BUCHAREST, 'Arad', 'Bucharest')
print(f"[A* ] Path: {' -> '.join(astar_path)}")
print(f"[A* ] Cumulative Cost: {astar_cost} km (Optimal & Efficient)")
print(f"[A* ] Total Nodes Expanded: {expanded}\n")
print("=" * 68)
print("DEMO 2: MAP COLORING CSP (AUSTRALIA 7 REGIONS, 3 COLORS)")
print("=" * 68)
regions = ['WA', 'NT', 'SA', 'Q', 'NSW', 'V', 'T']
colors = ['Red', 'Green', 'Blue']
initial_domains = {r: colors.copy() for r in regions}
adjacencies = {
'WA': ['NT', 'SA'],
'NT': ['WA', 'SA', 'Q'],
'SA': ['WA', 'NT', 'Q', 'NSW', 'V'],
'Q': ['NT', 'SA', 'NSW'],
'NSW':['SA', 'Q', 'V'],
'V': ['SA', 'NSW'],
'T': [] # Tasmania is an island (isolated)
}
csp = MapColoringCSP(regions, initial_domains, adjacencies)
solution = csp.backtrack({})
print("CSP Solution Found via MRV + Forward Checking:")
for region, color in sorted(solution.items()):
print(f" {region:5} : {color}")
Answer: At any point during exploration, BFS must retain the entire boundary of the search tree at depth d in its FIFO queue, requiring O(b^d) storage. In contrast, DFS only maintains the current path from the root down to the active leaf node, along with the unexpanded sibling nodes at each depth level along that single branch. The maximum memory consumed by DFS is therefore b * m nodes (where b is the branching factor and m is the maximum tree depth), which is purely linear.
Answer: In an exponential search tree, the number of nodes at bottom levels completely dominates the sum of all higher levels. Specifically, the bottom level contains approximately b^d nodes, while all higher levels combined contain b^d / (b - 1). When b = 10, re-generating earlier levels in IDS introduces an overhead of only ~11%. In return for this tiny 11% time overhead, IDS provides the linear space complexity of DFS (O(b * d)) while retaining the completeness and optimality of BFS. BFS typically crashes modern systems by running out of memory at depth 10, whereas IDS executes smoothly within megabytes of RAM.
Answer: In graphs with varying edge costs, the first path that reaches a goal node is not necessarily the cheapest. A node might be generated via a high-cost edge while an alternate, optimal route is still queued with lower accumulated cost. By postponing the goal test until a node is popped for expansion, the priority queue mathematically guarantees that all nodes with smaller path costs have already been evaluated and no cheaper path to that goal can exist.
Answer: An admissible heuristic never overestimates the true cost to the goal (0 <= h(n) <= h*(n)). A consistent heuristic enforces the triangle inequality: for every node n and successor n', h(n) <= StepCost(n, a, n') + h(n').
Every consistent heuristic is admissible, but an admissible heuristic is not necessarily consistent. Inconsistency occurs when a parent has a high admissible estimate, but moving to an adjacent node causes the heuristic estimate to drop precipitously by more than the edge cost. In tree search, admissibility alone suffices for optimality. In graph search, consistency is required to guarantee that when a state is first expanded, its path cost is strictly minimal.
Answer: When simulated annealing evaluates a neighbor state that degrades fitness (Delta E < 0), instead of immediately rejecting it like hill climbing, it accepts it with probability P = e^(Delta E / T).
The parameter Temperature T controls the degree of exploration: at high T, Delta E / T is close to zero, making P close to 1 (accepting almost all moves and wandering freely to escape deep local basins). As T gradually cools according to the annealing schedule, P approaches 0 for negative moves, causing the algorithm to smoothly converge into pure greedy hill climbing to lock onto the global optimum.
Answer: Forward Checking only looks one step ahead: whenever a variable X is assigned, it removes inconsistent values from the domains of immediate unassigned neighbors of X. However, it does not propagate constraints between unassigned neighbors.
Arc Consistency (AC-3) performs comprehensive multi-hop constraint propagation. If pruning a value from X causes neighbor Y's domain to shrink, AC-3 adds all arcs leading into Y back into its priority queue to verify whether Y's shrunk domain now renders other variables inconsistent. AC-3 catches domain wipeouts and contradictions far earlier in the search tree than forward checking.
Answer: MRV (Minimum Remaining Values) selects the variable with the smallest legal domain. It is called "fail-first" because if a variable has few options (or is destined to fail), testing it immediately causes an early failure and prunes large subtrees near the top of the search tree. Once a variable is chosen, LCV (Least Constraining Value) selects the value that eliminates the fewest choices for neighboring unassigned variables. It is called "fail-last" because we want to uncover a valid solution on the very first try without backtracking.