Unit 2 L2
Unit 2 L2
Unit 2 L2
Noida
Unit: 02
Introduction to Search
August 4, 2024 7
Continue…
Advantages:
• Best first search can switch between BFS and DFS by
gaining the advantages of both the algorithms.
• This algorithm is more efficient than BFS and DFS
algorithms.
Disadvantages:
• It can behave as an unguided depth-first search in
the worst case scenario.
• It can get stuck in a loop as DFS.
• This algorithm is not optimal.
August 4, 2024 8
Continue…
Example:
• Consider the below search problem, and we will
traverse it using greedy best-first search. At each
iteration, each node is expanded using evaluation
function f(n)=h(n) , which is given in the below table.
August 4, 2024 9
Continue…
August 4, 2024 10
Continue…
August 4, 2024 11
Continue…
August 4, 2024 12
Continue…
August 4, 2024 13
Continue…
• Time Complexity: The worst case time complexity of
Greedy best first search is O(bm).
• Space Complexity: The worst case space complexity
of Greedy best first search is O(bm). Where, m is the
maximum depth of the search space.
• Complete: Greedy best-first search is also
incomplete, even if the given state space is finite.
• Optimal: Greedy best first search algorithm is not
optimal.
August 4, 2024 14
A* Search Algorithm
August 4, 2024 16
Continue…
August 4, 2024 17
Continue…
Algorithm of A* search:
• Step1: Place the starting node in the OPEN list.
August 4, 2024 18
Continue…
• Step 4: Expand node n and generate all of its successors, and
put n into the closed list. For each successor n', check whether
n' is already in the OPEN or CLOSED list, if not then compute
evaluation function for n' and place into Open list.
• Step 5: Else if node n' is already in OPEN and CLOSED, then it
should be attached to the back pointer which reflects the
lowest g(n') value.
• Step 6: Return to Step 2.
August 4, 2024 19
Continue…
Advantages:
• A* search algorithm is the best algorithm than other
search algorithms.
• A* search algorithm is optimal and complete.
August 4, 2024 20
Continue…
Disadvantages:
• It does not always produce the shortest path as it
mostly based on heuristics and approximation.
• A* search algorithm has some complexity issues.
August 4, 2024 21
Continue…
Example:
• In this example, we will traverse the given graph
using the A* algorithm. The heuristic value of all
states is given in the below table so we will calculate
the f(n) of each state using the formula f(n)= g(n) +
h(n), where g(n) is the cost to reach any node from
start state.
• Here we will use OPEN and CLOSED list.
August 4, 2024 22
Continue…
Problem:
August 4, 2024 23
Continue…
Solution:
August 4, 2024 24
Continue…
• Initialization: {(S, 5)}
• Iteration1: {(S--> A, 4), (S-->G, 10)}
• Iteration2: {(S--> A-->C, 4), (S--> A-->B, 7), (S--
>G, 10)}
• Iteration3: {(S--> A-->C--->G, 6), (S--> A-->C--->D,
11), (S--> A-->B, 7), (S-->G, 10)}
• Iteration 4 will give the final result, as S--->A---
>C--->G it provides the optimal path with cost 6.
August 4, 2024 25
Continue…
Points to remember:
• A* algorithm returns the path which occurred first,
and it does not search for all remaining paths.
• The efficiency of A* algorithm depends on the quality
of heuristic.
• A* algorithm expands all nodes which satisfy the
condition f(n).
August 4, 2024 26
Continue…
Complete: A* algorithm is complete as long as:
Branching factor is finite.
Cost at every action is fixed.
Time Complexity: The time complexity of A* search algorithm
depends on heuristic function, and the number of nodes
expanded is exponential to the depth of solution d. So the
time complexity is O(b^d), where b is the branching factor.
Space Complexity: The space complexity of A* search
algorithm is O(b^d)
August 4, 2024 27
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 more lengthy while
It is less lengthy while implementation.
implementation.
Greedy Search, A* Search, Graph Depth First Search, Breadth First
Search Search
08/04/24 28
Generate and Test algorithm
August 4, 2024 29
MCQ
August 4, 2024 30
MCQ
• Q2. Which search uses the problem specific
knowledge beyond the definition of the problem?
a) Informed search
b) Depth-first search
c) Breadth-first search
d) Uninformed search
• Answer: a
• Informed search can solve the problem beyond the
function definition, So does it can find the solution
more efficiently.
August 4, 2024 31
MCQ
August 4, 2024 32
MCQ
August 4, 2024 33
MCQ
August 4, 2024 34
MCQ
• Q6. Which search method will expand the node that is closest to the goal?
a) Best-first search
b) Greedy best-first search
c) A* search
d) None of the mentioned
• Answer: b
August 4, 2024 35
MCQ
• Q7. A heuristic is a way of trying ___________
a) To discover something or an idea embedded in a program
b) To search and measure how far a node in a search tree seems to be
from a goal
c) To compare two nodes in a search tree to see if one is better than
another
d) All of the mentioned
• Answer: d
August 4, 2024 36
MCQ
August 4, 2024 37
MCQ
• Q9. The search strategy the uses a problem specific knowledge is
known as ___________
a) Informed Search
b) Best First Search
c) Heuristic Search
d) All of the mentioned
• Answer: d
August 4, 2024 38
MCQ
August 4, 2024 39
MCQ
• Q11. Best-First search is a type of informed search, which
uses _____ to choose the best next node for expansion.
a) Evaluation function returning lowest evaluation
b) Evaluation function returning highest evaluation
c) Evaluation function returning lowest & highest evaluation
d) None of them is applicable
• Answer: a
August 4, 2024 40
MCQ
• Q12. Best-First search can be implemented using the
following data structure.
a) Queue
b) Stack
c) Priority Queue
d) Circular Queue
• Answer: c
August 4, 2024 41
MCQ
• Q13. Heuristic function h(n) is ________
a) Lowest path cost
b) Cheapest path from root to goal node
c) Estimated cost of cheapest path from root to goal node
d) Average path cost
• Answer: c
August 4, 2024 42
MCQ
• Q14 . Greedy search strategy chooses the node for
expansion in ___________
a) Shallowest
b) Deepest
c) The one closest to the goal node
d) Minimum heuristic cost
• Answer: c
August 4, 2024 43
MCQ
• Q15. What is the space complexity of Greedy search?
a) O(b)
b) O(bl)
c) O(m)
d) O(bm)
• Answer: d
August 4, 2024 44
MCQ
• Q16. What is the evaluation function in greedy
approach?
a) Heuristic function
b) Path cost from start node to current node
c) Path cost from start node to current node + Heuristic
cost
d) Average of Path cost from start node to current node
and Heuristic cost
• Answer: a
August 4, 2024 45
MCQ
Q 17. What is the evaluation function in A* approach.
a) Heuristic function
Answer: c
August 4, 2024 46
References