Chapter 3 : Heuristic Search Techniques

Which search procedures work (given a problem)?

Which procedures are efficient?

Which procedures are easy to implement?

Which is best to think about?

Searching a path: efforts are in

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

Weak Methods of control: (weak but provide framework)

Depth-first

Breadth-first

Generate & Test

  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 the generation is done randomly, we get the British Museum algorithm. (monkeys at keyboards writing Shakespeare if enough time)

DENDRAL - classification of structure of organic compounds through mass spectroscopy and NMR uses plan-generate-test (where planning uses constraint satisfaction with backtracking) (read classnotes for next class)

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.)

Hill-Climbing

g&t with a closeness heuristic function need an adjustable parameter and a way to measure

  1. evaluate initial state, goal? return and quit, else

  2. generate proposed solution (apply rules). Call set A

  3. For each in A

    1. test if goal state
    2. 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)

    this is "steepest-ascent" (gets best rather than first that is better than the previous)

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)

Solutions: 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)

notice with each advancement we get closer to a "shorter" answer, but remember to consider the time to calculate and sort

see page 74

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)

* 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*

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 (wnat 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

still no focus....want to constrain space

Constraint Satisfaction

Goal: to discover some problem state that satisfies a given set of constraints

- fixed limits on time, cost, material

- not new search method

constrains space by augmenting description of state with list of constraints

Coursenotes: student and MOLGEN

page 89-94 Cryptarithmetic problem

SEND

+MORE

MONEY

page 98 # 1,3,5,6,12,14 Closeness paper next