Week 4: Local Search & Logical Agents Flashcards
Properties of Minimax search
Complete: Yes, if tree is finite
Optimal: Yes, against an optimal opponent.
Time: O(b^m)
Space: O(b^m)
Properties of the α–β algorithm
With “perfect ordering,” time complexity = O(b^m/2 )
Hill-climbing search
its a loop that continuously moves in the direction of increasing value
It terminates when a peak is reached
Hill-climbing chooses randomly among the set of best successors, if there is more
than one.
* Hill-climbing a.k.a. greedy local search
Example of hill climbing
- 8-queens problem (complete-state formulation).
- Successor function:
- move a single queen to another square in the same
column. - Heuristic function h(n):
- the number of pairs of queens that are attacking each
other (directly or indirectly).
Drawbacks of hill climbing algorithms
Ridge: sequence of local maxima difficult for greedy algorithms to navigate
Plateau: an area of the state space where the evaluation function is flat
Hill-climbing variations
Stochastic hill climbing
* Random selection among the uphill moves.
* The selection probability can vary with the steepness of the uphill move.
- First-choice hill climbing
- Variant of stochastic hill climbing that generates successors randomly until a
better one is found. - Random-restart hill climbing
- Tries to avoid getting stuck in local maxima
Simulated annealing
Escape local maxima by allowing “bad” moves
The simulated annealing algorithm, a version of stochastic hill climbing
some downhill moves are allowed
Simulated Annealing is an algorithm which yields both efficiency and completeness.
Genetic
algorithms
Typically applied to:
* discrete optimisation
Attributed features:
* not too fast
* good heuristic for combinatorial problems
Genetic Algorithms –
Pros and Cons
Pros
* Faster (and lower memory requirements) than searching a very large search
space
Cons
* Randomised – not optimal or even complete
