equal
deleted
inserted
replaced
41 /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths. |
41 /// "nearest neighbor" heuristic, but it maintains a set of disjoint paths. |
42 /// 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 |
43 /// 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 |
44 /// not increase the degree of any node above two. |
44 /// not increase the degree of any node above two. |
45 /// |
45 /// |
46 /// This method runs in O(n<sup>2</sup>log(n)) time. |
46 /// This method runs in O(n<sup>2</sup>) time. |
47 /// It quickly finds a short tour for most TSP instances, but in special |
47 /// It quickly finds a relatively short tour for most TSP instances, |
48 /// cases, it could yield a really bad (or even the worst) solution. |
48 /// but it could also yield a really bad (or even the worst) solution |
|
49 /// in special cases. |
49 /// |
50 /// |
50 /// \tparam CM Type of the cost map. |
51 /// \tparam CM Type of the cost map. |
51 template <typename CM> |
52 template <typename CM> |
52 class GreedyTsp |
53 class GreedyTsp |
53 { |
54 { |