Changeset 1202:ef200e268af2 in lemon for lemon
- Timestamp:
- 01/09/11 00:56:52 (13 years ago)
- Branch:
- default
- Phase:
- public
- Location:
- lemon
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/christofides_tsp.h
r1201 r1202 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
r1201 r1202 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
r1201 r1202 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
r1201 r1202 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
r1201 r1202 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.