19-09-2012, 10:54 AM
Heuristic Search
Heuristic.ppt (Size: 145 KB / Downloads: 166)
Generate-and-Test
Algorithm
Generate a possible solution.
Test to see if this is actually a solution.
Quit if a solution has been found.
Otherwise, return to step 1.
Exhaustive generate-and-test.
Heuristic generate-and-test: not consider paths that seem unlikely to lead to a solution.
Plan generate-test:
- Create a list of candidates.
- Apply generate-and-test to that list.
Simple Hill Climbing
Algorithm
Evaluate the initial state.
Loop until a solution is found or there are no new operators left to be applied:
- Select and apply a new operator
- Evaluate the new state:
goal quit
better than current state new current state
Steepest-Ascent Hill Climbing (Gradient Search)
Algorithm
Evaluate the initial state.
Loop until a solution is found or a complete iteration produces no change to current state:
- SUCC = a state such that any possible successor of the
current state will be better than SUCC (the worst state).
- For each operator that applies to the current state, evaluate
the new state:
goal quit
better than SUCC set SUCC to this state
- SUCC is better than the current state set the current
state to SUCC.
Hill Climbing: Conclusion
Can be very inefficient in a large, rough problem space.
Global heuristic may have to pay for computational complexity.
Often useful when combined with other methods, getting it started right in the right general neighbourhood.
Simulated Annealing
A variation of hill climbing in which, at the beginning of the process, some downhill moves may be made.
To do enough exploration of the whole space early on, so that the final solution is relatively insensitive to the starting state.
Lowering the chances of getting caught at a local maximum, or plateau, or a ridge.
Physical Annealing
Physical substances are melted and then gradually cooled until some solid state is reached.
The goal is to produce a minimal-energy state.
Annealing schedule: if the temperature is lowered sufficiently slowly, then the goal will be attained.
Nevertheless, there is some probability for a transition to a higher energy state: e-E/kT.