Unit-1
[Link],
[Link],
CSED,MVSREC.
Problem Solving & Search
Search Strategies
➢ Informed Search Strategies: BFS
➢ A* Algorithm
➢ Heuristic Functions.
➢ Iterative Deepening A*
Using problem specific knowledge to aid
searching
Search everywhere!!
➢ Without incorporating knowledge into
searching, one is forced to look everywhere to
find the answer.
➢ Hence, the complexity of uninformed search is
intractable.
➢ With knowledge, one can search the state Search only in this subtree!!
space as if given “hints”: Heuristic information
in search = Hints
➢ Leads to dramatic speed up in efficiency.
Informed Search
➢ Informed searches use domain knowledge
to guide selection of the best path to continue searching
➢ Heuristics are used, which are informed guesses
➢ Heuristic means "serving to aid discovery"
Heuristic function, h(n)
➢ A heuristic function is a function h(n) that gives an estimation on the “cost” of
getting from node n to the goal state – so that the node with the least cost
among all possible choices can be selected for expansion first.
➢ A heuristic function, h(n)
➢ uses domain-specific information in some way
➢ is (easily) computable from the current state description
➢ estimates
➢ the "goodness" of node n
➢ how close node n is to a goal
➢ the cost of minimum cost path from node n to a goal state
Heuristic function, h(n)
➢ h(n) ≥ 0 for all nodes n
➢ h(n) close to 0 means we think n is close to a goal state
➢ h(n) very big means we think n is far from a goal state
➢ All domain knowledge used in the search is encoded in the heuristic
function, h
Best-First Search
➢ Sort nodes in the Frontier list by increasing values of an evaluation function,
f(n), that incorporates domain-specific information
➢ This is a generic way of referring to the class of informed search methods
➢Types of best-first search include:
➢ Greedy best-first search
➢ A*
Evaluation Functions
➢ In informed search algorithms, the evaluation
function (f(n)) is used to determine the most
promising node to explore next by incorporating
problem-specific knowledge. It helps in guiding
the search process efficiently toward the goal
state.
➢ A general form of the evaluation function is:
f(n) = g(n) + h(n)
where g(n) = the cost to get to n (from initial state)
h(n) = an estimate of the cost to get from n to a
goal
➢ f(n) measures the estimated cost of getting to
the goal state from the current state and the
cost of the existing path to it.
Greedy Best-First Search
➢ Use as an evaluation function, f(n) = h(n), sorting nodes in the
Frontier by increasing values of f
➢ Selects the node to expand that is believed to be closest (i.e.,
smallest f value) to a goal node
Greedy Best-First Search
Cont. …
Cont. …
Cont. …
Cont. …
Example
Cont. …
Cont. …
2
Cont. …
3
Cont. …
Path cost:140+99+211=450
Problem with GBFS
Cont. …
Cont. …
Cont. …
Cont. …
Properties of GBFS
Examples
Example: Find Path from Arad to Bucharest
Heuristic: Straight-Line Distance
Cont. …
Cont. …
Example: Find Path from S to G in State-
Space Graph
A* Search
➢ Greedy best-first search minimizes a heuristic h(n) which is an estimated cost from
current state n to the goal state.
➢ Greedy best-first search is efficient but it is not optimal and not complete.
➢ Uniform cost search minimizes the cost g(n) from the initial state to current state n.
➢ Uniform cost search is optimal and complete but not efficient.
➢ A* Search: Combine Greedy best first search and Uniform cost search to get an
efficient algorithm which is complete and optimal.
Cont. …
➢ A* search evaluates nodes by combining
g(n), the cost to reach the node and h(n),
the cost to get the node to the goal.
➢ f(n)=g(n)+h(n)
➢ f(n) is the evaluation function which gives the
cheapest solution cost.
➢ g(n) is the exact cost to reach node n from
initial state.
➢ h(n) is an estimation of the assumed cost
from current state(n) to reach the goal.
A* -Example
Example of A* Search
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Path: A-E-G-H-I
Path cost: 140+80+97+101
Example
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …Example: Start node: A Goal: J
Properties of A*
Cont. …
Conditions for Optimality-Admissibility
➢ For all nodes n in the search space, h(n) ≤ h*(n), where h*(n) is
the actual cost of the minimum-cost path from n to a goal
➢ The cost to the nearest goal is never over-estimated
➢ When h(n) ≤ h*(n) holds true for all n, h is called an admissible
heuristic function
Example
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Cont. …
Conditions for Optimality-Consistency
Consistency
Admissible Heuristics for 8-puzzle problem
Cont. …
Cont. …
Cont. …
The heuristic f applied to states in the 8-puzzle.
Cont. …
IDA*
Cont. …
Example
Devising Heuristics