7 - Informed Search

Question 1

Define a heuristic function

Answer 1

Gives the cheapest estimate of getting from n to the goal

for n1 and n2 if h(n1) < h(n2) take h1

require that estimate of getting to goal is 0

Question 2

What is Greedy Search?

Answer 2

Use f(n) = h(n)

Always expand lowest h value

Not complete/optimal - can lead astray

Question 3

What is A* search?

Answer 3

Take into account cost of getting to a node from start node and estimate of getting to goal

f(n) = g(n)+h(n)

Question 4

What is admissibility in heuristics?

Answer 4

A function h is admissible if it never over estimates the true cost of getting to the goal (optimistic)

Question 5

What is consistency in heuristics?

Answer 5

Consistent/monotonic if the estimated cost of getting to goal from n is no greater than the step cost of getting to n’ plus the estimated cost of reaching the goal from n’:

h(n) <= c(n,a,n’)+h(n’)

n is every node
n’ every successor
a action

Question 6

What is the optimality for A* search?

Answer 6

It will give an optimal for graph search if the heuristic is consistent

tree search if the heuristic is admissible

Question 7

What is the effective branching factor?

Answer 7

A measure of efficiency for heuristics.

Expands N nodes and finds solutions at depth d then the EBF is the num of successors of each node having:

• each non-leaf has b successors
• leaf nodes are all at depth d
• Total number of nodes in the tree is N

then N = 1 +b + b^2 + … +b^d

A value of b close to one means search is focussed

Question 8

How can weighted sum improve efficiency?

Answer 8

f(n) = w * g(n) + (1-w)*h(n) where w is a num between 0 and 1

Question 9

What is hill climbing search?

Answer 9

1. choose a start and set c to there
2. search the neighbourhood of c
3. choose best neighbour
4. if best is better than c then update c
5. repeat 2 to 4 until no further improve

Question 10

What are the hill climbing drawbacks?

Answer 10

Local Maxima
Plateaus (flat areas)
Ridges (Long narrow hiltops).

Improved by random restart

Question 11

What is Tabu Search?

Answer 11

Remember the last few visited points using a tabu list (think Taboo)

Steer away from Tabu List items (a queue of fixed length)

Question 12

What is simulated annealing?

Answer 12

Annealing: Process of prepping a material to mould it. Heated then cooled. Particles move randomly but gradually settle

SA is a math model of the process

Question 13

Describe the simulated annealing method

Answer 13

1. t = 0
2. random start point x
3. set y to neighbour of x
4. if y is better xt+1 = y
5. else with probability min(1,1/(e^((f(y)-f(x]t)/T(t)))
6. update t to t+1
7. repeat 3 to 6 until end