Any interest in Nearest Neighbor greedy tour algorithm and/or cleaned up metric_tsp_approx?
メンテナーはふだん 1 日以内に返信
まだ誰も着手していません。
評価
調査の方向性
まず、既存の metric_tsp_approx の実装とそのサンプルおよびテストコードを確認し、提案されている nearest_neighbor_tour_from_vertex エントリーポイントと比較します。コーディングの前に、プロジェクトがどのアルゴリズムまたはクリーンアップを受け入れる予定なのかを確認してください。完了とするには、合意されたスコープに加えて、選択した変更に対する統合済みのサンプルとテストが必要です。
索引モデルが issue の本文から書いたものです。
説明
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 :-)
- 主要言語
- C++
- スター
- 399
- フォーク
- 247
- 平均マージ
- 1日 9時間
- マージ済み PR（30日）
- 40
環境構築
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートあり
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
boostorg/graph のほかの issue
-
Good first issues: start contributing to Boost.Graph here再び着手できるかも @andreacassioli が 8 日前に担当しましたが、オープン中のプルリクエストはありません。 オープンbeginner friendly
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
boostorg/graph#593 · コメント 47 件 ·
メンテナーはふだん 1 日以内に返信
-
algorithm beginner friendly priority: high
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
boostorg/graph#231 · コメント 2 件 ·
メンテナーはふだん 1 日以内に返信
-
Trivial Minimum Cycle Ratio Failing対応中かも @Becheler が 11 日前に担当しました。 オープンalgorithm
難易度 3/5 1〜2日 初心者へのやさしさ 68/100
boostorg/graph#599 · コメント 3 件 · 担当者 1 名 ·
メンテナーはふだん 1 日以内に返信
-
難易度 5/5 1週間以上 初心者へのやさしさ 30/100
メンテナーはふだん 1 日以内に返信
-
Implementing personalized PageRank for graph node scoring.対応中かも @Becheler が 146 日前に担当しました。 オープンalgorithm
boostorg/graph#493 · コメント 22 件 · リアクション 1 件 · 担当者 2 名 ·
メンテナーはふだん 1 日以内に返信
似ている issue
-
難易度 2/5 1〜3時間 初心者へのやさしさ 84/100
CachyOS/New-Cli-Installer#50 ·
-
難易度 1/5 1〜3時間 初心者へのやさしさ 90/100
Qiskit/qiskit-aer#2482 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 78/100
メンテナーはふだん 1 日以内に返信
-
content good first issue
難易度 1/5 1時間未満 初心者へのやさしさ 95/100
cpinitiative/usaco-guide#6699 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 65/100
codepointerapp/codepointer#231 ·