boostorg / boostorg/graph

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

オープン
#448 コメント 15 件 リアクション 2 件 担当者 0 名 GitHub で見る
algorithm generator
主要言語
C++
スター
392
フォーク
239
平均マージ
1日 11分
マージ済み PR(30日)
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 を短くまとめたダイジェスト。