Informed (Heuristic)
Search Strategies
Lec#4
• Heuristic Search: Tries to optimize a problem using heuristic
function.
• Optimization: Tries to solve a problem in minimum number of steps or cost.
• Heuristic Function: It is a function H(n), that given as estimation on
the cost of getting from node ‘n’ to the GOAL state.
• ADVANTAGE: It helps in selecting optimal node for expansion.
• Consider every cost for reaching goal state.
Working of Heuristic Search Algorithm:
• It expands nodes based on their heuristic value h(n).
• It maintains two lists, OPEN and CLOSED list.
• In the CLOSED list, it places those nodes which have already expanded and
• in the OPEN list, it places nodes which have yet not been expanded.
• On each iteration, each node n with the lowest heuristic value is
expanded and generates all its successors and n is placed to the
closed list.
• The algorithm continues unit a goal state is found.
Types of Heuristic approaches
Admissible Non-admissible
• Never overestimates the cost of • Overestimate the path cost
reaching the goal.
h(n) > h*(n)
h(n) <= h*(n)
• Here h(n) is heuristic cost, and h*(n)
• Hence heuristic cost should be
is the estimated cost. Hence heuristic greater than estimated cost.
cost should be less than or equal to the
estimated cost.
• It underestimates the path cost.
Best First Search
• Category of Informed or Heuristic Algorithm:
Search
• Tries to expand the node that is
closest to the goal which leads to a
solution quickly.
• Thus, it evaluates nodes by using
just the heuristic function; that is,
f(n) = h(n)
• Also called Greedy Best First Search
Algorithm
• Here, Straight Line distance method is used by
Best first search to reach A to G.
• These values are already provided since you
cannot determine it here from figure in x-y
coordinate system.
• These distances are considered as heuristic
values.
• A to B = cost 11. It is not a heuristic values
• We will only consider heuristic values in Best first
search
1. B,C and D are connected to A
7. Final Path
2. B, C and D takes A to the goal state with
A to C to F to G
Heuristic values of? 7. In uninformed searches, we explored all
branch nodes like from A to BCD.
• But in Informed, direct from A to C.
8. Hence time complexity and space
3. New queue ACBD is generated complexity issues were present in
uninformed searches.
9. Performs much better than uninformed
searches.
4. F has minimum cost, so it is explored
A* search: Minimizing the total estimated
solution cost
• Category of Informed or Heuristic Search • A∗ search is both complete and
• The most widely known form of best-first optimal.
search is called A∗ search (pronounced “A- • The algorithm is identical to
star search”). UNIFORM-COST-SEARCH except
• It evaluates nodes by combining g(n), the that A∗ uses g + h instead of g
cost to reach the node, and h(n), the cost
to get from the node to the goal:
f(n) = g(n) + h(n)
• Since g(n) gives the path cost from the
start node to node n, and h(n) is the
estimated cost of the cheapest path from n
to the goal, we have
f(n) = estimated cost of cheapest solution through n
Example.
Start from A and have to go to J.
Step-01:
We start with node A.
• Node B and Node F can be reached from node A.
• A* Algorithm calculates f(B) and f(F).
• f(B) = 6 + 8 = 14
• f(F) = 3 + 6 = 9
• Since f(F) < f(B), so it decides to go to node F.
Path- A → F
Step-02:
Node G and Node H can be reached from node F.
• A* Algorithm calculates f(G) and f(H).
• f(G) = (3+1) + 5 = 9
• f(H) = (3+7) + 3 = 13.
• Since f(G) < f(H), so it decides to go to node G.
Path- A → F → G
Step-03:
• Node I can be reached from node G.
• A* Algorithm calculates f(I).
• f(I) = (3+1+3) + 1 = 8
• It decides to go to node I.
Path- A → F → G → I
Step-04:
• Node E, Node H and Node J can be reached from node I.
• A* Algorithm calculates f(E), f(H) and f(J).
• f(E) = (3+1+3+5) + 3 = 15
• f(H) = (3+1+3+2) + 3 = 12
• f(J) = (3+1+3+3) + 0 = 10
• Since f(J) is least, so it decides to go to node J.
Path- A → F → G → I → J
• This is the required shortest path from node A to node J
Assignment
Write a short note on
1. Iterative Deepening A* Search
2. Recursive best-first search (RBFS)
3. backed-up value
