Informed Search Algorithms
Chapter 3, Sections 5–6
AIMA Slides © and ; Chapter 3, Sections 5–6 1
Copyright By PowCoder代写 加微信 powcoder
♢ Best-first search ♢ A∗ search
♢ Heuristics
♢ Hill-climbing
AIMA Slides © and ; Chapter 3, Sections 5–6 2
Review: General search
function General-Search( problem, Queuing-Fn) returns a solution, or failure
nodes ← Make-Queue(Make-Node(Initial-State[problem])) loop do
if nodes is empty then return failure
node ← Remove-Front(nodes)
if Goal-Test[problem] applied to State(node) succeeds then return node nodes ← Queuing-Fn(nodes, Expand(node, Operators[problem]))
A strategy is defined by picking the order of node expansion
AIMA Slides © and ; Chapter 3, Sections 5–6 3
Best-first search
Idea: use an evaluation function for each node – estimate of “desirability”
⇒ Expand most desirable unexpanded node Implementation:
QueueingFn = insert successors in decreasing order of desirability
Special cases: greedy search
AIMA Slides © and ; Chapter 3, Sections 5–6 4
Romania with step costs in km
AIMA Slides © and ; Chapter 3, Sections 5–6 5
Greedy search
Evaluation function h(n) (heuristic)
= estimate of cost from n to goal
E.g., hSLD(n) = straight-line distance from n to Bucharest
Greedy search expands the node that appears to be closest to goal
AIMA Slides © and ; Chapter 3, Sections 5–6 6
Greedy search example
AIMA Slides © and ; Chapter 3, Sections 5–6 7
Greedy search example
AIMA Slides © and ; Chapter 3, Sections 5–6 8
Greedy search example
AIMA Slides © and ; Chapter 3, Sections 5–6 9
Greedy search example
AIMA Slides © and ; Chapter 3, Sections 5–6 10
Properties of greedy search
Complete?? Time?? Space?? Optimal??
AIMA Slides © and ; Chapter 3, Sections 5–6 11
Properties of greedy search
Complete?? No – can get stuck in loops, e.g., Iasi to → Neamt → Iasi → Neamt →
Complete in finite space with repeated-state checking
Time?? O(bm), but a good heuristic can give dramatic improvement Space?? O(bm)—keeps all nodes in memory
Optimal?? No
AIMA Slides © and ; Chapter 3, Sections 5–6 12
Idea: avoid expanding paths that are already expensive Evaluation function f(n) = g(n) + h(n)
g(n) = cost so far to reach n (path cost)
h(n) = estimated cost to goal from n
f(n) = estimated total cost of path through n to goal
A∗ search uses an admissible heuristic
i.e., h(n) ≤ h∗(n) where h∗(n) is the true cost from n.
E.g., hSLD(n) never overestimates the actual road distance Theorem: A∗ search is optimal
AIMA Slides © and ;
Chapter 3, Sections 5–6 13
A∗ search example
AIMA Slides © and ; Chapter 3, Sections 5–6 14
A∗ search example
AIMA Slides © and ; Chapter 3, Sections 5–6 15
A∗ search example
AIMA Slides © and ; Chapter 3, Sections 5–6 16
A∗ search example
151 99 671
AIMA Slides © and ; Chapter 3, Sections 5–6 17
A∗ search example
151 99 671
AIMA Slides © and ; Chapter 3, Sections 5–6 18
A∗ search example
151 99 671
AIMA Slides © and ; Chapter 3, Sections 5–6 19
Optimality of A∗ (standard proof )
Suppose some suboptimal goal G2 has been generated and is in the queue. Let n be an unexpanded node on a shortest path to an optimal goal G.
f(G2) = g(G2) > g(G)
since h(G2) = 0
since G2 is suboptimal
since h is admissible
Since f(G2) > f(n), A∗ will never select G2 for expansion
AIMA Slides © and ; Chapter 3, Sections 5–6 20
Optimality of A∗ (more useful)
Lemma: A∗ expands nodes in order of increasing f value
Gradually adds “f-contours” of nodes (cf. breadth-first adds layers)
Contour i has all nodes with f = fi, where fi < fi+1
AIMA Slides © and ; Chapter 3, Sections 5–6 21
Properties of A∗
Complete?? Yes, unless there are infinitely many nodes with f ≤ f(G) Time?? Exponential in [relative error in h × length of soln.]
Space?? Keeps all nodes in memory
Optimal?? Yes—cannot expand fi+1 until fi is finished
AIMA Slides © and ; Chapter 3, Sections 5–6 22
Admissible heuristics
E.g., for the 8-puzzle:
h1(n) = number of misplaced tiles h2(n) = total Manhattan distance
(i.e., no. of squares from desired location of each tile)
Start State Goal State
h1(S) =?? h2(S) =??
AIMA Slides © and ;
Chapter 3, Sections 5–6 23
Admissible heuristics
E.g., for the 8-puzzle:
h1(n) = number of misplaced tiles h2(n) = total Manhattan distance
(i.e., no. of squares from desired location of each tile)
Start State Goal State
h1(S) =?? 7
h2(S) =?? 2+3+3+2+4+2+0+2 = 18
AIMA Slides © and ;
Chapter 3, Sections 5–6 24
If h2(n) ≥ h1(n) for all n (both admissible) then h2 dominates h1 and is better for search
Typical search costs:
IDS = 3,473,941 nodes A∗(h1) = 539 nodes A∗(h2) = 113 nodes IDS=toomanynodes A∗(h1) = 39,135 nodes A∗(h2) = 1,641 nodes
AIMA Slides © and ;
Chapter 3, Sections 5–6 25
Relaxed problems
Admissible heuristics can be derived from the exact solution cost of a relaxed version of the 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
AIMA Slides © and ; Chapter 3, Sections 5–6 26
Iterative improvement algorithms
In many optimization problems, path is irrelevant; the goal state itself is the solution
Then state space = set of “complete” configurations;
find optimal configuration, e.g., Travelling Salesperson Problem or, find configuration satisfying constraints, e.g., n-queens
In such cases, can use iterative improvement algorithms; keep a single “current” state, try to improve it
Constant space, suitable for online as well as offline search
AIMA Slides © and ; Chapter 3, Sections 5–6 27
Example: Travelling Salesperson Problem
Find the shortest tour that visits each city exactly once
Relaxed problem: let path be any structure that connects all cities =⇒ use minimum spanning tree as heuristic for the TSP
AIMA Slides © and ; Chapter 3, Sections 5–6 28
Example: n-queens
Put n queens on an n × n board with no two queens on the same row, column, or diagonal
AIMA Slides © and ; Chapter 3, Sections 5–6 29
Hill-climbing (or gradient ascent/descent)
“Like climbing Everest in thick fog with amnesia”
function Hill-Climbing( problem) returns a solution state inputs: problem, a problem
local variables: current, a node
next, a node
current ← Make-Node(Initial-State[problem]) loop do
next ← a highest-valued successor of current
if Value[next] < Value[current] then return current current ← next
AIMA Slides © and ; Chapter 3, Sections 5–6 30
Hill-climbing contd.
Problem: depending on initial state, can get stuck on local maxima
AIMA Slides © and ; Chapter 3, Sections 5–6 31
Heurstics help reduce search cost,
however, finding an optimal solution is still difficult.
Greedy best-first search is not optimal, but can be efficient.
A∗ search is complete and optimal, but is prohibitive in memory.
Hill-climbing methods operate on complete-state formulations, require less memory, but are not optimal.
Examples of skills expected:
♢ Demonstrate operation of search algorithms
♢ Discuss and evaluate the properties of search algorithms ♢ Derive and compare heuristics for a problem
AIMA Slides © and ;
Chapter 3, Sections 5–6 32
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com