Breadth-First Search (BFS)
Expands the shallowest unexpanded node first using a FIFO queue.
- Complete? Yes.
- Optimal? Yes, if costs are identical.
- Complexity: Time/Space .
About 1679 wordsAbout 21 min
2025-08-03
An intelligent agent solves problems by moving from an initial state to a desired goal state. This process is formalized into a structured sequence.
Formulate Goal The agent first defines what it wants to achieve—the goal state.
Formulate Problem Next, it formalizes the problem, defining states and the actions that transition between them.
Search The agent explores sequences of actions to find a path (a solution) from the initial state to the goal.
Execute Finally, it carries out the actions in the found solution.
A problem is formally defined with the following components:
StatesRequiredWorld configurations
The set of all possible configurations, including the initial state and one or more goal states.
ActionsRequiredOperators
The set of actions available in a given state, denoted as ACTIONS(s).
Transition ModelRequired`RESULTS(s, a)`
A function describing the state that results from performing action a in state s.
Action CostOptional`c(s, a, s')`
The cost of performing action a to go from state s to s'.
Goal TestRequiredConstraint
A function to determine if a given state is a goal state.
In(Arad)Is In(Bucharest)?Go(city), e.g., Go(Sibiu).RESULT(In(Arad), Go(Sibiu)) -> In(Sibiu).The core difference between tree and graph search lies in how they handle repeated states.
Tree search explores the state space without remembering past states. It builds a search tree, adding successors of expanded nodes to a frontier.
import collections
# A Node class is used to build the search tree
class Node:
"""A node in a search tree. Contains a pointer to the parent and the state,
the action that led to this state, and the total path cost."""
def __init__(self, state, parent=None, action=None, path_cost=0):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
def tree_search(problem, frontier):
"""
A generic implementation of the Tree Search algorithm.
It does NOT include an 'explored' set.
"""
frontier.append(Node(problem.initial))
while frontier:
node = frontier.popleft() # Using popleft for FIFO behavior (BFS)
if problem.is_goal(node.state):
return node # Return the goal node to reconstruct the path
for action in problem.get_actions(node.state):
child_state = problem.get_result(node.state, action)
child_node = Node(
state=child_state,
parent=node,
action=action
)
frontier.append(child_node)
return None # Return None if no solution is foundGraph search improves on tree search by keeping track of visited states in an explored set.
import collections
class Node:
"""A node in a search tree. Contains a pointer to the parent and the state.
Also includes the action that led to this state and the total path cost."""
def __init__(self, state, parent=None, action=None, path_cost=0):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
def __repr__(self):
return f"<Node {self.state}>"
def __eq__(self, other):
return isinstance(other, Node) and self.state == other.state
def __hash__(self):
return hash(self.state)
def graph_search(problem, frontier):
"""
Searches for a solution using the Graph Search algorithm.
"""
frontier.append(Node(problem.initial_state))
explored = set()
while frontier:
node = frontier.popleft() # For BFS, pop from the left (FIFO)
if problem.is_goal(node.state):
solution_path = []
while node.parent is not None:
solution_path.append(node.action)
node = node.parent
return solution_path[::-1]
explored.add(node.state)
for action in problem.get_actions(node.state):
child_state = problem.get_result(node.state, action)
child_node = Node(child_state, node, action, node.path_cost + 1)
if child_state not in explored and child_node not in frontier:
frontier.append(child_node)
return NoneUninformed search strategies explore the state space without any knowledge of how close a state is to the goal.
Breadth-First Search (BFS)
Expands the shallowest unexpanded node first using a FIFO queue.
Uniform-Cost Search (UCS)
Expands the node with the lowest path cost (g(n)) using a priority queue.
Depth-First Search (DFS)
Expands the deepest unexpanded node first using a LIFO stack.
Depth-Limited Search (DLS)
A DFS with a depth limit L. Solves the infinite loop problem but is incomplete if the solution is deeper than L.
Iterative Deepening Search (IDS)
Combines BFS and DFS benefits by running DLS with increasing depth limits.
| Criterion | Breadth-First | Uniform-Cost | Depth-First | Depth-Limited | Iterative Deepening |
|---|---|---|---|---|---|
| Complete? | Yes | Yes | No | No | Yes |
| Optimal? | Yes (costs equal) | Yes | No | No | Yes (costs equal) |
| Time | O(bd) | O(b1+⌊C∗/ϵ⌋) | O(bm) | O(bL) | O(bd) |
| Space | O(bd) | O(b1+⌊C∗/ϵ⌋) | O(bm) | O(bL) | O(bd) |
b: branching factord: depth of shallowest solutionm: max depthL: depth limitC*: optimal costThis diagram illustrates how the components interact in graph search.
Uniform-Cost Search (UCS) is an uninformed search algorithm that finds the least-cost path from a start to a goal state. Unlike Breadth-First Search, which expands the shallowest node, UCS expands the node with the lowest path cost (g(n)). This is achieved by using a priority queue for the frontier.
This Python function implements the UCS algorithm. It uses a priority queue (implemented with Python's heapq module) for the frontier to ensure the node with the lowest path cost is always selected for expansion. It also uses an explored dictionary to store the lowest cost found so far to reach each state, allowing it to update paths if a cheaper one is discovered.
import heapq
def uniform_cost_search(problem):
"""
Implements Uniform-Cost Search using a priority queue for the frontier.
Finds the path with the minimum total cost.
"""
# The start node has a path cost of 0.
node = Node(problem.initial, path_cost=0)
# The frontier is a priority queue, ordered by path cost.
# We store tuples of (cost, node) to allow the heap to sort correctly.
frontier = [(node.path_cost, node)]
# The explored set is a dictionary mapping a state to its lowest found path cost.
explored = {problem.initial: 0}
while frontier:
# Pop the node with the lowest cost from the priority queue.
cost, node = heapq.heappop(frontier)
# If the goal is reached, reconstruct and return the solution.
if problem.is_goal(node.state):
solution_path = []
while node.parent is not None:
solution_path.append(node.state)
node = node.parent
solution_path.append(node.state)
return solution_path[::-1], cost
# Expand the node.
for action in problem.get_actions(node.state):
child_state = problem.get_result(node.state, action)
# Calculate the new path cost to reach the child.
new_cost = cost + problem.action_cost(node.state, action, child_state)
# If the child hasn't been explored, or we've found a cheaper path to it,
# add it to the frontier and update the explored set.
if child_state not in explored or new_cost < explored[child_state]:
explored[child_state] = new_cost
child_node = Node(child_state, node, action, new_cost)
heapq.heappush(frontier, (new_cost, child_node))
return None, 0 # Return None if no solution is foundNode Class ModificationFor Python's heapq to function as a priority queue with custom objects like our Node, the class needs a method to compare two objects. We add the __lt__ (less than) method, which compares nodes based on their path_cost.
class Node:
"""A node in a search tree, modified for use in a priority queue."""
def __init__(self, state, parent=None, action=None, path_cost=0):
self.state = state
self.parent = parent
self.action = action
self.path_cost = path_cost
def __repr__(self):
return f"<Node {self.state}>"
# Add a less-than method for the priority queue (heapq)
def __lt__(self, other):
return self.path_cost < other.path_costThis graph shows the components of the UCS implementation. It highlights the use of a Priority Queue for the frontier, which is ordered by Path Cost, and an Explored Set that also stores costs to handle path updates.
87c17-web-deploy(Auto): Update base URL for web-pages branchon Copyright Ownership:WARREN Y.F. LONG
License under:Attribution-NonCommercial-NoDerivatives 4.0 International (CC-BY-NC-ND-4.0)