Package com.jgalgo

Class TSPMetricMatchingAppx

java.lang.Object

com.jgalgo.TSPMetricMatchingAppx

All Implemented Interfaces:

TSPMetric

public class TSPMetricMatchingAppx
extends Object

TSP \(3/2\)-approximation using maximum matching.

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

Based on 'Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem' by Nicos Christofides (1976).

Author:

Barak Ugav

Constructor Summary

Constructors

Constructor	Description
TSPMetricMatchingAppx()	Create a new TSP \(3/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

TSPMetricMatchingAppx

public TSPMetricMatchingAppx()

Create a new TSP \(3/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