equal
deleted
inserted
replaced
29 #include <lemon/matching.h> |
29 #include <lemon/matching.h> |
30 #include <lemon/euler.h> |
30 #include <lemon/euler.h> |
31 |
31 |
32 namespace lemon { |
32 namespace lemon { |
33 |
33 |
|
34 /// \ingroup tsp |
|
35 /// |
34 /// \brief Christofides algorithm for symmetric TSP. |
36 /// \brief Christofides algorithm for symmetric TSP. |
35 /// |
37 /// |
36 /// ChristofidesTsp implements Christofides' heuristic for solving |
38 /// ChristofidesTsp implements Christofides' heuristic for solving |
37 /// symmetric \ref tsp "TSP". |
39 /// symmetric \ref tsp "TSP". |
38 /// |
40 /// |
39 /// This a well-known approximation method for the TSP problem with |
41 /// This a well-known approximation method for the TSP problem with |
40 /// \ref checkMetricCost() "metric cost function". |
42 /// metric cost function. |
41 /// It yields a tour whose total cost is at most 3/2 of the optimum, |
43 /// It yields a tour whose total cost is at most 3/2 of the optimum, |
42 /// but it is usually much better. |
44 /// but it is usually much better. |
43 /// This implementation runs in O(n<sup>3</sup>log(n)) time. |
45 /// This implementation runs in O(n<sup>3</sup>log(n)) time. |
44 /// |
46 /// |
45 /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and |
47 /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and |
52 /// (i.e. creates shortcuts) assuming that the triangle inequality holds |
54 /// (i.e. creates shortcuts) assuming that the triangle inequality holds |
53 /// for the cost function. |
55 /// for the cost function. |
54 /// |
56 /// |
55 /// \tparam CM Type of the cost map. |
57 /// \tparam CM Type of the cost map. |
56 /// |
58 /// |
57 /// \warning \& CM::Value must be signed type. |
59 /// \warning CM::Value must be a signed number type. |
58 template <typename CM> |
60 template <typename CM> |
59 class ChristofidesTsp |
61 class ChristofidesTsp |
60 { |
62 { |
61 public: |
63 public: |
62 |
64 |
193 } |
195 } |
194 |
196 |
195 /// \brief Returns a const reference to the node sequence of the |
197 /// \brief Returns a const reference to the node sequence of the |
196 /// found tour. |
198 /// found tour. |
197 /// |
199 /// |
198 /// This function returns a const reference to the internal structure |
200 /// This function returns a const reference to a vector |
199 /// that stores the node sequence of the found tour. |
201 /// that stores the node sequence of the found tour. |
200 /// |
202 /// |
201 /// \pre run() must be called before using this function. |
203 /// \pre run() must be called before using this function. |
202 const std::vector<Node>& tourNodes() const { |
204 const std::vector<Node>& tourNodes() const { |
203 return _path; |
205 return _path; |