Tsp (JGAlgo - Parent 0.5.1-SNAPSHOT API)

All Known Implementing Classes:

TspAbstract, TspMetricMatchingAppx, TspMetricMstAppx
```
public interface Tsp
```
Traveling Salesman Problem (TSP) algorithm.
Given a graph, the traveling salesman problem asks what is the shortest tour that visit all the vertices and returns to the starting vertex. The problem itself is NP-hard, but various approximation algorithms exists.
The metric version of TSP is a special case in which the distances satisfy the triangle inequality and the distances are symmetric.

Author:

Barak Ugav

See Also:

Wikipedia

Method Summary

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

- Method Detail
  - computeShortestTour
```
<V,E> Optional<Path<V,E>> computeShortestTour(Graph<V,E> g,
                                                          WeightFunction<E> 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.
    If g is an IntGraph, an optional of IPath is returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.
    
    Type Parameters:
    
    V - the vertices type
    
    E - the edges type
    
    Parameters:
    
    g - a graph containing all the vertices the tour must visit, using its edges
    
    w - an edge weight function
    
    Returns:
    
    an optional of the tour calculated, or an empty optional if no such path was found