CS计算机代考程序代写 algorithm 02-search-part2

02-search-part2

Searching the State
Space

Part 2: Pruning, informed search, other strategies

1

The problem with cycles and multiple paths
There is an issue that affects all search strategies in the
framework of generic graph search:

The algorithm can expand multiple paths to the same node.

Can cause:

– Cycles (infinite search tree)

– Wasted computation

Solution:

We “prune” unnecessary branches of the search tree.

2

Pruning
Principle: Do not expand paths to nodes that have already been expanded.

Note: a node is expanded when the frontier returns a path ending in that node to the
generic search algorithm (and thus the algorithm expands that path by outgoing arcs).

Implementation:

• The frontier keeps track of expanded (aka “closed”) nodes.

• When trying to add a new path to the frontier, it is added only if another path to the same
end-node has not been already expanded, otherwise the new path is discarded (pruned).

• When asking for the next path to be returned by the frontier, a path is selected and
removed but it is returned only if the end-node has not been expanded before, otherwise
the path is discarded (pruned) and not returned. The selection and removal is repeated
until a path is returned (or the frontier becomes empty). If a path is returned, its end-
node will be remembered as an expanded node.

In frontier traces, every time a path is pruned (when trying to add or when asking for the
next path), we add an exclamation mark ‘!’ at the end of the line.

3

Example: LCFS with pruning
Trace LCFS with pruning on the following graph:

nodes = {S, A, B, G},

edge_list=[(S,A,3), (S,B,1), (B,A,1), (A,B,1), (A,G,5)],

starting_nodes = [S],

goal_nodes = {G}.

4

Answer:

# expanded={}

+ S,0

– S,0  # expanded={S}

+ SA,3

+ SB,1

– SB,1  # expanded={S,B}

+ SBA,2

– SBA,2  # expanded={S,B,A}

+ SBAB,3!   # not added!

+ SBAG,7

– SA,3!     # not returned!

– SBAG,7  # expanded={S,B,A,G}

How does LCFS behave?
LCFS explores increasing cost
contours.

The good:

– Finds an optimal solution.

The bad:

– Explores options in every
direction

– No information about goal
location

5

Search heuristic
Idea: don’t ignore information about the goal when selecting paths. Often
there is extra knowledge that can be used to guide the search: heuristics.

h(n) is an estimate of the cost of the shortest path from node n to a goal
node.

h needs to be efficient to compute.

h can be extended to paths: h(⟨n0,…,nk⟩) = h(nk).

h is said to be admissible if and only if:

• ∀n h(n) ≥ 0 [i.e. h is non-negative]; and

• there is no path from n to a goal node with cost less than h(n). In other
words h(n) is less than or equal to the actual optimal cost of getting
from n to a goal node. [Or equivalently h never over-estimates the cost.]

6

Example heuristic functions
• If the nodes are points on a Euclidean plane and the cost is the distance, h(n) can be the

straight-line distance from n to the closest goal.

• If the nodes are locations and cost is time, h(n) can be the straight-line distance to the closest
goal divided by the maximum possible speed.

• If the nodes are locations in a maze where the agent can move in four directions, h(n) can be
Manhattan distance.

• A heuristic function can be found by solving a simpler (less constrained) version of the
problem.

7

Example: Euclidean distance

8

Romania with step costs in km

Bucharest

Giurgiu

Urziceni

Hirsova

Eforie

Neamt
Oradea

Zerind

Arad

Timisoara

Lugoj
Mehadia

Dobreta
Craiova

Sibiu

Fagaras

Pitesti
Rimnicu Vilcea

Vaslui

Iasi

Straight!line distance
to Bucharest

0
160
242
161

77
151

241

366

193

178

253
329
80

199

244

380

226

234

374

98

Giurgiu

Urziceni
Hirsova

Eforie

Neamt

Oradea

Zerind

Arad

Timisoara

Lugoj

Mehadia

Dobreta

Craiova

Sibiu Fagaras

Pitesti

Vaslui

Iasi

Rimnicu Vilcea

Bucharest

71

75

118

111

70

75
120

151

140

99

80

97

101

211

138

146 85

90

98

142

92

87

86

B. Beckert: KI für IM – p.24

Best-first Search
• Idea: select the path whose end is closest to a goal according

to the heuristic function.

• Best-first search is a greedy strategy that selects a path on the
frontier with minimal h-value.

• It treats the frontier as a priority queue ordered by h.

• By exploring more “promising” paths first, in many instances, it
can find a solution faster than LCFS.

• Main drawback: does not guarantee finding an optimal
solution.

9

Best-first search: example

10

Romania with step costs in km

Bucharest

Giurgiu

Urziceni

Hirsova

Eforie

Neamt
Oradea

Zerind

Arad

Timisoara

Lugoj
Mehadia

Dobreta
Craiova

Sibiu

Fagaras

Pitesti
Rimnicu Vilcea

Vaslui

Iasi

Straight!line distance
to Bucharest

0
160
242
161

77
151

241

366

193

178

253
329
80

199

244

380

226

234

374

98

Giurgiu

Urziceni
Hirsova

Eforie

Neamt

Oradea

Zerind

Arad

Timisoara

Lugoj

Mehadia

Dobreta

Craiova

Sibiu Fagaras

Pitesti

Vaslui

Iasi

Rimnicu Vilcea

Bucharest

71

75

118

111

70

75
120

151

140

99

80

97

101

211

138

146 85

90

98

142

92

87

86

B. Beckert: KI für IM – p.24

stages of search tree and frontier

Example: tracing best-first search
• Trace the frontier when using the best-first

(greedy) search strategy for the following graph.

• The starting node is S and the goal node is G.

• Heuristic values are given next to each node.

• SA comes before SB.

11

Answer:

+ S,3

– S,3

+ SA,2

+ SB,1

– SB,1

+ SBG,0

– SBG,0

heuristic function
h(S) = 3

h(A) = 2

h(B) = 1

h(G) = 0

A* search strategy
Idea:

• Don’t be as wasteful as LCFS

• Don’t be as greedy as best-first search.

• Estimate the cost of paths as if they could be extended to reach a goal in the best possible way.

Evaluation function f(p) = cost(p) + h(n)

• p is a path, n is the last node on p

• cost(p) = cost of path p (This is the actual cost from the starting node to node n)

• h(n) = an estimate of cost from n to goal (This is an optimistic estimate to the closest goal node)

• f(p) = estimated total cost of path through p to goal

The frontier is a priority queue ordered by f(p).

12

Example: tracing A* search
• Trace the frontier when using the A* search

strategy for the following graph.

• The starting node is S and the goal node is G.

• Heuristic values are given next to each node.

• SA comes before SB.

13

Answer:

+ S,3    # 0 + 3 = 3

– S,3

+ SA,4   # 2 + 2 = 4

+ SB,3   # 2 + 1 = 3

– SB,3

+ SBG,5  # 5 + 0 = 5

– SA,4

+ SAG,4  # 4 + 0 = 4

– SAG,4
Note: This small example only show the inner working of A*. It
does not demonstrate its advantage over LCFS.

heuristic function
h(S) = 3

h(A) = 2

h(B) = 1

h(G) = 0

Example: tracing A* search

• Same example as the one before
just assume h(A) = 4 instead.

14

Answer:

+ S,3    # 0 + 3 = 3

– S,3

+ SA,6   # 2 + 4 = 6

+ SB,3   # 2 + 1 = 3

– SB,3

+ SBG,5  # 5 + 0 = 5

– SBG,5

Non-optimal solution! Why?

heuristic function
h(S) = 3

h(A) = 4

h(B) = 1

h(G) = 0

Properties of A*
• A* always finds an optimal solution (a solution with the lowest costs)

as long as:

– there is a solution;

– there is no pruning; and

– the heuristic function is admissible.

• Does it halt on every graph?

• How about time and space complexity?

• LCFS vs A* (in average):

15

A*: proof of optimality
When using A* (without pruning) the first path p from a starting node to a goal node that is selected
and removed from the frontier has the lowest cost.

Sketch of proof:

• Suppose to the contrary that there is another path from one of the starting nodes to a goal node
with a lower cost.

• There must be a path p’ on the frontier such that one of its continuations leads to the goal with a
lower overall cost than p.

• Since p was removed before p’:

• Let c be any continuation of p’ that goes to a goal node; that is, we have a path p’c from a start
node to a goal node. Since h is admissible, we have:

• Thus:

f(p) ≤ f(p′ ) ⟹ cost(p) + h(p) ≤ cost(p′ ) + h(p′ ) ⟹ cost(p) ≤ cost(p′ ) + h(p′ )

cost(p′ c) = cost(p′ ) + cost(c) ≥ cost(p′ ) + h(p′ )

cost(p) ≤ cost(p′ ) + h(p′ ) ≤ cost(p′ ) + cost(c) = cost(p′ c)
16

Effect of pruning on A*
Trace the frontier in A* search for the following graph,
with and without pruning.

nodes={s, a, b, g},

estimates = {s:7, a:2, b:6, g:0},

edge_list=[(s,a,3), (s,b,1),

(b,a,1), (a,g,5)],

starting_nodes = [s],

goal_nodes = {g}.

17

s

a

b

g

h(s) = 7

h(a) = 2

h(g) = 0

h(b) = 6

3

1

1

5

Answer without pruning

+ S, 7
– S, 7
+ SA, 5
+ SB, 7
– SA, 5
+ SAG, 8
– SB, 7
+ SBA, 4
– SBA, 4
+ SBAG, 7
– SBAG, 7

Answer with pruning

# expanded={}
+ S, 7
– S, 7       # expanded={S}
+ SA, 5
+ SB, 7
– SA, 5      # expanded={S,A}
+ SAG, 8
– SB, 7      # expanded={S,A,B}
+ SBA, 4!
– SAG, 8 Non-optimal solution!

What went wrong?
• An expensive path, sa, was expanded before a cheaper one sba could

be discovered because f(sa) < f(sb). • Is the heuristic function h admissible? ‣ Yes. • So why? ‣ h(a) is too low compared to h(b), this makes sa look better. [or equivalently h(b) is relatively too high making sb look worse.] ‣ we see that once, sb is expanded to sba, the f-value drops. • So what can we do? ‣ We need a stronger condition than admissibility to stop this from happening. 18 Monotonicity A heuristic function is monotone (or consistent) if for every two nodes n, and n' which is reachable from n: h(n) ≤ cost(n,n') + h(n')
 With monotone restriction, we have: f(n')   = cost(s,n') + h(n')         = cost(s,n) + cost(n,n') + h(n')         ≥ cost(s,n) + h(n)         = f(n)
 that is, f(n) is non-decreasing along any path. Another interpretation for monotone restriction: real cost must always exceed reduction in heuristic! Monotonicity is stronger condition than admissibility. If h meets the monotone requirement, A* using multiple-path pruning yields optimal solutions. 19 n' n g cost(n, n') h(n) h(n') Finding good heuristics • Most of the work is in coming up with admissible heuristics. • A common approach is to solve a less constrained (simpler) version of the problem. • Good news: usually admissible heuristics are also consistent. • Even inadmissible heuristics are often quite effective if we are OK with sacrificing optimality to some degree (or when we have no choice). • In fact a known hack is to use a * h(n) where h is admissible and a > 1
(i.e. create an inadmissible heuristic) in order to save more time (but
lose optimality).

• [In COSC367 programming exercises we do not use inadmissible
heuristics.]

20

Example heuristic in 8-puzzle

21

§ Number of tiles
misplaced?

§ Why is it admissible?

§ h(start) = 8 Average nodes expanded when optimal path has length…
…4
steps

…8 steps …12 steps

LCFS 112 6,300 3.6 x 106
A* – TILES 13 39 227

Example heuristic in 8-puzzle (cont’d)

22

§ What if we had an easier
8-puzzle where any tile
could slide any one
direction at any time?

§ Total Manhattan distance

§ Why admissible?

§ h(start) = 3 + 1 + 2 + … =
18

Average nodes expanded when
optimal path has length…
…4
steps

…8 steps …12 steps

A* – TILES 13 39 227
A* – MAN-HATTAN 12 25 73

Best heuristic?

How about using the actual cost as a heuristic?

– Would it be a valid heuristic?

– Would we save on nodes expanded?

– What’s wrong with it?

Choosing a heuristic: a trade-off between quality of estimate
and work per node!

23

Dominance relation

24

Other search strategies

25

Bidirectional search
• Idea: search backward from the goal and forward from the start simultaneously.

• Need to be able to generate the reverse graph (incoming arcs).

• Need to make sure the frontiers meet.

• Can be used with BFS, LCFS, or A*.

• This wins as 2bd/2 ≪ bd. This can result in an exponential saving in time and
space.

26

Bounded depth-first search
• A bounded depth-first search takes a bound (cost or depth) and does not expand paths

that exceed the bound.

– explores part of the search tree

– uses space linear in the depth of the search.

• Which shaded goal will a depth-bounded search find first? [Consider bounds 0, 1, 2, …]

27

Which shaded goal will a depth-bounded search find first?

Q W

T

U

Y

R

V

c�D. Poole and A. Mackworth 2017 Artificial Intelligence, Chapter 3, Page 42

Iterative-deepening search
• Iterative-deepening search:

‣ Start with a bound b = 0.

‣ Do a bounded depth-first search with bound b

‣ If a solution is found return that solution

‣ Otherwise increment b and repeat.

• This will find the same first solution as what other method?

• How much space is used?

• What happens if there is no path to a goal?

• How wasteful is recomputing paths?
28

Iterative-deepening search: illustration

29

Iterative-deepening search: complexity

30

Iterative Deepening Complexity

Complexity with solution at depth k & branching factor b:

level breadth-first iterative deepening # nodes
1 1 k b
2 1 k � 1 b2
. . . . . . . . . . . .
k � 1 1 2 bk�1
k 1 1 bk

total � bk  bk

b
b�1

⌘2

c�D. Poole and A. Mackworth 2017 Artificial Intelligence, Chapter 3, Page 44