Changeset 1034:ef200e268af2 in lemon-main for lemon/nearest_neighbor_tsp.h
- Timestamp:
- 01/09/11 00:56:52 (13 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
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 }
Note: See TracChangeset
for help on using the changeset viewer.