06-02-2024
Artificial Intelligence
(BITE308L)
Search Algorithm
2/6/2024
Basics
Dr. Hemalatha S, SCORE, VIT
Dr. S. Hemalatha
School of Computer Science Engineering & Information Systems
VIT, Vellore
Search Algorithm Terminologies
• Searching: a step by step procedure to solve a search-problem in a given
search space
A search problem can have 3 main factors:
2/6/2024
• 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 goal state is achieved or not
Dr. Hemalatha S, SCORE, VIT
1
06-02-2024
Search Algorithm Terminologies
• Search tree: A tree representation of search problem is called Search tree
• Root node - The root of the search tree
• Corresponds to the initial state
• Actions: It gives the description of all the available actions to the agent
2/6/2024
• Transition model: A description of what each action do, can be represented as
a transition model
• Path Cost: 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
Dr. Hemalatha S, SCORE, VIT
Properties of Search Algorithms
• 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
2/6/2024
is said to be an optimal solution.
• Time Complexity: 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.
Dr. Hemalatha S, SCORE, VIT
2
06-02-2024
Types of Search Algorithms
2/6/2024
Dr. Hemalatha S, SCORE, VIT
Uninformed search
• The search strategies have no additional information about states beyond that
provided in the problem definition
• Does not contain any domain knowledge
• Closeness
• Location of the goal
• Search tree is searched without any information about the search space 2/6/2024
• Initial state operators
• Test for the goal
• So, is called blind search
• It includes information about how to
• Traverse the tree &
• Identify leaf and goal nodes
• These search strategies are distinguished by the order in which nodes are
expanded
Dr. Hemalatha S, SCORE, VIT
3
06-02-2024
informed search
• Strategies that know whether one non-goal state is more promising than
another
• Informed search algorithms use domain knowledge
• In an informed search, problem information is available which can
2/6/2024
guide the search
• Informed search strategies can find a solution more efficiently than an
uninformed search strategy
• Also called a Heuristic search
• A heuristic is a way which might not always be guaranteed for best
solutions but guaranteed to find a good solution in reasonable time
Dr. Hemalatha S, SCORE, VIT
Uninformed Search Algorithms
• Breadth-first Search
• Depth-first Search 2/6/2024
• Uniform cost search
• Depth-limited Search
• Iterative deepening depth-first search
• Bidirectional Search
Dr. Hemalatha S, SCORE, VIT
4
06-02-2024
informed Search Algorithms
• Greedy Best-first Search
2/6/2024
• A* Search
Dr. Hemalatha S, SCORE, VIT
