boostorg / boostorg/graph

Any interest in Nearest Neighbor greedy tour algorithm and/or cleaned up metric_tsp_approx?

Open
#448 15 comments 2 reactions 0 assignees View on GitHub
algorithm generator
Dominant language
C++
Stars
392
Forks
239
Avg merge
1d 11m
Merged PRs (30d)
20

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 :-)

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.