Searching for Solutions in Artificial Intelligence

After problem formulation, the next step in AI is searching for a solution.

A problem may have many possible states and many possible actions. An AI system needs a systematic method to explore these possibilities and find a sequence of actions that takes it from the initial state to the goal state.

1. What is Searching for Solutions?

Definition

Searching for solutions in Artificial Intelligence is the process of exploring a state space to find a sequence of actions that transforms an initial state into a goal state.

In simple words:

Search means trying different possible paths until the AI finds a path from the starting state to the desired goal.

Basic idea

Initial State
     |
     v
Possible Actions
     |
     v
New States
     |
     v
More Possible Actions
     |
     v
Goal State

For example, if an AI has to travel from Ludhiana to Delhi, it can explore different routes:

                 Chandigarh
                /           \
Ludhiana ------              ------ Delhi
                \           /
                 Ambala

The AI searches through possible routes and selects a route according to the objective, such as:

shortest distance
minimum travel time
minimum cost
minimum fuel consumption

2. Search and Problem Solving

AI problem solving generally follows this sequence:

Real-World Problem
        |
        v
Problem Formulation
        |
        v
Initial State
        |
        v
State Space
        |
        v
Search
        |
        v
Solution Path
        |
        v
Goal State

For example:

Problem: Get 2 litres of water using 4L and 3L jugs.

Formulation

Component	Description
Initial state	(0,0)
State	(x,y)
Actions	Fill, empty, pour
Goal	Obtain 2 litres
Search	Explore possible states
Solution	Sequence of operations

3. What is a Search Space?

A state space is the collection of all possible states that can be reached from the initial state by applying valid actions.

For example, consider a simple problem:

Here:

A = initial state
D/E/F = possible goal states
A, B, C, D, E, F = states
Connections = possible actions

The AI must decide which state to explore first.

That decision is determined by the search strategy.

4. Search Tree

A search problem can be represented using a search tree.

Suppose:

             A
           /   \
          B     C
         / \   / \
        D   E F   G

The AI starts at A.

It can explore:

A → B → D

A → B → E

A → C → F

A → C → G

If G is the goal:

A → C → G

is the solution path.

5. Search Node

During search, AI normally maintains information about each node.

A search node can contain:

Node
 ├── State
 ├── Parent
 ├── Action
 ├── Path Cost
 └── Depth

Example

Suppose:

A → B → E

For node E:

Property	Value
State	E
Parent	B
Action	B → E
Depth	2
Path Cost	2, if each action costs 1

The parent information allows the AI to reconstruct the complete solution path after reaching the goal.

6. General Search Process

A general search algorithm works approximately as follows:

1. Start with the initial state
           ↓
2. Put it into the search structure
           ↓
3. Select a state/node
           ↓
4. Check whether it is the goal
           ↓
      Yes ─────→ Solution
       |
       No
       ↓
5. Expand the node
       ↓
6. Generate successor states
       ↓
7. Add successors to search structure
       ↓
8. Select next node
       ↓
9. Repeat

In simple pseudocode

SEARCH(problem):

    initialize search with initial state

    while search is not empty:

        select a node

        if node satisfies goal:
            return solution

        expand node

        add its successors to search

    return failure

The important part is:

How do we select the next node?

Different search algorithms answer this question differently.

7. Classification of Search Strategies

Search strategies can broadly be divided into two categories:

                 Search Strategies
                       |
          ┌────────────┴────────────┐
          |                         |
     Uninformed Search          Informed Search
     (Blind Search)             (Heuristic Search)
          |                         |
   No domain knowledge        Uses heuristic
          |                         |
   BFS, DFS, UCS              Greedy, A*, etc.

8. Uninformed Search

Uninformed search is also called:

Blind Search
Uninformed Search

The algorithm does not have additional knowledge about how close a state is to the goal.

It only knows:

initial state
possible actions
successor states
goal test
path cost, where applicable

Major uninformed search algorithms

Breadth-First Search (BFS)
Depth-First Search (DFS)
Uniform-Cost Search (UCS)
Depth-Limited Search
Iterative Deepening Search

9. Breadth-First Search — BFS

BFS explores nodes level by level.

Example:

             A
           /   \
          B     C
         / \   / \
        D   E F   G

BFS order:

A → B → C → D → E → F → G

It explores:

Level 0:       A

Level 1:      B C

Level 2:    D E F G

Data structure

BFS uses a Queue (FIFO).

First In → First Out

Advantage

If every action has the same cost, BFS can find the shortest solution in terms of number of steps.

Disadvantage

It can require a very large amount of memory.

10. Depth-First Search — DFS

DFS explores one branch as deeply as possible before going back and exploring another branch.

For:

             A
           /   \
          B     C
         / \   / \
        D   E F   G

One possible DFS order is:

A → B → D → E → C → F → G

Data structure

DFS uses a Stack (LIFO).

Last In → First Out

Advantage

Requires less memory than BFS in many cases.
Can reach a deep solution quickly.

Disadvantages

May go down an incorrect/deep branch.
Does not generally guarantee the shortest solution.
Can get stuck in infinite-depth spaces without safeguards.

11. Uniform-Cost Search — UCS

Uniform-Cost Search selects the node having the lowest path cost.

It uses:\[ g(n) \]

where:

g(n) = cost of reaching node n from the initial state.

Suppose:

A --1--> B --5--> D
 \
  2
   \
    C --1--> D

Costs:

A → B → D = 1 + 5 = 6

A → C → D = 2 + 1 = 3

UCS chooses:

A → C → D

because its total cost is 3.

Important

If step costs are positive, UCS is optimal.

12. Informed Search

Informed search uses additional knowledge about the problem.

This additional information is called a:

Heuristic

A heuristic estimates how close a state is to the goal.

It is commonly represented by:\[ h(n) \]

where:

h(n) = estimated cost from node n to the goal.

Examples:

8-Puzzle

Possible heuristic:\[ h(n) = \text{number of misplaced tiles} \]

Another:\[ h(n) = \text{Manhattan distance} \]

Route finding

A heuristic could be:

Straight-line distance to destination

13. Greedy Best-First Search

Greedy Best-First Search selects the node that appears closest to the goal.

It uses:\[ f(n)=h(n) \]

where:

h(n) = estimated distance to goal.

Suppose:

A
├── B   h(B)=8
├── C   h(C)=4
└── D   h(D)=2

Greedy search chooses:

because:\[ h(D)=2 \]

is the smallest.

Advantage

It can be very fast when the heuristic is good.

Disadvantage

It may choose a bad path because it ignores the cost already spent.

14. A* Search

A* is one of the most important search algorithms in AI.

It combines:

actual cost so far
estimated cost to goal

Formula:\[ \boxed{f(n)=g(n)+h(n)} \]

Where:

g(n) = actual cost from initial state to n
h(n) = estimated cost from n to goal
f(n) = estimated total cost of solution through n

Example

Suppose:

Node	g(n)	h(n)	f(n)
A	0	10	10
B	3	5	8
C	2	7	9
D	6	2	8

A* prefers nodes with lower f(n).

15. Search Algorithm Comparison

Algorithm	Knowledge	Main idea	Data structure	Optimal?
BFS	None	Lowest depth first	Queue	Yes, equal costs
DFS	None	Deepest first	Stack	No
UCS	Cost	Lowest path cost	Priority Queue	Yes
Greedy	Heuristic	Closest estimated goal	Priority Queue	No
A*	Cost + heuristic	Lowest `g+h`	Priority Queue	Yes, under suitable conditions
Hill Climbing	Heuristic	Best neighboring state	Local search	No
Simulated Annealing	Heuristic	Sometimes accepts worse states	Local search	No guarantee

16. Search Tree vs State Space

These two terms are often confused.

State Space

Represents all possible states of the problem.

Search Tree

Represents the paths explored by the search algorithm.

For example:

State Space:

       A
      / \
     B   C
    / \   \
   D   E   F

A search algorithm may explore only:

A → B → D

and therefore construct only part of the complete state space.

Important distinction

State space = possible states.

Search tree = exploration of those states by a particular search algorithm.

17. Solution Path

A solution is normally a sequence of actions.

For example:

Initial
   |
 Action 1
   |
 State 1
   |
 Action 2
   |
 State 2
   |
 Action 3
   |
 Goal

We can represent the solution as:\[ S_0 \rightarrow S_1 \rightarrow S_2 \rightarrow S_3 \]

where:

\(S_0\) = initial state
\(S_3\) = goal state

The sequence of actions is called the solution path.

18. What Makes a Good Search Algorithm?

We normally evaluate search algorithms using four important criteria.

1. Completeness

Will the algorithm definitely find a solution if one exists?

2. Optimality

Will it find the best/lowest-cost solution?

3. Time Complexity

How much time does it require?

4. Space Complexity

How much memory does it require?

These are very important for examination questions.

19. Example: Searching in the 8-Puzzle

Consider:

Initial State

1 2 3
4 _ 6
7 5 8

Goal:

1 2 3
4 5 6
7 8 _

Possible actions from the initial state:

        Up
         ↑
         |
Left ←  Blank  → Right
         |
         ↓
        Down

The AI generates possible successor states.

For example, moving the blank down:

1 2 3
4 5 6
7 _ 8

Then move right:

1 2 3
4 5 6
7 8 _

Goal reached.

Therefore:

Initial
   |
 Move Down
   |
 State 1
   |
 Move Right
   |
 Goal

This is an example of searching for a solution.

20. Search in the Water Jug Problem

Initial:

(0,0)

Possible actions generate:

             (0,0)
           /   |   \
          /    |    \
     Fill A  Fill B  ...
        |
      (4,0)
        |
      Pour
        |
      (1,3)
        |
       ...
        |
      (0,2)

The search algorithm explores states until it finds a state containing 2 litres.

Thus:

Problem
   ↓
State Space
   ↓
Search
   ↓
Goal State

21. Search Strategies in the AI Syllabus

Your syllabus first introduces the general concept:

Searching for Solutions

and later covers:

Uninformed search

Breadth-First Search
Depth-First Search
Uniform-Cost Search
Depth-Limited Search
Iterative Deepening

Informed/Heuristic search

Hill Climbing
Simulated Annealing
Greedy Best-First Search
A*
Memory-Bounded Heuristic Search

So, Searching for Solutions is the foundation for understanding all these algorithms.

22. General Search Algorithm — Exam View

A generic search procedure can be written as:

SEARCH(problem)

1. Create initial node from initial state.

2. Put initial node into the frontier.

3. Repeat:
      a. If frontier is empty:
             return FAILURE

      b. Select a node from frontier.

      c. If node is a goal:
             return solution

      d. Expand the node.

      e. Generate successor nodes.

      f. Add successors to frontier.

4. Continue until solution is found.

The frontier is the collection of nodes that have been generated but not yet explored.

Different algorithms use different rules for selecting from the frontier:

BFS       → shallowest node
DFS       → deepest node
UCS       → lowest g(n)
Greedy    → lowest h(n)
A*        → lowest g(n)+h(n)

This is an extremely important concept.

23. Search Tree Terminology

Term	Meaning
State	Current situation
Initial state	Starting situation
Goal state	Desired final situation
Node	Representation of a state in search
Parent	Previous node
Child	Successor node
Root	Initial node
Leaf	Node with no currently generated children
Depth	Number of actions from root
Path	Sequence of nodes
Path cost	Total cost of actions
Frontier	Generated but unexplored nodes
Expansion	Generating successors
Goal test	Checking whether goal is reached

24. Real-World Example: Google Maps

Consider route planning.

Initial State
Ludhiana
     |
     v
Possible Roads
     |
     +---- Chandigarh
     |
     +---- Ambala
     |
     +---- Jalandhar
             |
             v
          Delhi

The system can search for a route based on:

distance
traffic
travel time
tolls
fuel cost

A modern route-planning system can use graph-search techniques and heuristics.

This demonstrates that search is not limited to puzzles.

It can be used in:

navigation
robotics
game playing
scheduling
planning
logistics
network routing
resource allocation

25. Search vs Problem Formulation

This distinction is very important.

Problem Formulation	Searching
Defines the problem	Finds the solution
Defines states	Explores states
Defines actions	Applies actions
Defines goal	Checks goal
Defines cost	Evaluates paths
Answers “What is the problem?”	Answers “How can we solve it?”

Example

Water Jug

Problem formulation:

State = (x,y)
Actions = Fill, Empty, Pour
Goal = 2 litres

Searching:

(0,0)
 ↓
(0,3)
 ↓
(3,0)
 ↓
...
 ↓
(0,2)

26. Key Concept: Exploration vs Exploitation

In search, the AI faces a fundamental challenge:

Should it explore new possibilities or continue with the currently promising path?

For example:

                 Start
                /     \
          promising   unknown
             /           \
           ...           ...

Classical search algorithms systematically explore the search space.

Heuristic and local-search algorithms try to focus computational effort on promising regions.

This becomes especially important in:

large search spaces
optimization
game playing
robotics
machine learning
planning

27. Why Searching is Important in AI

Searching provides a general mechanism for solving problems where the AI must choose among many possibilities.

It enables AI systems to:

find routes
solve puzzles
play games
schedule activities
plan actions
make decisions
optimize solutions
solve constraint problems
navigate environments

The fundamental idea is:\[ \boxed{\text{Initial State} \rightarrow \text{Search} \rightarrow \text{Goal State}} \]

28. Exam-Oriented Definition

Searching for Solutions

Searching for solutions in Artificial Intelligence is the systematic process of exploring the state space of a problem to find a sequence of actions that transforms the initial state into a goal state. Search algorithms determine which states should be explored and in what order. Examples include Breadth-First Search, Depth-First Search, Uniform-Cost Search, Greedy Best-First Search and A Search.*

29. Quick Revision

Remember:

S-A-G-C-S

S → State Space
A → Actions
G → Goal
C → Cost
S → Search

And remember the major search formulas:\[ \boxed{g(n)=\text{cost from start to }n} \]\[ \boxed{h(n)=\text{estimated cost from }n\text{ to goal}} \]\[ \boxed{f(n)=g(n)+h(n)} \]

The last formula is the foundation of A* search.

Complete conceptual flow

                 AI PROBLEM
                     |
                     ↓
              Problem Formulation
                     |
        ┌────────────┼────────────┐
        ↓            ↓            ↓
     States       Actions        Goal
        \            |            /
         \           |           /
          └────── State Space ──┘
                     |
                     ↓
                  SEARCH
                     |
        ┌────────────┴────────────┐
        ↓                         ↓
 Uninformed Search          Informed Search
        ↓                         ↓
 BFS, DFS, UCS             Greedy, A*, etc.
        |                         |
        └────────────┬────────────┘
                     ↓
                 Solution

The next logical topic after this is “Uninformed Search Strategies,” especially BFS, DFS, Uniform-Cost Search, Depth-Limited Search and Iterative Deepening Search.