INFORMED (HEURISTIC)

SEARCH STRATEGIES
Course Title: Artificial Intelligence and Expert System
Course Code: CSC4226

Dept. of Computer Science

Faculty of Science and Technology

Lecture No: Four (4) Week No: Four (4) Semester:

Lecturer: Dr Debajyoti Karmaker

LECTURE OUTLINE

1. BEST-FIRST SEARCH

2. GREEDY BEST-FIRST SEARCH

3. A* SEARCH

4. CONDITIONS FOR OPTIMALITY

5. OPTIMALITY OF A*
 INFORMED SEARCH STRATEGY

Informed search strategy—

• one that uses problem-specific knowledge beyond the

definition of the problem itself

• can find solutions more efficiently than can an uninformed

strategy.

roblem-specific knowledge
is the extra bit of information the program uses rather than
the problem formulation, thus known as Informed Search
 BEST-FIRST SEARCH

• The general approach to informed search is called best-first search

• Best-first search is an instance of the general TREE-SEARCH or GRAPH-SEARCH algorithm
in which a node is selected for expansion based on an evaluation function, f(n).
• The evaluation function is construed as a cost estimate, so the node with the
lowest evaluation is expanded first

• The implementation of best-first graph search is identical to that for uniform-

cost search, except for the use of f instead of g to order the priority queue.

The choice of f determines the search strategy.

HEURISTIC SEARCH COMPARED
WITH BLIND SEARCH
 HEURISTIC FUNCTION
• The choice of f(evaluation function) determines the search strategy
• Best-first algorithms include as a component of f a heuristic function, denoted
h(n)
• h(n) = estimated cost of the cheapest path from the state at node n to a goal
state.
• h(n) takes a node as input, but, unlike g(n), it depends only on the state at that
node.
• Heuristic functions are the most common form in which additional knowledge of
the problem is imparted to the search algorithm
• Consider them to be arbitrary, nonnegative, problem-specific functions, with one
constraint: if n is a goal node, then h(n)=0.
 GREEDY BEST-FIRST SEARCH
• Greedy best-first search8 tries to expand the node that is closest to
the goal, on the grounds that this is likely to lead to a solution
quickly.
• Thus, it evaluates nodes by using just the heuristic function; that is,
f(n) = h(n).
• “greedy”—at each step it tries to get as close to the goal as it can.

• Its search cost is minimal. It is not optimal.

• Greedy best-first tree search is also incomplete even in a finite
state space, much like depth-first search.
STRAIGHT-LINE DISTANCE HEURISTIC
GREEDY BEST-FIRST
TREE SEARCH
 A* SEARCH:
MINIMIZING THE TOTAL ESTIMATED SOLUTION COST
The most widely known form of best-first search is called A*search
It evaluates nodes by combining
g(n), the 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 the cheapest solution through n .
A∗ search is both complete and optimal.

The algorithm is identical to UNIFORM-COST-SEARCH except that

A∗ uses g + h instead of g.
 InWe
We
Once
Press
actual
now
have
begin
now
Arad
Rimnicu
Fagaras
space
expand
fact,
just
now
expand
is
with expanded
to
expanded
is
the
arrived
issee
expanded
the
expanded
Fagaras
Sibiu
Rimnicu
Pitesti
algorithm
an
initial
atA*
(that
we
aBucharest.
(that
node
search
state
we
(that
we
look
will
is,look
is,
look
(Pitesti)
we
of
is,
for
not
we
ofArad.
we
for
expand
for
the
As
the
expand
really
expand
the
this
the
node
that
Romanian
Thelowest
recognise
node
is
the
the
revealed
cost
the
with
the
node
node
with
lowest
of
cost
node
the
map
reaching
with
that
the
Bucharest,
with
lowest
node.
featured
with
cost
we
lowest
the
the
As
node
the
have
Arad
cost.
lowest
lowest
you
cost.
in
lowest
but
found
AND
from
Sibiu
the
can
value
itAs
value
has
previous
the
see,
Arad
has
value
Bucharest.
youof
agoal
the
of
we
cost
can
(or
foff).now
lowest
).state
slide.
fg
Press
see,
of ).
Press
value)
Press
418.
Ithave
we
Pitesti
just
Note:
space
value
space
Ifis
can
space
two
keeps
there
0Throughout
has
to
for
miles.
terminate
to
Bucharest
continue
to
expanding
the
f.continue
is (The
continue
any
The
lowest
other
cost
the
straight
the
nodes.
the
the
value
search.
the
to
search.
animation
lower
search.
reach
lowest
search.
line
One
forcost
If Sibiu
f.of
youcost
all
nodes
nodes
distance
from
(The
node
these
look (based
back
costare
Arad
(and
nodesfrom
toinlabelled
over
is reach
(140on
this
AradArad
thefcase
)Pitesti
–until
with
miles,to
slides Bucharest
Sibiuityou
there
and f(n)
–finds
from the =one
Rimnicu
iswill g(n)
Aradasee
(or
goal
is+–that
straight h317
cheaperh(n).
state
value)
Pitesti
line
theHowever,we
AND
miles,–is
node, 366
distanceitFagaras,
solutionhas
miles.
Bucharest
and from
the the
will
This
lowest
returned be an
straight
)with
Sibiu
has gives
using
ato
by fvalue
line
cost
the
theus
the
value aof
abbreviations
total
distance
of
goal
A* 417)
of f.state
search So,
418. value
then
from we
isThe must
of
pattern
we
253 (f,f(gnow
Pitesti
other
need
miles. =Arad
and
togtothe
node +This
move
h–goal
expand)to
366
make
(Aradtostate
Sibiu
gives itmiles.
–Fagaras
ain the
is Press
Rimnicu
Sibiu
total
casenotation
98and
–of space
expand
itFagaras
miles.
–393
leads
Pitesti –to
to
it.simpler
expand
Press
miles).
aThis
–Bucharest
better space
Bucharest
gives the
Press
(2) ),)initial
solution
a total istointo
space
has continue.
of state
an
fact
to of optimal
Bucharest
415
f move
value
the
miles).Arad.
to
ofthan this
450.
Pressnode
solution.
the
We space
418
therefore
andtosolution
Press
expand
move move
space
to
we
it.this
to
have
tothe
node
continue
already
first
and Bucharest
with
expand
found.thePressit.
node
slideshow. space
and expand
to continue. it. Press space to continue

Zerind F= 75 + 374 Oradea

F= 449
F= 291 + 380
F= 671

F= 0 + 366
F= 366
Arad Fagaras
Sibiu F= 239 + 178
F= 417
F= 140 + 253
F= 393
F= 220 + 193 Bucharest(2)
F= 118 + 329
F= 413
F= 447 F= 450 + 0
Rimnicu F= 450
Timisoara
Bucharest
F= 418 + 0
F= 418
Pitesti
F= 317 + 98
Craiova F= 415
F= 366 + 160
F= 526
A∗ SEARCH FOR BUCHAREST
A∗ SEARCH FOR BUCHAREST
CONDITIONS FOR OPTIMALITY:
ADMISSIBILITY AND CONSISTENCY
• The first condition we require for optimality is that h(n) be an
admissible heuristic
• An admissible heuristic is one that never overestimates the cost to
reach the goal
• Because g(n) is the actual cost to reach n along the current path,
and f(n)=g(n) + h(n), we have as an immediate consequence that
f(n) never overestimates the true cost of a solution along the
current path through n.
• Admissible heuristics are by nature optimistic because they think
the cost of solving the problem is less than it actually is.
ADMISSIBILITY
 CONSISTENCY
• A second, slightly stronger condition called consistency (or
sometimes monotonicity) is required only for applications of A∗
to graph search.
• A heuristic h(n) is consistent if, for every node n and every
successor n of n generated by any action a, the estimated cost of
reaching the goal from n is no greater than the step cost of getting
to n plus the estimated cost of reaching the goal from n :
h(n) ≤ c(n, a, n’) + h(n’).
• This is a form of the general triangle inequality, which stipulates
that each side of a triangle cannot be longer than the sum of the
other two sides
 OPTIMALITY OF A*
A∗ has the following properties: the tree-search version of A∗ is optimal if h(n) is
admissible, while the graph-search version is optimal if h(n) is consistent.

if h(n) is consistent, then the values of f(n) along any path are nondecreasing.
The proof follows directly from the definition of consistency. Suppose n is a
successor of n; then g(n’)=g(n) + c(n, a, n’) for some action a, and we have
f(n) = g(n) + h(n) = g(n) + c(n, a, n) + h(n) ≥ g(n) + h(n) = f(n) .

The next step is to prove that whenever A∗ selects a node n for expansion, the
optimal path to that node has been found. Were this not the case, there would have
to be another frontier node n on the optimal path from the start node to n. because
f is nondecreasing along any path, n would have lower f-cost than n and would
have been selected first.
References

1. Chapter 3: Solving Problem by Searching , Pages 92-97

“Artificial Intelligence: A Modern Approach,” by Stuart J. Russell and Peter Norvig,
 Books

1. “Artificial Intelligence: A Modern Approach,” by Stuart J. Russell and Peter Norvig.

2. "Artificial Intelligence: Structures and Strategies for Complex Problem Solving", by
George F. Luger, (2002)
3. "Artificial Intelligence: Theory and Practice", by Thomas Dean.
4. "AI: A New Synthesis", by Nils J. Nilsson.
5. “Programming for machine learning,” by J. Ross Quinlan,
6. “Neural Computing Theory and Practice,” by Philip D. Wasserman, .
7. “Neural Network Design,” by Martin T. Hagan, Howard B. Demuth, Mark H.
Beale, .
8. “Practical Genetic Algorithms,” by Randy L. Haupt and Sue Ellen Haupt.
9. “Genetic Algorithms in Search, optimization and Machine learning,” by David E.
Goldberg.
10."Computational Intelligence: A Logical Approach", by David Poole, Alan
Mackworth, and Randy Goebel.
11.“Introduction to Turbo Prolog”, by Carl Townsend.