Package com.jgalgo

Class TSPMetricMSTAppx

java.lang.Object

com.jgalgo.TSPMetricMSTAppx

All Implemented Interfaces:

TSPMetric

public class TSPMetricMSTAppx
extends Object

TSP $2$-approximation using MST.

An MST of a graph weight is less or equal to the optimal TSP tour. By doubling each edge in such MST and finding an Eulerian tour on these edges a tour was found with weight at most $2$ times the optimal TSP tour. In addition, shortcuts are used if vertices are repeated in the initial Eulerian tour - this is possible only in the metric special case.

The running of this algorithm is $O(n^2)$ and it achieve $2$-approximation to the optimal TSP solution.

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
TSPMetricMSTAppx()	Create a new TSP $2$-approximation algorithm.

Method Summary

Modifier and Type	Method	Description
Path	computeShortestTour(Graph g, WeightFunction w)	Compute the shortest tour that visit all vertices.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

TSPMetricMSTAppx

public TSPMetricMSTAppx()

Create a new TSP $2$-approximation algorithm.

Method Detail

computeShortestTour

public Path computeShortestTour(Graph g,
                                WeightFunction w)

Description copied from interface: TSPMetric

Compute the shortest tour that visit all vertices.

Note that this problem is NP-hard and therefore the result is only the best approximation the implementation could find.

Specified by:

computeShortestTour in interface TSPMetric

Parameters:

g - a graph containing all the vertices the tour must visit, using its edges

w - an edge weight function. In the metric world every three vertices $u,v,w$ should satisfy \(w((u,v)) + w((v,w)) \leq w((u,w))$

Returns:

a result object containing the list of the $n$ vertices ordered by the calculated path