22 /// \ingroup tsp |
22 /// \ingroup tsp |
23 /// \file |
23 /// \file |
24 /// \brief Nearest neighbor algorithm for symmetric TSP |
24 /// \brief Nearest neighbor algorithm for symmetric TSP |
25 |
25 |
26 #include <deque> |
26 #include <deque> |
|
27 #include <vector> |
27 #include <limits> |
28 #include <limits> |
28 #include <lemon/full_graph.h> |
29 #include <lemon/full_graph.h> |
29 #include <lemon/maps.h> |
30 #include <lemon/maps.h> |
30 |
31 |
31 namespace lemon { |
32 namespace lemon { |
32 |
33 |
|
34 /// \ingroup tsp |
|
35 /// |
33 /// \brief Nearest neighbor algorithm for symmetric TSP. |
36 /// \brief Nearest neighbor algorithm for symmetric TSP. |
34 /// |
37 /// |
35 /// NearestNeighborTsp implements the nearest neighbor heuristic for solving |
38 /// NearestNeighborTsp implements the nearest neighbor heuristic for solving |
36 /// symmetric \ref tsp "TSP". |
39 /// symmetric \ref tsp "TSP". |
37 /// |
40 /// |
39 /// It starts with a minimum cost edge and at each step, it connects the |
42 /// It starts with a minimum cost edge and at each step, it connects the |
40 /// nearest unvisited node to the current path. |
43 /// nearest unvisited node to the current path. |
41 /// Finally, it connects the two end points of the path to form a tour. |
44 /// Finally, it connects the two end points of the path to form a tour. |
42 /// |
45 /// |
43 /// This method runs in O(n<sup>2</sup>) time. |
46 /// This method runs in O(n<sup>2</sup>) time. |
44 /// It quickly finds an effectively short tour for most TSP |
47 /// It quickly finds a short tour for most TSP instances, but in special |
45 /// instances, but in special cases, it could yield a really bad |
48 /// cases, it could yield a really bad (or even the worst) solution. |
46 /// (or even the worst) solution. |
|
47 /// |
49 /// |
48 /// \tparam CM Type of the cost map. |
50 /// \tparam CM Type of the cost map. |
49 template <typename CM> |
51 template <typename CM> |
50 class NearestNeighborTsp |
52 class NearestNeighborTsp |
51 { |
53 { |
83 /// This function runs the algorithm. |
85 /// This function runs the algorithm. |
84 /// |
86 /// |
85 /// \return The total cost of the found tour. |
87 /// \return The total cost of the found tour. |
86 Cost run() { |
88 Cost run() { |
87 _path.clear(); |
89 _path.clear(); |
88 |
90 if (_gr.nodeNum() == 0) { |
89 if (_gr.nodeNum() == 0) return _sum = 0; |
91 return _sum = 0; |
|
92 } |
90 else if (_gr.nodeNum() == 1) { |
93 else if (_gr.nodeNum() == 1) { |
91 _path.push_back(_gr(0)); |
94 _path.push_back(_gr(0)); |
92 return _sum = 0; |
95 return _sum = 0; |
93 } |
96 } |
94 |
97 |
|
98 std::deque<Node> path_dq; |
95 Edge min_edge1 = INVALID, |
99 Edge min_edge1 = INVALID, |
96 min_edge2 = INVALID; |
100 min_edge2 = INVALID; |
97 |
101 |
98 min_edge1 = mapMin(_gr, _cost); |
102 min_edge1 = mapMin(_gr, _cost); |
99 Node n1 = _gr.u(min_edge1), |
103 Node n1 = _gr.u(min_edge1), |
100 n2 = _gr.v(min_edge1); |
104 n2 = _gr.v(min_edge1); |
101 _path.push_back(n1); |
105 path_dq.push_back(n1); |
102 _path.push_back(n2); |
106 path_dq.push_back(n2); |
103 |
107 |
104 FullGraph::NodeMap<bool> used(_gr, false); |
108 FullGraph::NodeMap<bool> used(_gr, false); |
105 used[n1] = true; |
109 used[n1] = true; |
106 used[n2] = true; |
110 used[n2] = true; |
107 |
111 |
108 min_edge1 = INVALID; |
112 min_edge1 = INVALID; |
109 while (int(_path.size()) != _gr.nodeNum()) { |
113 while (int(path_dq.size()) != _gr.nodeNum()) { |
110 if (min_edge1 == INVALID) { |
114 if (min_edge1 == INVALID) { |
111 for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) { |
115 for (IncEdgeIt e(_gr, n1); e != INVALID; ++e) { |
112 if (!used[_gr.runningNode(e)] && |
116 if (!used[_gr.runningNode(e)] && |
113 (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) { |
117 (_cost[e] < _cost[min_edge1] || min_edge1 == INVALID)) { |
114 min_edge1 = e; |
118 min_edge1 = e; |
125 } |
129 } |
126 } |
130 } |
127 |
131 |
128 if (_cost[min_edge1] < _cost[min_edge2]) { |
132 if (_cost[min_edge1] < _cost[min_edge2]) { |
129 n1 = _gr.oppositeNode(n1, min_edge1); |
133 n1 = _gr.oppositeNode(n1, min_edge1); |
130 _path.push_front(n1); |
134 path_dq.push_front(n1); |
131 |
135 |
132 used[n1] = true; |
136 used[n1] = true; |
133 min_edge1 = INVALID; |
137 min_edge1 = INVALID; |
134 |
138 |
135 if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1) |
139 if (_gr.u(min_edge2) == n1 || _gr.v(min_edge2) == n1) |
136 min_edge2 = INVALID; |
140 min_edge2 = INVALID; |
137 } else { |
141 } else { |
138 n2 = _gr.oppositeNode(n2, min_edge2); |
142 n2 = _gr.oppositeNode(n2, min_edge2); |
139 _path.push_back(n2); |
143 path_dq.push_back(n2); |
140 |
144 |
141 used[n2] = true; |
145 used[n2] = true; |
142 min_edge2 = INVALID; |
146 min_edge2 = INVALID; |
143 |
147 |
144 if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2) |
148 if (_gr.u(min_edge1) == n2 || _gr.v(min_edge1) == n2) |
145 min_edge1 = INVALID; |
149 min_edge1 = INVALID; |
146 } |
150 } |
147 } |
151 } |
148 |
152 |
149 _sum = _cost[_gr.edge(_path.back(), _path.front())]; |
153 n1 = path_dq.back(); |
150 for (int i = 0; i < int(_path.size())-1; ++i) { |
154 n2 = path_dq.front(); |
151 _sum += _cost[_gr.edge(_path[i], _path[i+1])]; |
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 |
154 return _sum; |
164 return _sum; |
155 } |
165 } |
156 |
166 |
169 } |
179 } |
170 |
180 |
171 /// \brief Returns a const reference to the node sequence of the |
181 /// \brief Returns a const reference to the node sequence of the |
172 /// found tour. |
182 /// found tour. |
173 /// |
183 /// |
174 /// This function returns a const reference to the internal structure |
184 /// This function returns a const reference to a vector |
175 /// that stores the node sequence of the found tour. |
185 /// that stores the node sequence of the found tour. |
176 /// |
186 /// |
177 /// \pre run() must be called before using this function. |
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 return _path; |
189 return _path; |
180 } |
190 } |
181 |
191 |
182 /// \brief Gives back the node sequence of the found tour. |
192 /// \brief Gives back the node sequence of the found tour. |
183 /// |
193 /// |