CH 4

Question 1

Greedy Best First Search

Answer 1

tries to expand the node that is closest to the goal

Question 2

Straight Line Distance

Answer 2

shortest distance between two points.

Question 3

A* Search

Answer 3

f(n) = g(n) + h(n) where g(n) is the cost to reach the node and h(n) is the estimated cost to get from the node to the goal

Question 4

Admissible Hueristic

Answer 4

h(n) never overestimates the cost to reach the goal

Question 5

Consistency (Monotonicity)

Answer 5

a huerisitic h(n) is consistent if. for every node n and every successor n’ of n generated by an action a. the estimated cost of reaching the goal from n is no greater than the step cost of getting to n’

Question 6

Triangle Inequality

Answer 6

stipulates that each side of a triangle cannot be longer than the sum of the other two sides

Question 7

Pruned

Answer 7

a subtree can be ignored or pruned because h(n) is admissible

Question 8

Recursive best-first search

Answer 8

is a simple recursive algorithm that attempts to mimic the operation of standard best-first search but using only linear space.

Question 9

IDA*

Answer 9

difference between IDA* and Iterative deepening is that rather than using the depth as the cutoff it uses f(n) = g(n) + h(n)

Question 10

SMA*

Answer 10

Simple memory bound A* expands the best leaf until memory is full at which time it drops the worst leaf

Question 11

Effective Branching Factor

Answer 11

the total number of nodes generated by A* for a particular problem is N. and the solution depth is d. then b* is the branching factor that a uniform tree of depth d would have to have in order to contain N + 1 nodes.

Question 12

Relaxed Problem

Answer 12

a problem with fewer restrictions on the actions

Question 13

Hill Climbing

Answer 13

a loop that continually moves in the direction of increasing value. that is. uphill. It terminates when it reaches a peak where no neighbor has a higher value

Question 14

Local Maxima

Answer 14

a local maximum peak that is higher than each of its neighboring states

Question 15

Plateaux

Answer 15

a plateau is an area of the state space landscape where the evaluation function is flat.

Question 16

Stochastic Hill Climbing

Answer 16

chooses at random from among the uphill moves

Question 17

First-Choice Hill Climbing

Answer 17

implements stochastic hill climbing by generating successors randomly until one is generated.

Question 18

Random Restart Hill Climbing

Answer 18

conducts a series of hill climbings from random restarts

Question 19

Simulated Annealing

Answer 19

pick a move. then make a random move. It the random move is an improvement it is always accepted

Question 20

Local Beam Search

Answer 20

keeps track of k states rather than just 1. If any state is the goal then it halts otherwise it generates 8 new states (useful information is passed among the k parallel search threads)

Question 21

Genetic Algorithms

Answer 21

GAs begin with a set of k randomly generated states called the population. (crossover. mutation)