1

Artificial Intelligence

Module-2
Informed Search Strategies

2. Informed search/Heuristic search

A heuristic is a method that might not always find the best solution but is guaranteed to find a good solution
inreasonable time. By sacrificing completeness it increases efficiency.
 Useful in solving tough problems which
o could not be solved any other way.
o solutions take an infinite time or very long time to compute.

Calculating Heuristic Value:

 1. Euclidian distance- used to calculate straight line distance.

 2.Manhatten distance-If we want to calculate vertical or

horizontal distanceFor ex: 8 puzzle problem

2.1 Informed search

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.
The general approach we consider 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).

f(n)=Evaluation Function.

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.

Most 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.
if n is a goal node, then h(n)=0.

2.1.1 Greedy Best First Search:

 A combination of depth first and breadth first searches.

 Depth first is good because a solution can be found without computing all nodes and
breadth first is good because it does not get trapped in dead ends.
 Greedy best-first search tries to expand the node that is closest to the goal, on the
grounds GREEDY BEST-FIRST SEARCH that this is likely to lead to a solution
2023-24
2
Artificial Intelligence

quickly. Thus, it evaluates nodes by using just the heuristic function that is, f(n) =
h(n).
 we use the straight line distance heuristic, which we will call hSLD.
 The best first search allows us to switch between paths thus gaining the benefit of both
approaches. At each step the most promising node is chosen. If one of the nodes chosen
generates nodes that are less promising it is possible to choose another at the same
level and in effect the search changes from depth to breadth. If on analysis these are no
better than this previously unexpanded node and branch is not forgotten and the search
method reverts to the

OPEN is a priority queue of nodes that have been evaluated by the heuristic function but
Which have not yet been expanded into successors. The most promising nodes are at the
front.

CLOSED are nodes that have already been generated and these nodes must be stored
because a graph is being used in preference to a tree.

Algorithm:

1. Start with OPEN holding the initial state

2. Until a goal is found or there are no nodes left on open do.

 Pick the best node on OPEN

 Generate its successors
 For each successor Do
• If it has not been generated before ,evaluate it ,add it to
OPEN and record its parent

• If it has been generated before change the parent if this new path
is better and in that case update the cost of getting to any
successor nodes.

3. If a goal is found or no more nodes left in OPEN, quit, else return to 2.

2023-24
3
Artificial Intelligence

Example:
Figure shows the progress of a greedy best-first search using hSLD to find a path from Arad to
Bucharest.

States H(n)

2023-24
4
Artificial Intelligence

1. It is not optimal.

2. It is incomplete because it can start down an infinite path and never return to
try other possibilities.
3. The worst-case time complexity for greedy search is O (bm), where m is the
maximum depth of the search space.
4. Because greedy search retains all nodes in memory, its space complexity is the
same as its time complexity.
Problems:
EX-1

2023-24
5
Artificial Intelligence

EX-2

EX-3

2023-24
6
Artificial Intelligence

253+178=431 distance
A->E->F->I

2.1.2 A* Algorithm

The Best First algorithm is a simplified form of the A* algorithm.

The A* search algorithm (pronounced "Ay-star") is a tree search algorithm that finds a path
from a given initial node to a given goal node (or one passing a given goal test). It employs a
"heuristic estimate" which ranks each node by an estimate of the best route that goes through

2023-24
7
Artificial Intelligence

thatnode. It visits the nodes in order of this heuristic estimate.

Similar to greedy best-first search but is more accurate because A* takes into account the
nodes that have already been traversed.

From A* we note that f = g + h where

g is a measure of the distance/cost to go from the initial node to the current node

his an estimate of the distance/cost to solution from the current node.

Thus fis an estimate of how long it takes to go from the initial node to the solution

Algorithm:

1. Initialize : Set OPEN = (S); CLOSED

= ( ) g(s)= 0, f(s)=h(s)
2. Fail : If OPEN = ( ), Terminate and fail.

3. Select : select the minimum cost state, n, from

OPEN, save n in CLOSED

4. Terminate : If n €G, Terminate with success and return f(n)

5. Expand : for each successor, m, of n

a) If m € [OPEN U
b) CLOSED] Set g(m)
= g(n) + c(n , m) Set
f(m)
= g(m) + h(m)
Insert m in OPEN

c) If m € [OPEN U CLOSED]

Set g(m) = min { g(m) , g(n) + c(n

, m)} Set f(m) = g(m) + h(m)
If f(m) has decreased and m € CLOSED

Move m to OPEN.
Description:

2023-24
8
Artificial Intelligence

 A* begins at a selected node. Applied to this node is the "cost" of entering this node
(usually zero for the initial node). A* then estimates the distance to the goal node from
the current node. This estimate and the cost added together are the heuristic which is
assigned to the path leading to this node. The node is then added to a priority queue, often
called "open".
 The algorithm then removes the next node from the priority queue (because of the way a
priority queue works, the node removed will have the lowest heuristic). If the queue is
empty, there is no path from the initial node to the goal node and the algorithm stops.
Ifthe node is the goal node, A* constructs and outputs the successful path and stops.
 If the node is not the goal node, new nodes are created for all admissible adjoining nodes;
the exact way of doing this depends on the problem at hand. For each successivenode, A*
calculates the "cost" of entering the node and saves it with the node. This cost is
calculated from the cumulative sum of costs stored with its ancestors, plus the cost of the
operation which reached this new node.
 The algorithm also maintains a 'closed' list of nodes whose adjoining nodes have been
checked. If a newly generated node is already in this list with an equal or lower cost, no
further processing is done on that node or with the path associated with it. If a node in the
closed list matches the new one, but has been stored with a higher cost, it is removed
from the closed list, and processing continues on the new node.

 Next, an estimate of the new node's distance to the goal is added to the cost to form the
heuristic for that node. This is then added to the 'open' priority queue, unless an identical
nodeis found there.
 Once the above three steps have been repeated for each new adjoining node, the original
node taken from the priority queue is added to the 'closed' list. The next node is then
popped fromthe priority queue and the process is repeated

2023-24
9
Artificial Intelligence

The heuristic costs from each city to Bucharest:

2023-24
10

Artificial Intelligence

2023-24
11

Artificial Intelligence

A* search properties:((Performance Measurement parameters)

 The algorithm A* is admissible. This means that

provided a solution exists, the firstsolutionfound
by A* is an optimal solution.
 A* is admissible under the following conditions:
 Heuristic function: for every node n , h(n) ≤ h*(n) .
 A* is also complete.

 A* is optimally efficient for a given heuristic.

 A* is much more efficient that uninformed search.

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. An obvious example of an admissible heuristic is the straight-line distance
hSLD that we used in getting to Bucharest. Straight-line distance is admissible
because the shortest path between any two points is a straight line, so the straight
line.

 A second, slightly stronger condition called consistency (or sometimes

monotonicity) MONOTONICITY is required only for applications of A∗ to graph
search.9 A heuristic h(n) is consistent if, for every node n and every successor nof 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 nplus the estimated cost of reaching the
goal from n: h(n) ≤ c(n, a, n) + h(n).

Problems-1

2023-24
12

Artificial Intelligence

2023-24
13

Artificial Intelligence

2023-24
14

Artificial Intelligence

2.2 Heuristic Functions:

A heuristic is a method that

 might not always find the best solution but is guaranteed to find
a good solutioninreasonable time. By sacrificing completeness it
increases efficiency.
 Useful in solving tough problems which
o could not be solved any other way.
o solutions take an infinite time or very long time to compute.

Calculating Heuristic Value:

 1. Euclidian distance- used to calculate straight line distance.

 2.Manhatten distance-If we want to calculate

vertical or horizontaldistanceFor ex: 8 puzzle problem

The 8-puzzle was one of the earliest heuristic search problems.

the object of the puzzle is to slide the tiles horizontally or vertically into the empty space until
the configuration matches the goal configuration

2023-24
15

Artificial Intelligence

The average solution cost for a randomly generated 8-puzzle instance is about 22 steps.
The branching factor is about 3.
(When the empty tile is in the middle, four moves are possible; when it is in a corner,
two; and when it is along an edge, three.) This means that an exhaustive tree search to
depth 22 would look at about 322 ≈ 3.1 × 1010 states.
A graph search would cut this down by a factor of about 170,000 because only 9!/2 = 181,
440 distinct states are reachable
h1 = the number of misplaced tiles. For Figure 3.28, all of the eight tiles are out of position,
so the start state would have h1 = 8.
h1 is an admissible heuristic because it is clear that any tile that is out of place must be
moved at least once.
• h2 = the sum of the distances of the tiles from their goal positions. Because tiles cannot
move along diagonals, the distance we will count is the sum of the horizontal and vertical
distances. This is sometimes called the city block distance or Manhattan distance. h2 is also
admissible because all any move can do is move one tile one step MANHATTAN
DISTANCE closer to the goal. Tiles 1 to 8 in the start state give a Manhattan distance of h2
= 3 + 1 + 2 + 2 + 2 + 3 + 3 + 2 = 18 . As expected, neither of these overestimates the true
solution cost, which is 26.
2.2 .1 The effect of heuristic accuracy on performance
One way to characterize the quality of a heuristic is the effective branching factor b∗. If the
EFFECTIVE BRANCHING FACTOR total number of nodes generated by A∗ for a
particular problem is N and the solution depth is d, then b∗ is the branching factor that a
uniform tree of depth d would have to have in order to contain N + 1 nodes.
Thus, N +1=1+ b∗ + (b∗) 2 + ··· + (b∗) d .

For example, if A∗ finds a solution at depth 5 using 52 nodes, then the effective branching
factor is 1.92. The effective branching factor can vary across problem instances.

2.2.2 Generating admissible heuristics from relaxed problems

We have seen that both h1 (misplaced tiles) and h2 (Manhattan distance) are fairly good
heuristics for the 8-puzzle and that h2 is better. How might one have come up with h2? Is it
possible for a computer to invent such a heuristic mechanically? h1 and h2 are estimates of
the remaining path length for the 8-puzzle, but they are also perfectly accurate path lengths
for simplified versions of the puzzle.

If the rules of the puzzle were changed so that a tile could move anywhere instead of just to
the adjacent empty square, then h1 would give the exact number of steps in the shortest
solution. Similarly, if a tile could move one square in any direction, even onto an occupied
square, then h2 would give the exact number of steps in the shortest solution. A problem with
fewer restrictions on the actions is called a relaxed problem.

2023-24
16

Artificial Intelligence

2.2.3 Generating admissible heuristics from subproblems: Pattern databases

Admissible heuristics can also be derived from the solution cost of a subproblem of a given
problem.
The idea behind pattern databases is to store these exact solution costs for every possible
subproblem instance.

2.2.4 Learning heuristics from experience

A heuristic function h(n) is supposed to estimate the cost of a solution beginning from the
state at node n. How could an agent construct such a function? One solution was given in the
preceding sections—namely, to devise relaxed problems for which an optimal solution can be
found easily. Another solution is to learn from experience. “Experience” here means solving
lots of 8-puzzles, for instance. Each optimal solution to an 8-puzzle problem provides
examples from which h(n) can be learned.
A common approach is to use a linear combination: h(n) = c1x1(n) + c2x2(n)

Example:

2023-24
17

Artificial Intelligence

2023-24