(some diagrams are included in the word document that are not posted on the web page, the diagrams did not convert all that great)

• Heuristic search

This is used in the following situations

1. Game Playing (1)

2. Branch & Bound (2)

3. Generate & Test

1. Genetic Algorithms

Problem

You have a four-gallon jug and a three-gallon jug and the goal is to come up with exactly two gallons of water.

Directed Graph (This is the best way to show the solution for this problem)

(0 0) à (4 0) (0 3))

(4 0) à (( 4 3) (0 0) (1 3))

(0 3) à ((4 3) (3 0) (0 0))

(1 3) à (1 0) (4 3))

1. Make important things clear /explicit
2. Expose natural constraints
3. Must be complete
4. Concise
5. Transparent / Easily understood
6. Information needs to be retrieved / stored quickly
7. Detail suppressed
8. Should be computable using existing procedures

There are four items a farmer, wold, goose, and corn. The farmer can only take one item across the river at a time.

Rules…

1. the wolf will eat the goose if left alone
2. the goose will eat the corn if left alone

F = Farmer

W = Wolf

G = Goose

C = Corn

R = River

Step One: F - W – G - C – R

Step Two: W – C – R – F – G

Step Three: F – W – C – R – G

Step Four: C – R – F – W – G

Step Five: F – C – G – R – W

Or

Step Four: W – R – F – G – C

Step Five: F – G – W – R – C

Step Six: G – R – F – W – C

Step Seven: F – G – R – W – C

Step Eight: R – F – W – G – C

1. Need to have forward motion
2. Needs to be systematic

Heuristics – trade speed for completeness

Any path?

Shortest path?

Any Path?

1. Depth First Search
2. Hill Climbing
3. Best First Search
4. Breadth First Search
5. Beam Search

S à A,B

A à S,B,F

B à S,A,C

F à A,C

C à B,F

1. Add root to queue of partial paths
2. Until queue is empty or goal is attained

If the first queue element equals the goal do nothing

Else remove the first queue element and add its children to the front of the queue of the partial paths

3. If the goal is attained success will be announced, if failure it will be announced

((S))

((A S) (B S))

((B A S) (F A S) (B S))

(( C B A S) (F A S) (B S))

(( F C B A S) (F A S) (B S))

(S A B C F)

1. Add root to queue of partial paths
2. Until queue is empty or goal is attained

If the first queue element equals the goal do nothing

Else remove the first queue element and add its children to the rear of the queue of the partial paths

3. If the goal is attained success will be announced, if failure it will be announced

((S))

((A S) (B S))

((B S) (B A S) (F A S))

((B A S) ( F A S) (A B S) (C B S))

((F A S) (A B S) (C B S) (C B A S))

(S A F)

When this works and when it does not?

• depth first search is good with no dead ends, this is good for tall skinny trees
• breadth first is not good to use for short fat trees

1. Add root to queue of partial paths
2. Until queue is empty or goal is attained

(3) If the goal is attained success will be announced, if failure it will be announced

((S))

((A S) (B S))

((F A S) (B A S) (B S))

(S A F)

Weakness

1. foothills – goal is to go up, it does not like to go back down after it has gone up
2. plateau
3. Ridge Problem

(sort `(1 2 3 4) ` >)

(4 3 2 1)

(sort ‘(1 2 3 4) ‘ <)

(sort ‘(1 2 3 4) ‘(closerp)) ; line 113 on code handout

• this is not illustrated in a lot of text books, we will touch on it briefly

Look at n best paths to the goal. ( you pick any number you want for n)

In this example we picked the number three. Here we look at the first level from left to right all the way across and then move to the next level and then the next.

((S))

((A S) (B S))

((F A S) (C B S) (A B S) (B A S)

(S A F)

1. Root on the queue
2. Until the queue is empty or the goal in front

If front (Q) equals goal then do nothing

Else remove first node and add the children to the front and then sort the queue by the remaining distance.

3. If goal on the queue then success.

• sort the whole queue or just the new children?
• Breadth first is shorter
• You should use more knowledge on search instead of working on efficiency

((S))

((A S) (B S))

((F A S) (B A S) (B S))

(S A F)

British museum search

• given enough time monkey’s with typewriters can reproduce all info in the museum.
• Delineate everything and solve
• Based on cost to get where you are at.
• The current path cost

1. Root on the queue
2. Until queue empty or goal is in the front

If front (Q) equals goal then do nothing

Else remove the first node and sort the queue by cost

3. If goal on queue then success else failure

((S))

((A S) (B S))

((B S) (B A S) (F A S))

((A B S) (F A S) (C B S) (B A S))

((B A S) (F A S) (C B S) (F A B S))

((F A S) (F C B S) (F A B S) (C B A S))

(S A F)

1. Root in queue
2. Until queue empty or goal in the front

If front (Q) equals goal then do nothing

Else remove first root and add the children to the front sort queue by the cost estimator

3. If goal is on queue then success

((S))

((A S) (B S))

((F A S) (B S) (B A S))

(S A F)

1. Root in queue
2. Until queue empty or goal in the front

If front (Q) equals goal then do nothing

Else remove first root and add the children to the front sort queue and use the cost estimator and remove duplicates

3. If goal is on queue then success

Else failure

((S))

((A S) (B S))

((B S) (F A S))

((A B S) (F A S) (C B S))

((C B S) (F A S))

((F A S))

((S A F))

• This one is a little dangerous to use.

1. Root in queue
2. Until queue empty or goal in the front

If front (Q) equals goal then do nothing

Else remove first root and add the children to the front sort queue using cost estimation and remove duplicate paths

3. If goal is on queue then success

Else failure

((S))

((A S) (B S))

((F A S) (B S))

((F A S))

• British Museum Search
• only good for small searches
• this one is no good, we need to get rid of this
• Branch & Bound
• Works good on big trees if bad paths turn bad quickly.
• Branch & Build with "guess" underestimator
• estimate must be reliable
• it must be longer and can not equal the actual value.
• Branch & Bound with Dynamic Programming and under estimator
• This is best used when there are redundant paths
• A*
• Best used when underetimator can be defined and there are redundant paths.