Issues in the Design of Search Techniques:

*

Forward search	vs	Backward search
data-driven		goal-driven (assume hypothesis)
discover		verify/deny a conclusion

* Chess: 8 X 8 board, 32 pieces about 10¹²⁰ board positions

- humans don't memorize such lists

- even with computers it is infeasable to consider all

- all are not even legal anyway! (discuss cognitive psych study) (experts and memory)

we need a representation for describing patterns and allowable substitutions
(1)

Heuristic Search Techniques

Which procedures are efficient?

Which procedures are easy to implement?

Searching a path: efforts are in

1. finding possible paths (operators)
2. traversing the path (control)

(2)

Depth-first
Breadth-first

Generate & Test

1. (1) generate a solution
2. test if it is an acceptable goal
3. quit or goto (1)

What does (1) mean. If a "complete" solution must be generated before it is tested than this means exhaustive depth-first search... (at each state, not at goal yet but still don't know if future generation of this path may be successful). If generation done systematically will find a solution eventually, if one exists. If problem space is very large - could take a very long time.

If the generation is done randomly, we get the British Museum algorithm and no guarantee that a solution will ever be found.

British Museum algorithm, a reference to the fact that if a sufficient number of monkeys were placed in front of a set of typewriters and left alone long enough, then their implementation of this algorithm would generate all the books the museum contains. (Monkeys at keyboards writing Shakespeare if enough time)

In a sense, almost all search techniques are a form of generate and test (in pure generate and test, the test responds with only yes or no.)
(3)

Hill-Climbing

1. evaluate initial state, goal? return and quit, else
2. generate proposed solution (apply rules). Call set A
3. For each in A
   
   a. test if goal state
   b. use function to determine which is "closest"
4. Use the best (and must be better than previous)... go to (2)
   (procedure takes one step in each fixed set of directions, moves to the best alternative)
   (procedure stops when node reached where all nodes children have lower values)

Hill climbing is a local method - moves are determined by being better than previous.

What if reach:

1. local maximun (all moves appear to make worse) (sometimes called foothills - in sight of solution)
   
2. plateau (flat - same value)
   
3. ridge (cannot be traversed by single moves)

(4)

Beam Search

breadth-first except only downward from the best 'w' nodes at each level (not exponential...if b is branching factor - wb nodes) ... prunes, may lose goal, not optimal

Best-First Search

Like hill-climbing except

the best available state is selected even if the value is lower than the value of the previous state

in hill-climbing, one move is selected and all others are rejected (never considered unless add backtracking)

(5)

Branch and Bound (Dykstra's shortest path algorithm)

provides an optimal path (heuristic here is length (absolute) ) (distances)

During search, many incomplete paths are encountered
- shortest one is extended one level, creating as many new incomplete paths as branches. Consider these and remaining old ones ... extend shortest path.
- terminate when shortest incomplete path is longer than shortest complete path (ensures optimum)

Example: Shortest distance Start to Goal: Page 1 , Page 2 , Page 3 (I looked it up, there was no more nodes on the S-A-B-C link, hence the C with value 11 ended (not a path to G))

* More knowledge means less search
* Search is seductive.

While involved in many tasks, tuning a search procedure is rarely the right thing to do. More often, the right thing is to improve understanding, thereby reducing the need for search.
weak methods are too general
reduce the search space even more

A*

The A* algorithm, first described in [Hart, 1968; Hart, 1972] is a way to implement best-first search of a problem graph.
See Wikipedia

Uses:

branch and bound		(best) - now
estimate		(promising) - now and later
dynamic programming		(know way (past) -- already better (waste him))

(solution to problem is viewed as the result of sequence of decisions (want optimal))

Dynamic Programming uses principle of optimality

An optimal decision sequence has the property that whatever the initial state and decision are, the remaining decisions must constitute an optimal decision sequence with regard to the state that results from the first decision.

f' =  g + h'		f is heuristic measure of goodness
				g is how good the node is now
				h is how much farther to go to goal
				' means it is an estimate