Problem Solving by Searching: Search Algorithms & State Spaces

Key Concepts and Definitions

Problem Solving by Searching

Problem solving by searching involves finding a sequence of actions (a solution path) that transforms an initial state into a goal state. It is a fundamental approach in AI where the problem is represented as a state space—a set of states connected by operators (actions).

State Space

A state space is a graph where:

• Nodes represent states of the problem.
• Edges represent transitions between states via operators.

graph TD
    A["Initial State"] --> B["State 1"]
    B --> C["State 2"]
    C --> D["Goal State"]
    B --> E["State 3"]
    E --> F["State 4"]
    F --> D

Example: In the 8-puzzle, each state is a configuration of tiles, and operators are valid moves (up, down, left, right).

Search Algorithms

1. Uninformed (Blind) Search

These algorithms explore the state space without any additional information (heuristics). They are complete (guaranteed to find a solution if one exists) but may be inefficient.

a) Breadth-First Search (BFS)

• Explores all nodes at the present depth before moving deeper.
• Uses a queue to manage nodes.
• Time Complexity: $O(b^d)$ (where $b$ = branching factor, $d$ = depth of solution).
• Space Complexity: $O(b^d)$.

graph TD
    A["Start"] --> B["Level 1"]
    A --> C["Level 1"]
    B --> D["Level 2"]
    B --> E["Level 2"]
    C --> F["Level 2"]
    D --> G["Goal"]

Worked Example: Finding the shortest path in Kathmandu traffic

• Initial State: Home (Thapathali).
• Goal State: TU Campus (Kirtipur).
• Operators: Walk, bus, taxi (each with different costs).
• BFS explores all possible routes level by level until it finds the shortest path.

b) Depth-First Search (DFS)

• Explores as far as possible along a branch before backtracking.
• Uses a stack (LIFO).
• Time Complexity: $O(b^m)$ (where $m$ = maximum depth of search tree).
• Space Complexity: $O(bm)$.

graph TD
    A["Start"] --> B["Path 1"]
    B --> C["Path 1.1"]
    C --> D["Path 1.1.1"]
    D --> E["Goal"]
    B --> F["Path 1.2"]

Disadvantage: May get stuck in infinite loops if no depth limit is set.

c) Uniform Cost Search (UCS)

• A modified BFS that explores the least-cost path first.
• Uses a priority queue (min-heap) based on path cost.
• Optimal for problems with non-negative edge costs.

Worked Example: Pathao’s optimal route planning

• Initial State: User’s location.
• Goal State: Destination.
• Cost: Distance + traffic congestion.
• UCS finds the cheapest path by always expanding the least-cost node first.

2. Informed (Heuristic) Search

Uses heuristics (problem-specific knowledge) to guide the search toward the goal. Faster than uninformed search but may not always find the optimal solution.

a) Greedy Best-First Search (GBFS)

• Expands the node that appears closest to the goal (using a heuristic $h(n)$).
• Not guaranteed to be optimal (may take a longer path).
• Time Complexity: $O(b^d)$ (worst case).

graph TD
    A["Start"] --> B["Node 1 (h=5)"]
    A --> C["Node 2 (h=2)"]
    C --> D["Node 3 (h=1)"]
    D --> E["Goal"]

Worked Example: Google Maps navigation

• Uses heuristics like straight-line distance to prioritize routes.
• May not always be the shortest (e.g., avoids tolls but takes a longer scenic route).

b) A Search*

• Combines cost-so-far ($g(n)$) and heuristic estimate ($h(n)$) to compute $f(n)=g(n)+h(n)$.
• Optimal if $h(n)$ is admissible (never overestimates the true cost).
• Time Complexity: $O(b^d)$ (with an efficient heuristic).

graph TD
    A["Start (f=0)"] --> B["Node 1 (f=3)"]
    A --> C["Node 2 (f=2)"]
    C --> D["Node 3 (f=4)"]
    D --> E["Goal (f=5)"]

Worked Example: WhatsApp’s message delivery optimization

• $g(n)$: Number of hops so far.
• $h(n)$: Estimated remaining hops to destination server.
• A* ensures the fastest path with minimal retries.

Comparison of Search Algorithms

Real-World Applications

1. E-Sewa & NTC Service Optimization

• Problem: Citizens need to book appointments or check service statuses.
• Search Used: A* to find the fastest server with minimal latency.
• Heuristic: Estimated wait time based on server load history.

2. Daraz’s Order Fulfillment

• Problem: Delivering orders from warehouses to customers.
• Search Used: UCS to find the cheapest route considering fuel cost, traffic, and delivery time.
• Cost Function: Distance + time + fuel expense.

3. Pathao’s Ride Matching

• Problem: Matching drivers to passengers efficiently.
• Search Used: Greedy Best-First Search to assign the nearest available driver.
• Heuristic: Euclidean distance between driver and passenger.

4. NEPSE Stock Trading Bots

• Problem: Predicting stock movements for automated trading.
• Search Used: DFS with backtracking to explore possible trade sequences.
• State Space: Different stock prices and market conditions.

Exam Tip

1. Understand the difference between uninformed and informed search.
2. Memorize time/space complexities of BFS, DFS, UCS, GBFS, and A*.
3. Practice tracing search trees for small problems (e.g., 8-puzzle, grid pathfinding).
4. Explain heuristics clearly—what makes a heuristic admissible or consistent?
5. Relate to real-world examples (e.g., Google Maps uses A*, Pathao uses UCS).
6. For coding questions, always prioritize efficiency (e.g., use a priority queue for A*).

Final Note: Search algorithms are the backbone of AI problem-solving. Mastering them will help you design efficient systems for route optimization, game playing, and automated decision-making.