Any interest in Nearest Neighbor greedy tour algorithm and/or cleaned up metric_tsp_approx? #448
Description
Hi,
I have written a Nearest Neighbor greedy tour heuristic w/ example and test code. I think this heuristic is a good pairing to the metric_tsp as it has less constraints on the graph/edge weight types (no triangle inequality required), does not require a global MST, uses less memory while running due to local greedy characteristic, and runs much faster albeit with the caveat that it does not have a defined upper bound on tour efficiency. However, typical results are very strong and it is a good starting point to the more advanced k-opt TSP algorithms (e.g. LKH) that require a starting tour.
template < typename VertexListGraph, typename WeightMap,
typename VertexIndexMap, typename TSPVertexVisitor >
void nearest_neighbor_tour_from_vertex(const VertexListGraph& g,
typename graph_traits< VertexListGraph >::vertex_descriptor start,
WeightMap weightmap,
VertexIndexMap indexmap,
TSPVertexVisitor vis)
I also have cleaned up my original tsp_metric_approx code significantly, addressing all of Andrew Sutton's (who helped tremendously) original comments. I've also improved the test and example code for it.
I am also considering implementing Christofides 3/2 solution O(v^3) due to MWPM because it has the interesting characteristic of not requiring a complete graph as well as a lower upper bound solution, but I wanted to write a fast starter for LK first.
Let me know if there is any interest in either of these (cleaned up metric, new nearest neighbor). I haven't contributed to Boost BGL in nearly 20 years and I know much has changed, but I had interest over the holidays :-)