Scribd
Upload
25 views20 pages

3.informed Searches

The document discusses different search algorithms including heuristic searches, best-first search, and A* search. It provides details on heuristic functions, how best-first search works by combining depth-first and breadth-first searches, and outlines the steps of the A* search algorithm.

Uploaded by

mandeep
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
25 views20 pages

3.informed Searches

The document discusses different search algorithms including heuristic searches, best-first search, and A* search. It provides details on heuristic functions, how best-first search works by combining depth-first and breadth-first searches, and outlines the steps of the A* search algorithm.

Uploaded by

mandeep
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 20

Informed searches – Part 1

TO DO
Heuristics function
• takes the current state of the agent as its
input and produces the estimation of how
close agent is from the goal
• might not always give the best solution, but
guaranteed to find a good solution in
reasonable time
h(n) <= h*(n) 
Here
h(n) is heuristic cost
h*(n) is the estimated cost.

Heuristic cost should be less than or equal to


the estimated cost.
Best-first Search Algorithm (Greedy
Search)
• combination of depth-first search and
breadth-first search algorithms
• f(n)= g(n)
Best first search algorithm
Step 1: Place the starting node into the OPEN list.
Step 2: If the OPEN list is empty, Stop and return failure.
Step 3: Remove the node n, from the OPEN list which has the lowest value of
h(n), and places it in the CLOSED list.
Step 4: Expand the node n, and generate the successors of node n.
Step 5: Check each successor of node n, and find whether any node is a goal
node or not. If any successor node is goal node, then return success and
terminate the search, else proceed to Step 6.
Step 6: For each successor node, algorithm checks for evaluation function
f(n), and then check if the node has been in either OPEN or CLOSED list. If the
node has not been in both list, then add it to the OPEN list.
Step 7: Return to Step 2.
A *search
Tree search
• Exploration of states by generating successors
of already explored states
A* Search Algorithm
• combined features of UCS and greedy best-
first search
Thank you!!

You might also like