Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
Algorithms: Sequential, Parallel and Distributed 1-1
Chapter 23
Heuristic Search Strategies
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Algorithms: Sequential, Parallel and Distributed 1-2
Lecture Notes
Overview
In Chapter 23 we discuss various heuristic search strategies that are used in artificial
intelligence and game theory. We begin by discussing the 8-puzzle game, which is nice way to
motivate the discussion of A* search that follows. We define what is meant by a monotone
heuristic, and show that the (first) goal found by A* search is optimal. We then describe the
least cost branch-and-bound design strategy. We finish the chapter with a discussion of game
trees, and present an algorithm for determining the value of a given game using the minimax
strategy, this value being the outcome of the game assuming optimal play.
Chapter Objectives
After completing the chapter the student will know:
• The definitions of A-search and A*-search, and that A*-search always terminates by
finding an optimal path to a reachable goal (if one exists). Moreover, the first goal reached
by A*-search is always optimal, which is not necessarily the case for A-search
• The definition of monotone heuristic and its role in A* search
determine the value of a given game given optimal play
Instructor Notes
The material in this chapter can be covered anytime after the material in Chapter 10 on
backtracking and branch-and-bound has been discussed. However, it may be best to have
already covered Dijkstra’s shortest path algorithm given in Chapter 12, since this algorithm is a
special case of A*-search.
Algorithms: Sequential, Parallel and Distributed 1-3
Solutions to Selected Exercises
Section 23.2 8-Puzzle Game
23.1 In the following figure for the first three levels of the state-space tree generated by
breadth-first search for the 8-Puzzle game, we prune repeated states.
23.2 We show that a single movement (left, right, up, down) of the empty space tile n2
changes the parity of both
=
=
2
1
)(
n
k
kLt
and i + j, where (i,j) is the position of the empty space.
First note that it is obvious that the parity of i + j changes, since the parity of either i or j
changes when the empty space is moved, but not both. Suppose that the empty space moves
Algorithms: Sequential, Parallel and Distributed 1-4
odd, so that exactly one of |A| and |B| must be odd. It follows that that parity of t changes. On
the other hand, if n is odd, then
1−= nBA
is even, so that – |A| + |B| has even parity. It
Section 23.3 A*-Search
23.3 We show that if h is a monotone heuristic, then h(v) is a lower bound of the cost of the
shortest path from v to a (nearest) goal by induction on the number of edges τ(v) from v to a
nearest goal.
23.4 We prove that the f-values of the vertices dequeued by an A*-search using a monotone
heuristic are nondecreasing by induction on the kth vertex dequeued.
Basis step: k = 1. Trivial.
23.5 In the following pseudocode for an A*-search using a heuristic that is not necessarily
monotone, the modified breadth-first out-directed search is a variant of ordinary breadth-first
out-directed search where only vertices that are in the previously generated tree or in the queue
Q are considered.
procedure A*-Search(D,c,r,GoalSet,h,T)
enqueue all vertices in the out neighborhood of r.
while Q is not empty do
dequeue vertex v in Q with minimum priority value f(v)
add vertex v to T using parent pointer
if v GoalSet then
endif
endif
endfor
perform a modified out-directed breadth-first search root at v, updating priority value of
all vertices w reached that are either in Q or in T if shortest paths to them now exist via
23.6 The cost c(v,w) of an edge in the state-space graph is one. Also, if v and w are adjacent in
the state-space graph, then the number of tiles not in their correct position in w can be at most
23.7 The cost c(v,w) of an edge in the state-space graph is one. Also, if v and w are adjacent
in the state-space graph, then state v can be transformed into state w by a horizontal move of
one tile x by one position, or a vertical move of one tile x by one position (but not both).
23.8 In this and the next exercise, a “move” is interpreted as dequeuing a state and expanding
its children in the state-space tree. When drawing the state-space tree, we assume that
23.9 Similar to the previous exercise, we show that portion of the state-space tree generated
by A*-search for three dequeuings, but this time using the Manhattan-based heuristic. The
23.12 Suppose we reach a goal x in A*-search that has strictly larger cost than the cost of a
path Pr,v to a goal v. Consider the node y adjacent to x on the path Pr,x generated by A*-search
when x was added to the tree by A*-search. Also, let w be the last point on the path Pr,v that is
23.13 Suppose d1 > d2 > … . > dk are the denominations of the coins, and that C is the amount
of change required. Given a problem state v, if r(v) is the remaining change required, h(v) is
computed by using as many coins of denomination d1 as possible, then as many coins of
denomination d2 as possible, and so forth, as long as we do not exceed r(v). It is important to
note that we do not proceed to the next denomination di+1 if we can’t use a coin of
m
iii nnn +++ ...
21
(the first
1
i
n
terms involve
1
i
d
, the next
2
i
n
terms involve
2
i
d
, and so forth). In the computation
of h(v), note that if d1 > r(v), then h(v) = 0, so clearly h(v) is a lower bound for
m
iii nnn +++ ...
21
in this case. Suppose, then, that strictly positive integers m1, m2, …, mj have
23.15 The heuristic required for the variation of the coin-changing problem in which we have
a limited number of coins of each denomination (the number of coins of each denomination is
23.16 It turns out that the same portion of the state space tree as shown in Figure 10.13 is
generated by least-cost branch-and-bound as by backtracking. The value of c(v) used as the
priority of a node v is the same as what was called LoBd in Figure 10.13. What is new here is
whether or not a given node is enqueued, and the fact that the current value of UB is sometimes
different when a node is reached by backtracking then it is when it is generated by least-cost
23.19 a) That c(r) is a lower bound for the minimum cost of a tour follows from the fact that
each entry in the cost matrix C = (cij) is not reduced by more than its value in the reduced cost
matrix Cr. More precisely, let mr(i) denote the minimum value in the ith row, i = 0, …, n – 1.
Then, let mc(j), j = 0, …, n – 1denote the minimum value in the jth column of the row-reduced
matrix (where each entry in row i has been reduced by mr(i), i = 0, …, n – 1 ). Then it is clear
−
1
=
0
i
23.22
Algorithms: Sequential, Parallel and Distributed 1-11
23.26 Assuming the first player is X in the 3 × 3 × 3 cube, the winning strategy is given in the
following figure, where the cells in the cube are labeled by X or O, as well as the number of the
move that player X or player O makes. In particular, the first move of player X is to take the
23.23
procedure ABNodeValue(X, NumLevels, ParentValue, Value, i) recursive
Input: X (a node in the game tree having children C1,C2, . . . , Ck),
NumLevels (number of levels to search)
ParentValue (lower bound on value of parent of X)
Value ← –ValueC
i ← 1
for j ← 2 to k do
if Value ≥ –ParentValue then //cutoff
return
