Bai giai tri tue nhan tao tut 3

TRƯỜNG ĐẠI HỌC BÁCH KHOA TP.HCM

Khoa Khoa học & Kỹ thuật Máy tính

TUTORIAL SESSION 3

HEURISTIC SEARCH AND GAME PLAYING

Question 1: Prove each of the following statements: (refer wikipedia for uniform-cost search algorithm)

a. Breadth-first search is a special case of uniform-cost search.

b. Breadth-first search, depth-first search, and uniform-cost search are special cases of best-first

search.

c. Uniform-cost search is a special case of A* search.

Solution:

a. When all step costs are equal, g(n) ~ depth(n), so uniform-cost search reproduces breadth-first

search.

b. Breadth-first search is best-first search with f(n) = depth(n).

Depth-first search is best-first search with f(n) = - depth(n).

Uniform-cost search is best-first search with f(n) = g(n).

c. Uniform-cost search is A* search with h(n) = 0.

Question 2:

Consider the n blocks world in which only one block can be on another block or on the table. And,

possible actions including picking up a block from the table, putting a block down on the table,

stacking a block on another block, and unstacking a block from another block.

Consider the problem of 3 blocks world with start and goal state in Figure 1.

 Draw the search tree resulting from using best-first search with the heuristic function as the

number of blocks not in the correct place as an estimate of the remaining distance to the

goal. For example, the heuristic value for start state is 2 since blocks A and C are not in the

correct place (but block B is) relative to the goal state.

 Repeat previous question with steepest ascent hill climbing. Compare the number of

expanded nodes.

 Draw the search tree resulting from using A-start with g being the number of operators

executed and h being the same heuristic as about. Give your opinion about this heuristic

function.

Notes:

 In the situation where we can’t decide which node to expand next. Choose it randomly.

 If the search tree resulting from using heuristic function, write node’s evaluation value beside it.

 Each node of search tree will have the state representation as the node’s label. For example, the