equal
deleted
inserted
replaced
28 #include <lemon/full_graph.h> |
28 #include <lemon/full_graph.h> |
29 #include <lemon/unionfind.h> |
29 #include <lemon/unionfind.h> |
30 |
30 |
31 namespace lemon { |
31 namespace lemon { |
32 |
32 |
|
33 /// \ingroup tsp |
|
34 /// |
33 /// \brief Greedy algorithm for symmetric TSP. |
35 /// \brief Greedy algorithm for symmetric TSP. |
34 /// |
36 /// |
35 /// GreedyTsp implements the greedy heuristic for solving |
37 /// GreedyTsp implements the greedy heuristic for solving |
36 /// symmetric \ref tsp "TSP". |
38 /// symmetric \ref tsp "TSP". |
37 /// |
39 /// |
40 /// At each step, the shortest possible edge is added to these paths |
42 /// At each step, the shortest possible edge is added to these paths |
41 /// as long as it does not create a cycle of less than n edges and it does |
43 /// as long as it does not create a cycle of less than n edges and it does |
42 /// not increase the degree of any node above two. |
44 /// not increase the degree of any node above two. |
43 /// |
45 /// |
44 /// This method runs in O(n<sup>2</sup>log(n)) time. |
46 /// This method runs in O(n<sup>2</sup>log(n)) time. |
45 /// It quickly finds an effectively short tour for most TSP |
47 /// It quickly finds a short tour for most TSP instances, but in special |
46 /// instances, but in special cases, it could yield a really bad |
48 /// cases, it could yield a really bad (or even the worst) solution. |
47 /// (or even the worst) solution. |
|
48 /// |
49 /// |
49 /// \tparam CM Type of the cost map. |
50 /// \tparam CM Type of the cost map. |
50 template <typename CM> |
51 template <typename CM> |
51 class GreedyTsp |
52 class GreedyTsp |
52 { |
53 { |
191 } |
192 } |
192 |
193 |
193 /// \brief Returns a const reference to the node sequence of the |
194 /// \brief Returns a const reference to the node sequence of the |
194 /// found tour. |
195 /// found tour. |
195 /// |
196 /// |
196 /// This function returns a const reference to the internal structure |
197 /// This function returns a const reference to a vector |
197 /// that stores the node sequence of the found tour. |
198 /// that stores the node sequence of the found tour. |
198 /// |
199 /// |
199 /// \pre run() must be called before using this function. |
200 /// \pre run() must be called before using this function. |
200 const std::vector<Node>& tourNodes() const { |
201 const std::vector<Node>& tourNodes() const { |
201 return _path; |
202 return _path; |