Hacktoberfest 2026: những issue maintainer đã đánh dấu cho tháng Mười, đang mở và phù hợp người mới. Xem issue Hacktoberfest

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

Đang mở
  • Có gì không ổn?
#448 15 bình luận 2 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
5/5
Thời gian dự kiến
Hơn một tuần
Mức phù hợp với người mới
25/100
Loại issue
Tính năng
Độ rõ ràng
Cần làm rõ
Mức độ hoạt động
Ít trao đổi
Công nghệ
cpp
Lĩnh vực
data

Hướng nghiên cứu

Bắt đầu bằng việc xem xét triển khai metric_tsp_approx hiện có cùng mã ví dụ và mã kiểm thử của nó, sau đó so sánh chúng với entry point nearest_neighbor_tour_from_vertex được đề xuất. Trước khi viết mã, hãy xác nhận dự án muốn chấp nhận thuật toán hoặc việc dọn dẹp nào. Công việc chỉ được xem là hoàn tất khi có phạm vi đã thống nhất cùng với các ví dụ và bài kiểm thử tích hợp cho thay đổi được chọn.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

algorithm generator

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

Ngôn ngữ chính
C++
Star
399
Fork
247
Merge trung bình
1 ngày 9 giờ
Pull request đã merge (30 ngày)
40

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của boostorg/graph

Tất cả issue của boostorg/graph

Issue tương tự

Thêm issue về C++

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.