boostorg / boostorg/graph

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

未关闭
#448 15 条评论 2 个 reaction 已指派 0 人 在 GitHub 查看
algorithm generator
主要语言
C++
星标
392
派生
239
平均合并
1 天 11 分钟
30 天内合并 PR
20

描述

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

贡献指南

打开贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。