Algorithms Chapter 23 Algorithms Sequential Parallel And Distributed Heuristic Search Strategies Glance Table Contents

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

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