We now describe a local search heuristic for the traveling salesman problem.
We've already seen the main idea of the local search algorithm,
but let me describe it once again.
So to solve an optimization problem with a local search heuristic
means the following, we usually start with some initial solution s,
then we'll repeat the following procedure.
For a current solution s, we look into some neighborhood of this solution and
we try to find a solution in this neighborhood,
if the solution [INAUDIBLE] which is better than the current solution s.
If there is some solution such a solution s', and we replace s with s' and
repeat this and we stop when s is the best one in its neighborhood.
So first of all, the first thing to note is that this algorithm might
return a sub optimal solution because the only thing which we can guarantee about
the return solution it is that it is the local optimum, not the global optimum.
So namely it is optimum in its neighborhood.
But also, the quality and the running time of this
algorithm depends on how we define the neighborhood actually.
For example, we might define the neighborhood of some solution
as the search of all possible solutions.
Then this algorithm in one iteration will need to
go through all possible candidate solutions and to find the best one.
So, this is algorithm will be actually the same as the brute force algorithm.
How do we define the neighborhood in case of the traveling salesman problem?
Well, for this we first need to define a distance between two solutions.
We call that, in case of traveling salesman,
a candidate solution is a cycle that visits each vertex exactly once.
So assume that we have two stage cycles, s and s'.
We say that the distance between them is at most d, if we can get s'
from s by first deleting the edges, at most, the edges from s, and
then adding probably some other d edges to the resulting structure, okay?
Then we can define a neighborhood, again, as in the case with algorithm,
namely, we define a neighborhood of s with radius r as all the cycles
that we can obtain from s by changing it's most r edges.
To give you a specific example, consider the following graph
containing of eight vertices, and, again, we assume that the vertices here
are just points on a plane and the distance between any two vertices
is just equal to the distance between the corresponding points on a plane.
Assume that our initial solution looks as follows, It is clearly suboptimal but
just changing the two edges in this solution makes it optimal.
So instead of using these three edges, we use the following two edges.
This gives us an optimal solution.