Informed Search Strategies

Informed search algorithms
Module 3
Informed (Heuristic) Search
Idea: be smart
about what paths
to try.
2
Blind Search vs. Informed Search
What’s the difference?

Blind search
• Randomly choose where to search in the search tree
• When problems get large, not practical anymore
Heuristic search
• Explore the node which is more likely to lead to the goal state
• Quite often, using knowledge
3
Heuristics
• Heuristic technique is a criterion for determining which among
several alternatives will be the most effective to achieve some
goal
• This technique improves the efficiency of a search process

possibly by sacrificing claims of systematic and completeness
• It no longer guarantees to find the best solution but almost

always finds a very good solution
• Using good heuristics we can hope to get good solutions to

hard problems in less than exponential time
Informed (Heuristic) Search
Heuristic or informed search exploits additional knowledge about
the problem that helps direct search to more promising paths.
• A heuristic function, h(n), provides an estimate of the cost of the

path from a given node to the closest goal state.
• Must be zero if the node represents a goal state.

• Usually more efficient than blind searches
• There is no guarantee that it is the best node
5
Best-First Search
Combines the advantages of both DFS and BFS into a
single method.
DFS is good because it allows a solution to be found
without all competing branches having to be expanded.
BFS is good because it does not get branches on dead end
paths.
One way of combining the two is to follow a single path
at a time, but switch paths whenever some competing
path looks more promising than the current one does.
6
Best-First Search
At each step of the BFS search process, we select the
most promising of the nodes we have generated so far.
This is done by applying an appropriate heuristic
function to each of them.
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)
7
Best-First Search
• Use an evaluation function f(n) for node n.
• Always choose the node from fringe that has
the lowest f value.
3 5 1
4 6
8
Best-first search
• A search strategy is defined by picking the order of node
expansion
• Idea: use an evaluation function f(n) for each node
– estimate of "desirability“
→ Expand most desirable unexpanded node
• Implementation:
Order the nodes in fringe in decreasing order of desirability
• Special cases:
– greedy best-first search
– A* search
Greedy best-first search
• Evaluation function f(n) = h(n) (heuristic)
= estimate of cost from n to goal
• e.g., hSLD(n) = straight-line distance from n to

Bucharest
• Greedy best-first search expands the node

that appears to be closest to goal
Romania with step costs in km
Greedy best-first search- Route finding
problems in Romania
straight line distance heuristic, Hsld
• If the goal is Bucharest, we need to know the straight-line distances to
Bucharest
• hSLD is correlated with actual road distances and is, therefore, a useful
heuristic
problem in Romania
problem in Romania
Greedy Best-First Search - Backtrack
A A A
B C D B C D
3 5 1 3 5
E F
4 6
A A
B C D B C D
5 5
G H E F G H E F
6 5 4 6 6 5 6
I J
2 1
15
Properties of greedy best-first search
• Complete?
• No – can get stuck in loops, e.g., Iasi → Neamt → Iasi →
Neamt →
• Time?
• O(bm), but a good heuristic can give dramatic
improvement
• Space?
• O(bm) -- keeps all nodes in memory
• Optimal?
• No
A* search
• Evaluation function f(n) = g(n) + h(n)
• g(n) = cost so far to reach n

• h(n) = estimated cost from n to goal
• f(n) = estimated total cost of path through n to
goal
A*
f(n) = g(n) + h(n)
g(n) = “cost from the starting node to reach n”
h(n) = “estimate of the cost of the cheapest path from n to
the goal node”
h(n)
20
g(n) 15 n
10 5
15
20 18
25
33
A* for Romanian Shortest Path
19
20
21
22
23
24
Admissible heuristics
• A heuristic h(n) is admissible if for every node n,
h(n) ≤ h*(n), where h*(n) is the true cost to reach the goal state from
n.
• An admissible heuristic never overestimates the cost to reach the

goal, i.e., it is optimistic
• Example: hSLD(n) (never overestimates the actual road distance)
• Theorem: If h(n) is admissible, A* using TREE-SEARCH is optimal

Consistent Heuristics
• h(n) is consistent if
– for every node n
– for every successor n´ due to legal action a
– h(n) <= c(n,a,n´) + h(n´) (Triangle Inequality)
n
h(n)
c(n,a,n´)
h(n´)
n´ G
• Every consistent heuristic is also admissible.

• Theorem: If h(n) is consistent, A* using GRAPH-
SEARCH is optimal
19
Properties of A*
• Complete?
Yes (unless there are infinitely many nodes with f ≤ f(G) )
• Time? Exponential in worst case
• Space? Keeps all nodes in memory
• Optimal?
Yes (depending upon search algo and heuristic property)
http://www.youtube.com/watch?v=huJEgJ82360
Heuristics Functions
8-puzzle search space

Typical solution length: 22 steps
Average branching factor: 3
Exhaustive tree search: 320 =~ 3.1 x 1010 states
Exhaustive Graph search: 9! = 3,62,880
How about for a 15 puzzle problem? Good Heuristics is

required!!
Admissible heuristics
E.g., for the 8-puzzle:
• h1(n) = number of misplaced tiles. In fig., all of the eight

tiles are out of position, so the start state would have h1
= 8.
• h2(n) = total Manhattan or City block distance
(i.e., no. of squares from desired location of each tile)
• h1(S) = ? 8
• h2(S) = ? 3+1+2+2+2+3+3+2 = 18
Dominance
To test the heuristic functions h1 and h2, 1200 random problems were generated with
solution lengths from 2 to 24 (100 for each even number) and solved them with iterative
deepening search and with A∗ tree search using both h1 and h2.
Performance of heuristics function
• One way to characterize the quality of a heuristic is the
effective branching factor b∗
• If the 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, given by
N = 1 + b* + (b*)2 + ...+ (b*)d
• To test the heuristic functions h1 and h2, 1200 random

problems were generated with solution lengths from 2 to 24
(100 for each even number) and solved them with iterative
deepening search and with A∗ tree search using both h1 and h2.
Performance of heuristics function
Dominance
• If h2(n) ≥ h1(n) for all n (both
admissible) then h2 dominates h1
• h2 is better for search (in terms of efficiency)
• Typical search costs (average number of node expanded):
• d=12
A*(h1) = 227 nodes
A*(h2) = 73 nodes
• d=24
A*(h1) = 39,135 nodes
A*(h2) = 1,641 nodes
Relaxed problems
• A problem with fewer restrictions on the actions is called a
relaxed problem
• The cost of an optimal solution to a relaxed problem is an

admissible heuristic for the original problem
• If the rules of the 8-puzzle are relaxed so that a tile can move
anywhere, then h1(n) gives the shortest solution
• If the rules are relaxed so that a tile can move to any adjacent
square, then h2(n) gives the shortest solution
• The state-space graph of the relaxed problem is a supergraph

of the original state space because the removal of restrictions
creates added edges in the graph.
Generating admissible heuristics from
subproblems: Pattern databases
• Figure shows a subproblem of the 8-puzzle problem. The subproblem involves
getting tiles 1, 2, 3, 4 into their correct positions. Clearly, the cost of the optimal
solution of this subproblem is a lower bound on the cost of the complete problem.
• The choice of 1-2-3-4 is fairly arbitrary; we could also construct databases for 5-
6-7-8, for 2-4-6-8, and so on. Each database yields an admissible heuristic, and
these heuristics can be combined
• The idea behind pattern databases is to store these exact solution costs for every
possible subproblem instance—in our example, every possible configuration of
the four tiles and the blank.

Informed Search Strategies

Uploaded by

Copyright:

Available Formats

Informed Search Strategies

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Informed Search Strategies

Uploaded by

Copyright:

Available Formats

Informed search algorithms

What’s the difference?

• When problems get large, not practical anymore

• Quite often, using knowledge

• This technique improves the efficiency of a search process

• It no longer guarantees to find the best solution but almost

• Using good heuristics we can hope to get good solutions to

• A heuristic function, h(n), provides an estimate of the cost of the

• Must be zero if the node represents a goal state.

Best-first search is an instance of the general TREE-

→ Expand most desirable unexpanded node

• e.g., hSLD(n) = straight-line distance from n to

• Greedy best-first search expands the node

• g(n) = cost so far to reach n

• An admissible heuristic never overestimates the cost to reach the

• Example: hSLD(n) (never overestimates the actual road distance)

• Theorem: If h(n) is admissible, A* using TREE-SEARCH is optimal

• Every consistent heuristic is also admissible.

• Time? Exponential in worst case

• Space? Keeps all nodes in memory

8-puzzle search space

How about for a 15 puzzle problem? Good Heuristics is

• h1(n) = number of misplaced tiles. In fig., all of the eight

• If the total number of nodes generated by A∗ for a

• To test the heuristic functions h1 and h2, 1200 random

• The cost of an optimal solution to a relaxed problem is an

• The state-space graph of the relaxed problem is a supergraph

You might also like