Solution to Travelling Salesman Problem?

Question

I was wondering if this is a solution to the TSP problem. For a set of $n$ points on the plane, the number of 'roads' in the plane such that there is a road between every point is $n\Bbb C 2$ = $n^2-n \over 2$

The total number of possible paths which connect all the points together is $n!$.

The Algorithm is as such:

*Assign weights(the length of the roads) to each road.

*Calculate the minimum spanning Tree for the graph (Algorithms exist to calculate in linear time.)

*Between the two end(free) vertices of the MST take the road.

*The cycle formed thus is the solution.

Answer 1

The weights of the edges need not be their lengths. In the TSP they are just costs - perhaps the salesman needs to take air fare into account.

Counterexample: suppose the cities are at the vertices of an equilateral triangle together with one city at the center. Then suppose the cost of traveling from the center to each of the three vertices is $0$ (or some small number if you like) while the cost of traveling along an edge is $1$. Then the MST is the graph consisting of the three spokes from the center.

The cheapest way for the salesman to visit all the cities is to go back and forth to the center. If she must travel in a cycle, use two edges of the triangle and two spokes. Neither of these is built from the spanning tree using your algorithm.

Answer 2

It is true that the total weight of a minimum spanning tree gives us a lower bound on the minimum weight of a Hamiltonian tour in a graph. However, it also easy to find graphs for which a minimum spanning tree need not be a Hamiltonian tour. Consider e.g. any $n$-ary wheel graph for which the weight of each spoke is $1$ and every other edge has weigh $2$. The minimum spanning tree will have total weight $n-1$, whereas a minimum weight Hamiltonian tour must have total weight greater than $n-1$, as it will need to use at least one edge that is not a spoke.

The subgraph mentioned in the question, that is, a spanning tree together with an additional vertex connected to the tree by two edges, is what is known as a 1-tree. A classic paper by Held and Karp from 1970 shows a connection between 1-trees and Hamiltonian tours and shows how this leads to a branch-and-bound algorithm for searching for Hamiltonian tours below a given bound.

Moreover, there is a well-known approximate algorithm for solving the so-called metric Travelling Salesman Problem using minimum spanning trees. The metric TSP is one in which one only considers weight functions that satisfy the triangle inequality. See e.g. https://people.orie.cornell.edu/dpw/orie6300/Recitations/Rec12.pdf for more.

Answer 3

I think that if one nearest path for any one point is calculated. İt can be calculated in polynomial time.

1. Line is generated with these shortest lines.
2. Then all line's vertices combine with their nearest other line vertices.
3. İf one point have $2$ or more nearest another point. (İt can be maximum $6$ because $\frac{2\pi}{6} = 60^{\circ}$. Therefore more than $6$ equal nearest another point generates in plane. Smaller than $60^{\circ}$ triangle generates for other two points a nearest line between them therefore one point have maximum $6$ equal nearest point.)

İn the end. We assume that all nearest points are one group. Then calculated nearest two points for these group. One nearest for generating line for exiting from this group another for generating line for intaking from this group. These steps calculates in polynomial time for TSP solution.