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.