Changeset 1034:ef200e268af2 in lemon-main
- Timestamp:
- 01/09/11 00:56:52 (13 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r1032 r1034 562 562 once (i.e. the minimum cost Hamiltonian cycle). 563 563 564 These TSP algorithms should be used with a 565 metric cost function. Otherwise, they could yield worse results. 564 These TSP algorithms are intended to be used with a \e metric \e cost 565 \e function, i.e. the edge costs should satisfy the triangle inequality. 566 Otherwise the algorithms could yield worse results. 566 567 567 568 LEMON provides five well-known heuristics for solving symmetric TSP: -
lemon/christofides_tsp.h
r1033 r1034 32 32 namespace lemon { 33 33 34 /// \ingroup tsp 35 /// 34 36 /// \brief Christofides algorithm for symmetric TSP. 35 37 /// … … 38 40 /// 39 41 /// This a well-known approximation method for the TSP problem with 40 /// \ref checkMetricCost() "metric cost function".42 /// metric cost function. 41 43 /// It yields a tour whose total cost is at most 3/2 of the optimum, 42 44 /// but it is usually much better. … … 55 57 /// \tparam CM Type of the cost map. 56 58 /// 57 /// \warning \& CM::Value must be signedtype.59 /// \warning CM::Value must be a signed number type. 58 60 template <typename CM> 59 61 class ChristofidesTsp … … 196 198 /// found tour. 197 199 /// 198 /// This function returns a const reference to the internal structure200 /// This function returns a const reference to a vector 199 201 /// that stores the node sequence of the found tour. 200 202 /// -
lemon/greedy_tsp.h
r1033 r1034 31 31 namespace lemon { 32 32 33 /// \ingroup tsp 34 /// 33 35 /// \brief Greedy algorithm for symmetric TSP. 34 36 /// … … 43 45 /// 44 46 /// This method runs in O(n<sup>2</sup>log(n)) time. 45 /// It quickly finds an effectively short tour for most TSP 46 /// instances, but in special cases, it could yield a really bad 47 /// (or even the worst) solution. 47 /// It quickly finds a short tour for most TSP instances, but in special 48 /// cases, it could yield a really bad (or even the worst) solution. 48 49 /// 49 50 /// \tparam CM Type of the cost map. … … 194 195 /// found tour. 195 196 /// 196 /// This function returns a const reference to the internal structure197 /// This function returns a const reference to a vector 197 198 /// that stores the node sequence of the found tour. 198 199 /// -
lemon/insertion_tsp.h
r1033 r1034 31 31 namespace lemon { 32 32 33 /// \ingroup tsp 34 /// 33 35 /// \brief Insertion algorithm for symmetric TSP. 34 36 /// … … 75 77 /// During the algorithm, nodes are selected for addition to the current 76 78 /// subtour according to the applied rule. 77 /// In general, the FARTHEST yields the best tours, thus it is the78 /// default option. RANDOM usually gives somewhat worse results, but79 /// it is much faster than the others and it is the most robust.79 /// In general, the FARTHEST method yields the best tours, thus it is the 80 /// default option. The RANDOM rule usually gives somewhat worse results, 81 /// but it is much faster than the others and it is the most robust. 80 82 /// 81 83 /// The desired selection rule can be specified as a parameter of the … … 179 181 /// found tour. 180 182 /// 181 /// This function returns a const reference to the internal structure183 /// This function returns a const reference to a vector 182 184 /// that stores the node sequence of the found tour. 183 185 /// -
lemon/nearest_neighbor_tsp.h
r1033 r1034 25 25 26 26 #include <deque> 27 #include <vector> 27 28 #include <limits> 28 29 #include <lemon/full_graph.h> … … 31 32 namespace lemon { 32 33 34 /// \ingroup tsp 35 /// 33 36 /// \brief Nearest neighbor algorithm for symmetric TSP. 34 37 /// … … 42 45 /// 43 46 /// This method runs in O(n<sup>2</sup>) time. 44 /// It quickly finds an effectively short tour for most TSP 45 /// instances, but in special cases, it could yield a really bad 46 /// (or even the worst) solution. 47 /// It quickly finds a short tour for most TSP instances, but in special 48 /// cases, it could yield a really bad (or even the worst) solution. 47 49 /// 48 50 /// \tparam CM Type of the cost map. … … 64 66 const CostMap &_cost; 65 67 Cost _sum; 66 std:: deque<Node> _path;68 std::vector<Node> _path; 67 69 68 70 public: … … 86 88 Cost run() { 87 89 _path.clear(); 88 89 if (_gr.nodeNum() == 0) return _sum = 0; 90 if (_gr.nodeNum() == 0) { 91 return _sum = 0; 92 } 90 93 else if (_gr.nodeNum() == 1) { 91 94 _path.push_back(_gr(0)); … … 93 96 } 94 97 98 std::deque<Node> path_dq; 95 99 Edge min_edge1 = INVALID, 96 100 min_edge2 = INVALID; … … 99 103 Node n1 = _gr.u(min_edge1), 100 104 n2 = _gr.v(min_edge1); 101 _path.push_back(n1);102 _path.push_back(n2);105 path_dq.push_back(n1); 106 path_dq.push_back(n2); 103 107 104 108 FullGraph::NodeMap<bool> used(_gr, false); … … 107 111 108 112 min_edge1 = INVALID; 109 while (int( _path.size()) != _gr.nodeNum()) {113 while (int(path_dq.size()) != _gr.nodeNum()) { 110 114 if (min_edge1 == INVALID) { 111 115 for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) { … … 128 132 if (_cost[min_edge1] < _cost[min_edge2]) { 129 133 n1 = _gr.oppositeNode(n1, min_edge1); 130 _path.push_front(n1);134 path_dq.push_front(n1); 131 135 132 136 used[n1] = true; … … 137 141 } else { 138 142 n2 = _gr.oppositeNode(n2, min_edge2); 139 _path.push_back(n2);143 path_dq.push_back(n2); 140 144 141 145 used[n2] = true; … … 147 151 } 148 152 149 _sum = _cost[_gr.edge(_path.back(), _path.front())]; 150 for (int i = 0; i < int(_path.size())-1; ++i) { 151 _sum += _cost[_gr.edge(_path[i], _path[i+1])]; 153 n1 = path_dq.back(); 154 n2 = path_dq.front(); 155 _path.push_back(n2); 156 _sum = _cost[_gr.edge(n1, n2)]; 157 for (int i = 1; i < int(path_dq.size()); ++i) { 158 n1 = n2; 159 n2 = path_dq[i]; 160 _path.push_back(n2); 161 _sum += _cost[_gr.edge(n1, n2)]; 152 162 } 153 163 … … 172 182 /// found tour. 173 183 /// 174 /// This function returns a const reference to the internal structure184 /// This function returns a const reference to a vector 175 185 /// that stores the node sequence of the found tour. 176 186 /// 177 187 /// \pre run() must be called before using this function. 178 const std:: deque<Node>& tourNodes() const {188 const std::vector<Node>& tourNodes() const { 179 189 return _path; 180 190 } -
lemon/opt2_tsp.h
r1033 r1034 22 22 /// \ingroup tsp 23 23 /// \file 24 /// \brief 2-opt algorithm for symmetric TSP 24 /// \brief 2-opt algorithm for symmetric TSP. 25 25 26 26 #include <vector> … … 29 29 namespace lemon { 30 30 31 /// \ingroup tsp 32 /// 31 33 /// \brief 2-opt algorithm for symmetric TSP. 32 34 /// … … 115 117 } 116 118 117 /// \brief Runs the algorithm from the given tour.119 /// \brief Runs the algorithm starting from the given tour. 118 120 /// 119 121 /// This function runs the algorithm starting from the given tour. … … 157 159 } 158 160 159 /// \brief Runs the algorithm from the given tour. 160 /// 161 /// This function runs the algorithm starting from the given tour. 162 /// 163 /// \param tour The tour as a node sequence. It must be a standard 164 /// sequence container storing all <tt>Node</tt>s in the desired order. 161 /// \brief Runs the algorithm starting from the given tour. 162 /// 163 /// This function runs the algorithm starting from the given tour 164 /// (node sequence). 165 /// 166 /// \param tour A vector that stores all <tt>Node</tt>s of the graph 167 /// in the desired order. 165 168 /// 166 169 /// \return The total cost of the found tour. 167 template <template <typename> class Container> 168 Cost run(const Container<Node>& tour) { 170 Cost run(const std::vector<Node>& tour) { 169 171 _path.clear(); 170 172 … … 181 183 182 184 _plist.resize(2*_gr.nodeNum()); 183 typename Container<Node>::const_iterator it = tour.begin();185 typename std::vector<Node>::const_iterator it = tour.begin(); 184 186 int first = _gr.id(*it), 185 187 prev = first, … … 218 220 /// found tour. 219 221 /// 220 /// This function returns a const reference to the internal structure222 /// This function returns a const reference to a vector 221 223 /// that stores the node sequence of the found tour. 222 224 ///
Note: See TracChangeset
for help on using the changeset viewer.