Introduction to Search
1
Ms. Richa Singh
CSE(AI)
CONTENTS
Basic
Search Terminologies
Properties of Search Algorithms
Types of Search Algorithms
Informed Search vs. Uninformed Search
2
BASIC
Searching is a step by step procedure to
solve a search-problem in a given search
space.
A search problem can have three main
factors:
Search Space: Search space represents a set
of possible solutions, which a system may have.
Start State: It is a state from where agent
begins the search.
Goal Test: It is a function which observe the
current state and returns whether the goal3
state is achieved or not.
CONTI…
Other factors are
Search tree: A tree representation of
search problem is called Search tree. The
root of the search tree is the root node
which is corresponding to the initial state.
Actions: It gives the description of all the
available actions to the agent.
Transition model: A description of what
each action do, can be represented as a4
transition model.
CONTI…
PathCost: It is a function which assigns
a numeric cost to each path.
Solution:It is an action sequence which
leads from the start node to the goal
node.
Optimal Solution: If a solution has the
lowest cost among all solutions.
5
SEARCH TERMINOLOGIES
Problem Space − It is the environment in
which the search takes place. (A set of
states and set of operators to change those
states)
Problem Instance − It is Initial state +
Goal state.
Problem Space Graph − It represents
problem state. States are shown by nodes
and operators are shown by edges.
Depth of a problem − Length of a
shortest path or shortest sequence of6
operators from Initial State to goal state.
CONTI…
Space Complexity − The maximum number
of nodes that are stored in memory.
Time Complexity − The maximum number
of nodes that are created.
Admissibility − A property of an algorithm
to always find an optimal solution.
Branching Factor − The average number of
child nodes in the problem space graph.
Depth − Length of the shortest path from
initial state to goal state.
7
PROPERTIES OF SEARCH
ALGORITHMS
Following are the four essential properties
of search algorithms to compare the
efficiency of these algorithms
Completeness
Optimality
Time Complexity
Space Complexity
8
CONTI…
Completeness: A search algorithm is
said to be complete if it guarantees to
return a solution if at least any solution
exists for any random input.
Optimality: If a solution found for an
algorithm is guaranteed to be the best
solution (lowest path cost) among all
other solutions, then such a solution for is
said to be an optimal solution.
9
CONTI…
TimeComplexity: Time complexity is a
measure of time for an algorithm to
complete its task.
Space Complexity: It is the maximum
storage space required at any point
during the search, as the complexity of
the problem.
10
TYPES OF SEARCH ALGORITHMS
Fundamental search algorithms, divided
into two categories, as
11
INFORMED SEARCH VS. UNINFORMED
SEARCH
INFORMED SEARCH UNINFORMED SEARCH
It uses knowledge for the searching It doesn’t use knowledge for searching
process. process.
It finds solution slow as compared to
It finds solution more quickly.
informed search.
It is highly efficient. It is mandatory efficient.
Cost is low. Cost is high.
It consumes less time. It consumes moderate time.
It provides the direction regarding the No suggestion is given regarding the
solution. solution in it.
It is less lengthy while
It is more lengthy while implementation.
implementation.
Greedy Search, A* Search, Graph 12
Depth First Search, Breadth First Search
Search
THANKS
13
