11-07-2012, 01:28 PM
Local search algorithms
Local search algorithms.pdf (Size: 243.12 KB / Downloads: 215)
Iterative improvement algorithms
In many optimization problems, the path to a goal is irrelevant;
the goal state itself is the solution
Then state space = a set of goal states
nd one that satises constraints (e.g., no two classes at same time)
or, nd optimal one (e.g., highest possible value, least possible cost)
In such cases, can use iterative improvement algorithms;
keep a single \current" state, try to improve it
Constant space
Suitable for online as well as oine search
Traveling Salesperson Problem
Given a complete graph (edges between all pairs of nodes)
A tour is a cycle that visits every node exactly once
Find a least-cost tour (simple cycle that visits each city exactly once)
Iterative improvement:
Start with any tour, perform pairwise exchanges
Local beam search
Not the same as k parallel searches
Searches that nd good states will recruit other searches to join them
Problem: often all k states end up on same local hill
Stochastic beam search:
choose k successors randomly, biased towards good ones
Close analogy to natural selection