TSPMetric (JGAlgo - Parent 0.2.0 API)

All Known Implementing Classes:

TSPMetricMatchingAppx, TSPMetricMSTAppx
```
public interface TSPMetric
```
Metric Traveling Salesman Problem (TSP) algorithm.
Given a list of points, the traveling salesman problem asking what is the shortest tour to visit all points. The metric version of TSP is a special case in which the distances satisfy the triangle inequality and the distances are symmetric.
The problem itself is NP-hard, but various approximation algorithms exists.

Author:

Barak Ugav

See Also:

Wikipedia

Method Summary

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

- Method Detail
  - computeShortestTour
```
Path computeShortestTour(Graph g,
                         WeightFunction w)
```
    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.
    
    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