AIA (NEP) Edurite College of Management Studies

UNIT- 2
PROBLEM SOLVING BY SEARCHING
1.0 Introduction
The AI problems are solved using the universal technique known as searching. Searching
is a knowledge base solution to reach the goal state. There are many approaches for
searching an exact goal state from all other states.
Many searching algorithms are followed by an agent to solve the problems by searching.
Artificial intelligence is building the agents to perform some kind of search algorithm in
the background to reach the goal.
A search problem consists of:
State space: It is a set of all possible states.
Start state: It is the state where the search begins.
Goal state: It is the state where the searching task looks for.

1.1 Problem-Solving Agents

The problem-solving agents or rational agents in AI are mostly used to search to reach
the goal or to solve the specific problems and provide the best results. Problem solving
agents are the goal-based agents and they use the atomic representation.
Steps performed by problem solving agents.
1. Goal Formulation:
a. It is the simplest and first step in problem solving, where it organizes the
sequence required to formulate one goal from out of many goals as well as
actions to achieve the goal. It is based on the agent’s performance measure
and current situation.
2. Problem Formulation: It is the very important step in problem solving, where it
decides what actions to be taken to achieve the formulated goal. It involves the five
components.
a. Initial State: It is the starting state of the agent towards its goal.
b. Actions: It describes the possible actions available to the agent.

Shadab pasha (Asst. Professor) Dept. of BCA P a g e 1 | 29

 AIA (NEP) Edurite College of Management Studies
c. Transition Model: It describes about each action has been taken.
d. Goal Test: It determines if the given state is a goal state.
e. Path cost: It assigns a quantity cost to each path that follows the goal. The
problem-solving agent selects a cost function. Which also reflects its
performance measure. An optimal solution has the lowest path cost.

1.2 Well-Defined problems and Solutions

➢ Well-defined problems are also called as State-space of a problem. It is a set of all
states which can be traversed from the initial state to goal state followed by any
sequence of actions.
➢ The state space forms a directed graph where nodes are the states, edges are the
actions, and the path is a sequence of states connected by the sequence of actions.
1. Search: It finds all the best possible sequences of actions to reach the goal from
current state. It inputs the problem and gives the solutions.
2. Solution: It finds the best algorithm out of all algorithms, that proven as the best
optimal solution
3. Execution: It executes the best optional solution from the searching algorithm to
reach goal state from the current state.
Example problem
Toy problem: 3x3 matrix with movable tiles numbered from 1 to 8 with a blank space.
The tile adjacent to the black space can slide into that space. The objective is to reach a
specified goal state from current state by sliding digits into the black space.
Solution 1: The problem formulation is as follows:
• States: It specifies the location of each numbered tiles and the blank tile
• Initial State: It is the starting state.
• Actions: It defines the blank space either left, right, up, and down
• Transition Model: It returns the goal state as per the given state and actions.
• Goal test: It identifies whether the correct goal-state is reached or not.
• Path Cost: The path cost is the number of steps.

Shadab pasha (Asst. Professor) Dept. of BCA P a g e 2 | 29

 AIA (NEP) Edurite College of Management Studies
Note: The 8-puzzle problem is a type of sliding-block problem which is used for testing
new search algorithms in artificial intelligence

1.3 Searching for Solutions

➢ It is also known as solution strategy. There are many problems, which is need to
search for solutions to solve them by using the searching technique by the agent.
➢ To solve different problems, the agents make use of different strategies to reach
the goal by searching the best possible algorithms.
Steps involved to build a system to solve a problem:
Step 1: Problem Definition
Step 2: Problem Analyze
Step 3: Solve the problem with help of isolate and represent the task knowledge
Step 4: Choose the best problem-solving techniques and apply it to the particular problem

Search Algorithm Terminologies

Search: Searching solves a search issue in each space step by step. Three major factors
can influence a search issue.
Search Space: A search space is a collection of potential solutions a system may have.
Start State: The jurisdiction where the agent starts the search.
Goal test: A function that examines the current state and returns whether or not the goal
state has been attained.
Search tree: A search tree is a tree representation of a search issue. The node at the root
of the search tree corresponds to the initial condition.
Actions: It describes all the steps, activities, or operations accessible to the agent
Transition model: It can be used to convey a description of what each action does.
Path Cost: It is a function that gives a cost to each path.
Solution: An action sequence connects the start node to the target node
Optimal Solution: If a solution has the lowest cost among all solutions, it is said to be
the optimal answer.

Shadab pasha (Asst. Professor) Dept. of BCA P a g e 3 | 29

 AIA (NEP) Edurite College of Management Studies
1.4 Uninformed Search Strategies
Uninformed search is a general-purpose search algorithms which operates in brute force-
way uninformed search is also called as blind search, since this algorithms do not have
additional information about state or search space other than how to traverse the tree.
The uniformed search algorithm are:
• Breadth-First Search
• Uniform-Cost Search
• Depth-First Search
• Depth-Limited Search
• Iterative Deepening Depth-First Search
• Bidirectional Search
• Greedy Best-First Search
• A* Search
• Ao* Search Informed (Heuristic) Search Strategies
• Heuristic Functions

1.4.1 Breadth-First Search

➢ It is the general-graph search algorithm and most common search strategy for
traversing a tree or graph in breadthwise.
➢ It is implemented using FIFO queue concept. These algorithm starts searching
form the root node of the tree and traverse to the successor node at the each level.

In the given tree structure, the BFS algorithm start from root node S and reach to the goal
node K

Shadab pasha (Asst. Professor) Dept. of BCA P a g e 4 | 29

 AIA (NEP) Edurite College of Management Studies
From S to K by traversing all the successors nodes
S→A→B→C→D→G→H→E→F→I→K
Time Complexity: BFS algorithm time complexity is generated by the number of nodes
traversed in BFS until the goal state.
T(b) = 1 + b2 + b3 . . . + bd = O(bd)
Where the d = depth of shallowest solution and b is a node at every state.
Space Complexity: BFS algorithm space complexity is given by the Memory size of
frontier which is O(bd)
Completeness: BFS is complete, which means if the shallowest goal node is at some
finite depth, the BFS will find a solutions
Optimality: BFS is optimal if path cost is a non-decreasing function of the depth of the
node.
Advantages:
➢ It will provide a solution if any solution exists
➢ It provide the minimal solution which requires the least number of steps
Disadvantages:
➢ It requires more memory
➢ It consume more time if the goal node is far away from the root node

1.4.2 Uniform-Cost Search

➢ Uniform-cost search is a searching algorithm that is used for traversing a weighted
tree or graph.
➢ This algorithm comes into play when each edge as a different cost. The main goal
of this algorithm is to find a path from root node to the goal node with lowest cost
with optimal.
➢ To find a path to the goal node which has the lowest cumulative cost. It is
implemented by the priority queue where it gives maximum priority to the lowest
cumulative cost. Uniform cost search is equivalent to BFS algorithm if the path
cost of all edges is the same.

Shadab pasha (Asst. Professor) Dept. of BCA P a g e 5 | 29

 AIA (NEP) Edurite College of Management Studies

From root node S to goal node G, the traversing choose the nodes of low weightage
S→A→D→G

Completeness: Uniform-Cost search is complete, such as if there is a solutions. UCS

will find it
Time Complexity: Best Time Complexity of UCS is C*/e+1. Where C* is cost of
optimal solution. The Worst-case tie complexity of Uniform-cost search is O(b1+[C*/e])

Space Complexity: The worst-case space complexity of Uniform-cost search is

O(b1+[C*/e])

Optimal: Uniform-cost search is always optimal as it only selects a path with the lowest
path cost

Advantages: UCS is optimal because it use least cost at every state

Disadvantages: It is stuck in an infinite loop since it has more number of steps which is
involved in searching

1.4.3 Depth-First Search

Depth-First Search is a recursive algorithm for traversing a tree or graph. IT starts from
the toot node and follows each path to its greatest depth node before moving to the next
path. It uses a stack data structure for implementation. Its processing is similar to the
BFS algorithm.

In the above search tree, the DFS will follow the order as:

Root node → Left node → Right node

Shadab pasha (Asst. Professor) Dept. of BCA P a g e 6 | 29

 AIA (NEP) Edurite College of Management Studies
It will start searching from root node S, and traverse A, then B, then D and E, after
traversing E, it will backtrack the tree as E has no other successor and still goal node is
not found. After backtracking it will traverse node C and then G, and here it will
terminate as it found goal node.

S→A→B→D→E→C→G

Completeness: DFS search algorithm is complete within finite state space as it will
expand every node within a limited search tree
Time Complexity: Time complexity of DFS is O(nm) which is equivalent to the node
traversed by the algorithm. it is given by

T(n) = 1 + n2 + n3 … + nm = O(nm)

Where m = maximum depth of any node

Space Complexity: Space complexity of DFS algorithm is O(bm) which is equivalent to
the size of the fringe set

Optimal: DFS algorithm is non-optimal as it may generate a large number of steps or

high cost to reach to the goal node.

Advantage:
➢ It requires very less memory

➢ It takes less time to traverse from root node to goal node

Disadvantages:
➢ Sometimes there is no guarantee of finding the solution

➢ It goes for deep down searching and sometime it may go to the infinite loop

Shadab pasha (Asst. Professor) Dept. of BCA P a g e 7 | 29