[1201] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
| 5 | * Copyright (C) 2003-2010 |
---|
| 6 | * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
---|
| 7 | * (Egervary Research Group on Combinatorial Optimization, EGRES). |
---|
| 8 | * |
---|
| 9 | * Permission to use, modify and distribute this software is granted |
---|
| 10 | * provided that this copyright notice appears in all copies. For |
---|
| 11 | * precise terms see the accompanying LICENSE file. |
---|
| 12 | * |
---|
| 13 | * This software is provided "AS IS" with no warranty of any kind, |
---|
| 14 | * express or implied, and with no claim as to its suitability for any |
---|
| 15 | * purpose. |
---|
| 16 | * |
---|
| 17 | */ |
---|
| 18 | |
---|
[1199] | 19 | #ifndef LEMON_INSERTION_TSP_H |
---|
| 20 | #define LEMON_INSERTION_TSP_H |
---|
| 21 | |
---|
[1201] | 22 | /// \ingroup tsp |
---|
| 23 | /// \file |
---|
| 24 | /// \brief Insertion algorithm for symmetric TSP |
---|
| 25 | |
---|
| 26 | #include <vector> |
---|
[1204] | 27 | #include <functional> |
---|
[1199] | 28 | #include <lemon/full_graph.h> |
---|
| 29 | #include <lemon/maps.h> |
---|
| 30 | #include <lemon/random.h> |
---|
| 31 | |
---|
| 32 | namespace lemon { |
---|
| 33 | |
---|
[1202] | 34 | /// \ingroup tsp |
---|
| 35 | /// |
---|
[1201] | 36 | /// \brief Insertion algorithm for symmetric TSP. |
---|
| 37 | /// |
---|
| 38 | /// InsertionTsp implements the insertion heuristic for solving |
---|
| 39 | /// symmetric \ref tsp "TSP". |
---|
| 40 | /// |
---|
[1204] | 41 | /// This is a fast and effective tour construction method that has |
---|
| 42 | /// many variants. |
---|
[1201] | 43 | /// It starts with a subtour containing a few nodes of the graph and it |
---|
| 44 | /// iteratively inserts the other nodes into this subtour according to a |
---|
| 45 | /// certain node selection rule. |
---|
| 46 | /// |
---|
[1204] | 47 | /// This method is among the fastest TSP algorithms, and it typically |
---|
| 48 | /// provides quite good solutions (usually much better than |
---|
| 49 | /// \ref NearestNeighborTsp and \ref GreedyTsp). |
---|
| 50 | /// |
---|
| 51 | /// InsertionTsp implements four different node selection rules, |
---|
| 52 | /// from which the most effective one (\e farthest \e node \e selection) |
---|
| 53 | /// is used by default. |
---|
| 54 | /// With this choice, the algorithm runs in O(n<sup>2</sup>) time. |
---|
[1201] | 55 | /// For more information, see \ref SelectionRule. |
---|
| 56 | /// |
---|
| 57 | /// \tparam CM Type of the cost map. |
---|
| 58 | template <typename CM> |
---|
| 59 | class InsertionTsp |
---|
| 60 | { |
---|
| 61 | public: |
---|
[1199] | 62 | |
---|
[1201] | 63 | /// Type of the cost map |
---|
[1199] | 64 | typedef CM CostMap; |
---|
[1201] | 65 | /// Type of the edge costs |
---|
[1199] | 66 | typedef typename CM::Value Cost; |
---|
| 67 | |
---|
| 68 | private: |
---|
| 69 | |
---|
[1201] | 70 | GRAPH_TYPEDEFS(FullGraph); |
---|
| 71 | |
---|
| 72 | const FullGraph &_gr; |
---|
| 73 | const CostMap &_cost; |
---|
| 74 | std::vector<Node> _notused; |
---|
[1204] | 75 | std::vector<Node> _tour; |
---|
[1201] | 76 | Cost _sum; |
---|
| 77 | |
---|
| 78 | public: |
---|
| 79 | |
---|
| 80 | /// \brief Constants for specifying the node selection rule. |
---|
| 81 | /// |
---|
| 82 | /// Enum type containing constants for specifying the node selection |
---|
| 83 | /// rule for the \ref run() function. |
---|
| 84 | /// |
---|
| 85 | /// During the algorithm, nodes are selected for addition to the current |
---|
| 86 | /// subtour according to the applied rule. |
---|
[1204] | 87 | /// The FARTHEST method is one of the fastest selection rules, and |
---|
| 88 | /// it is typically the most effective, thus it is the default |
---|
| 89 | /// option. The RANDOM rule usually gives slightly worse results, |
---|
| 90 | /// but it is more robust. |
---|
[1201] | 91 | /// |
---|
| 92 | /// The desired selection rule can be specified as a parameter of the |
---|
| 93 | /// \ref run() function. |
---|
| 94 | enum SelectionRule { |
---|
| 95 | |
---|
| 96 | /// An unvisited node having minimum distance from the current |
---|
| 97 | /// subtour is selected at each step. |
---|
[1204] | 98 | /// The algorithm runs in O(n<sup>2</sup>) time using this |
---|
[1201] | 99 | /// selection rule. |
---|
| 100 | NEAREST, |
---|
| 101 | |
---|
| 102 | /// An unvisited node having maximum distance from the current |
---|
| 103 | /// subtour is selected at each step. |
---|
[1204] | 104 | /// The algorithm runs in O(n<sup>2</sup>) time using this |
---|
[1201] | 105 | /// selection rule. |
---|
| 106 | FARTHEST, |
---|
| 107 | |
---|
| 108 | /// An unvisited node whose insertion results in the least |
---|
| 109 | /// increase of the subtour's total cost is selected at each step. |
---|
| 110 | /// The algorithm runs in O(n<sup>3</sup>) time using this |
---|
[1204] | 111 | /// selection rule, but in most cases, it is almost as fast as |
---|
| 112 | /// with other rules. |
---|
[1201] | 113 | CHEAPEST, |
---|
| 114 | |
---|
| 115 | /// An unvisited node is selected randomly without any evaluation |
---|
| 116 | /// at each step. |
---|
| 117 | /// The global \ref rnd "random number generator instance" is used. |
---|
| 118 | /// You can seed it before executing the algorithm, if you |
---|
| 119 | /// would like to. |
---|
| 120 | /// The algorithm runs in O(n<sup>2</sup>) time using this |
---|
| 121 | /// selection rule. |
---|
| 122 | RANDOM |
---|
| 123 | }; |
---|
| 124 | |
---|
| 125 | public: |
---|
| 126 | |
---|
| 127 | /// \brief Constructor |
---|
| 128 | /// |
---|
| 129 | /// Constructor. |
---|
| 130 | /// \param gr The \ref FullGraph "full graph" the algorithm runs on. |
---|
| 131 | /// \param cost The cost map. |
---|
| 132 | InsertionTsp(const FullGraph &gr, const CostMap &cost) |
---|
| 133 | : _gr(gr), _cost(cost) {} |
---|
| 134 | |
---|
| 135 | /// \name Execution Control |
---|
| 136 | /// @{ |
---|
| 137 | |
---|
| 138 | /// \brief Runs the algorithm. |
---|
| 139 | /// |
---|
| 140 | /// This function runs the algorithm. |
---|
| 141 | /// |
---|
| 142 | /// \param rule The node selection rule. For more information, see |
---|
| 143 | /// \ref SelectionRule. |
---|
| 144 | /// |
---|
| 145 | /// \return The total cost of the found tour. |
---|
| 146 | Cost run(SelectionRule rule = FARTHEST) { |
---|
[1204] | 147 | _tour.clear(); |
---|
[1201] | 148 | |
---|
| 149 | if (_gr.nodeNum() == 0) return _sum = 0; |
---|
| 150 | else if (_gr.nodeNum() == 1) { |
---|
[1204] | 151 | _tour.push_back(_gr(0)); |
---|
[1201] | 152 | return _sum = 0; |
---|
| 153 | } |
---|
| 154 | |
---|
| 155 | switch (rule) { |
---|
| 156 | case NEAREST: |
---|
| 157 | init(true); |
---|
[1204] | 158 | start<ComparingSelection<std::less<Cost> >, |
---|
| 159 | DefaultInsertion>(); |
---|
[1201] | 160 | break; |
---|
| 161 | case FARTHEST: |
---|
| 162 | init(false); |
---|
[1204] | 163 | start<ComparingSelection<std::greater<Cost> >, |
---|
| 164 | DefaultInsertion>(); |
---|
[1201] | 165 | break; |
---|
| 166 | case CHEAPEST: |
---|
| 167 | init(true); |
---|
| 168 | start<CheapestSelection, CheapestInsertion>(); |
---|
| 169 | break; |
---|
| 170 | case RANDOM: |
---|
| 171 | init(true); |
---|
| 172 | start<RandomSelection, DefaultInsertion>(); |
---|
| 173 | break; |
---|
| 174 | } |
---|
| 175 | return _sum; |
---|
| 176 | } |
---|
| 177 | |
---|
| 178 | /// @} |
---|
| 179 | |
---|
| 180 | /// \name Query Functions |
---|
| 181 | /// @{ |
---|
| 182 | |
---|
| 183 | /// \brief The total cost of the found tour. |
---|
| 184 | /// |
---|
| 185 | /// This function returns the total cost of the found tour. |
---|
| 186 | /// |
---|
| 187 | /// \pre run() must be called before using this function. |
---|
| 188 | Cost tourCost() const { |
---|
| 189 | return _sum; |
---|
| 190 | } |
---|
| 191 | |
---|
| 192 | /// \brief Returns a const reference to the node sequence of the |
---|
| 193 | /// found tour. |
---|
| 194 | /// |
---|
[1202] | 195 | /// This function returns a const reference to a vector |
---|
[1201] | 196 | /// that stores the node sequence of the found tour. |
---|
| 197 | /// |
---|
| 198 | /// \pre run() must be called before using this function. |
---|
| 199 | const std::vector<Node>& tourNodes() const { |
---|
[1204] | 200 | return _tour; |
---|
[1201] | 201 | } |
---|
| 202 | |
---|
| 203 | /// \brief Gives back the node sequence of the found tour. |
---|
| 204 | /// |
---|
| 205 | /// This function copies the node sequence of the found tour into |
---|
| 206 | /// the given standard container. |
---|
| 207 | /// |
---|
| 208 | /// \pre run() must be called before using this function. |
---|
| 209 | template <typename Container> |
---|
| 210 | void tourNodes(Container &container) const { |
---|
[1204] | 211 | container.assign(_tour.begin(), _tour.end()); |
---|
[1201] | 212 | } |
---|
| 213 | |
---|
| 214 | /// \brief Gives back the found tour as a path. |
---|
| 215 | /// |
---|
| 216 | /// This function copies the found tour as a list of arcs/edges into |
---|
| 217 | /// the given \ref concept::Path "path structure". |
---|
| 218 | /// |
---|
| 219 | /// \pre run() must be called before using this function. |
---|
| 220 | template <typename Path> |
---|
| 221 | void tour(Path &path) const { |
---|
| 222 | path.clear(); |
---|
[1204] | 223 | for (int i = 0; i < int(_tour.size()) - 1; ++i) { |
---|
| 224 | path.addBack(_gr.arc(_tour[i], _tour[i+1])); |
---|
[1201] | 225 | } |
---|
[1204] | 226 | if (int(_tour.size()) >= 2) { |
---|
| 227 | path.addBack(_gr.arc(_tour.back(), _tour.front())); |
---|
[1201] | 228 | } |
---|
| 229 | } |
---|
| 230 | |
---|
| 231 | /// @} |
---|
| 232 | |
---|
| 233 | private: |
---|
| 234 | |
---|
| 235 | // Initializes the algorithm |
---|
| 236 | void init(bool min) { |
---|
| 237 | Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost); |
---|
| 238 | |
---|
[1204] | 239 | _tour.clear(); |
---|
| 240 | _tour.push_back(_gr.u(min_edge)); |
---|
| 241 | _tour.push_back(_gr.v(min_edge)); |
---|
[1201] | 242 | |
---|
| 243 | _notused.clear(); |
---|
| 244 | for (NodeIt n(_gr); n!=INVALID; ++n) { |
---|
| 245 | if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) { |
---|
| 246 | _notused.push_back(n); |
---|
| 247 | } |
---|
| 248 | } |
---|
| 249 | |
---|
| 250 | _sum = _cost[min_edge] * 2; |
---|
| 251 | } |
---|
| 252 | |
---|
| 253 | // Executes the algorithm |
---|
| 254 | template <class SelectionFunctor, class InsertionFunctor> |
---|
| 255 | void start() { |
---|
[1204] | 256 | SelectionFunctor selectNode(_gr, _cost, _tour, _notused); |
---|
| 257 | InsertionFunctor insertNode(_gr, _cost, _tour, _sum); |
---|
[1201] | 258 | |
---|
| 259 | for (int i=0; i<_gr.nodeNum()-2; ++i) { |
---|
| 260 | insertNode.insert(selectNode.select()); |
---|
| 261 | } |
---|
| 262 | |
---|
[1204] | 263 | _sum = _cost[_gr.edge(_tour.back(), _tour.front())]; |
---|
| 264 | for (int i = 0; i < int(_tour.size())-1; ++i) { |
---|
| 265 | _sum += _cost[_gr.edge(_tour[i], _tour[i+1])]; |
---|
[1201] | 266 | } |
---|
| 267 | } |
---|
| 268 | |
---|
| 269 | |
---|
[1204] | 270 | // Implementation of the nearest and farthest selection rule |
---|
| 271 | template <typename Comparator> |
---|
| 272 | class ComparingSelection { |
---|
[1199] | 273 | public: |
---|
[1204] | 274 | ComparingSelection(const FullGraph &gr, const CostMap &cost, |
---|
| 275 | std::vector<Node> &tour, std::vector<Node> ¬used) |
---|
| 276 | : _gr(gr), _cost(cost), _tour(tour), _notused(notused), |
---|
| 277 | _dist(gr, 0), _compare() |
---|
| 278 | { |
---|
| 279 | // Compute initial distances for the unused nodes |
---|
[1201] | 280 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
[1204] | 281 | Node u = _notused[i]; |
---|
| 282 | Cost min_dist = _cost[_gr.edge(u, _tour[0])]; |
---|
| 283 | for (unsigned int j=1; j<_tour.size(); ++j) { |
---|
| 284 | Cost curr = _cost[_gr.edge(u, _tour[j])]; |
---|
| 285 | if (curr < min_dist) { |
---|
| 286 | min_dist = curr; |
---|
[1201] | 287 | } |
---|
| 288 | } |
---|
[1204] | 289 | _dist[u] = min_dist; |
---|
| 290 | } |
---|
| 291 | } |
---|
[1201] | 292 | |
---|
[1204] | 293 | Node select() { |
---|
| 294 | |
---|
| 295 | // Select an used node with minimum distance |
---|
| 296 | Cost ins_dist = 0; |
---|
| 297 | int ins_node = -1; |
---|
| 298 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
| 299 | Cost curr = _dist[_notused[i]]; |
---|
| 300 | if (_compare(curr, ins_dist) || ins_node == -1) { |
---|
| 301 | ins_dist = curr; |
---|
| 302 | ins_node = i; |
---|
[1199] | 303 | } |
---|
| 304 | } |
---|
[1201] | 305 | |
---|
[1204] | 306 | // Remove the selected node from the unused vector |
---|
| 307 | Node sn = _notused[ins_node]; |
---|
| 308 | _notused[ins_node] = _notused.back(); |
---|
| 309 | _notused.pop_back(); |
---|
[1201] | 310 | |
---|
[1204] | 311 | // Update the distances of the remaining nodes |
---|
| 312 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
| 313 | Node u = _notused[i]; |
---|
| 314 | Cost nc = _cost[_gr.edge(sn, u)]; |
---|
| 315 | if (nc < _dist[u]) { |
---|
| 316 | _dist[u] = nc; |
---|
| 317 | } |
---|
| 318 | } |
---|
| 319 | |
---|
| 320 | return sn; |
---|
[1199] | 321 | } |
---|
| 322 | |
---|
| 323 | private: |
---|
| 324 | const FullGraph &_gr; |
---|
| 325 | const CostMap &_cost; |
---|
[1204] | 326 | std::vector<Node> &_tour; |
---|
[1199] | 327 | std::vector<Node> &_notused; |
---|
[1204] | 328 | FullGraph::NodeMap<Cost> _dist; |
---|
| 329 | Comparator _compare; |
---|
[1199] | 330 | }; |
---|
| 331 | |
---|
[1201] | 332 | // Implementation of the cheapest selection rule |
---|
[1199] | 333 | class CheapestSelection { |
---|
| 334 | private: |
---|
| 335 | Cost costDiff(Node u, Node v, Node w) const { |
---|
[1201] | 336 | return |
---|
[1199] | 337 | _cost[_gr.edge(u, w)] + |
---|
| 338 | _cost[_gr.edge(v, w)] - |
---|
| 339 | _cost[_gr.edge(u, v)]; |
---|
| 340 | } |
---|
| 341 | |
---|
| 342 | public: |
---|
| 343 | CheapestSelection(const FullGraph &gr, const CostMap &cost, |
---|
[1204] | 344 | std::vector<Node> &tour, std::vector<Node> ¬used) |
---|
| 345 | : _gr(gr), _cost(cost), _tour(tour), _notused(notused), |
---|
| 346 | _ins_cost(gr, 0), _ins_pos(gr, -1) |
---|
| 347 | { |
---|
| 348 | // Compute insertion cost and position for the unused nodes |
---|
[1199] | 349 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
[1204] | 350 | Node u = _notused[i]; |
---|
| 351 | Cost min_cost = costDiff(_tour.back(), _tour.front(), u); |
---|
| 352 | int min_pos = 0; |
---|
| 353 | for (unsigned int j=1; j<_tour.size(); ++j) { |
---|
| 354 | Cost curr_cost = costDiff(_tour[j-1], _tour[j], u); |
---|
| 355 | if (curr_cost < min_cost) { |
---|
| 356 | min_cost = curr_cost; |
---|
| 357 | min_pos = j; |
---|
[1199] | 358 | } |
---|
| 359 | } |
---|
[1204] | 360 | _ins_cost[u] = min_cost; |
---|
| 361 | _ins_pos[u] = min_pos; |
---|
| 362 | } |
---|
| 363 | } |
---|
[1199] | 364 | |
---|
[1204] | 365 | Cost select() { |
---|
| 366 | |
---|
| 367 | // Select an used node with minimum insertion cost |
---|
| 368 | Cost min_cost = 0; |
---|
| 369 | int min_node = -1; |
---|
| 370 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
| 371 | Cost curr_cost = _ins_cost[_notused[i]]; |
---|
| 372 | if (curr_cost < min_cost || min_node == -1) { |
---|
| 373 | min_cost = curr_cost; |
---|
| 374 | min_node = i; |
---|
[1199] | 375 | } |
---|
| 376 | } |
---|
| 377 | |
---|
[1204] | 378 | // Remove the selected node from the unused vector |
---|
| 379 | Node sn = _notused[min_node]; |
---|
| 380 | _notused[min_node] = _notused.back(); |
---|
| 381 | _notused.pop_back(); |
---|
| 382 | |
---|
| 383 | // Insert the selected node into the tour |
---|
| 384 | const int ipos = _ins_pos[sn]; |
---|
| 385 | _tour.insert(_tour.begin() + ipos, sn); |
---|
[1199] | 386 | |
---|
[1204] | 387 | // Update the insertion cost and position of the remaining nodes |
---|
| 388 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
| 389 | Node u = _notused[i]; |
---|
| 390 | Cost curr_cost = _ins_cost[u]; |
---|
| 391 | int curr_pos = _ins_pos[u]; |
---|
| 392 | |
---|
| 393 | int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1; |
---|
| 394 | int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1; |
---|
| 395 | Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u); |
---|
| 396 | Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u); |
---|
| 397 | |
---|
| 398 | if (nc1 <= curr_cost || nc2 <= curr_cost) { |
---|
| 399 | // A new position is better than the old one |
---|
| 400 | if (nc1 <= nc2) { |
---|
| 401 | curr_cost = nc1; |
---|
| 402 | curr_pos = ipos; |
---|
| 403 | } else { |
---|
| 404 | curr_cost = nc2; |
---|
| 405 | curr_pos = ipos_next; |
---|
| 406 | } |
---|
| 407 | } |
---|
| 408 | else { |
---|
| 409 | if (curr_pos == ipos) { |
---|
| 410 | // The minimum should be found again |
---|
| 411 | curr_cost = costDiff(_tour.back(), _tour.front(), u); |
---|
| 412 | curr_pos = 0; |
---|
| 413 | for (unsigned int j=1; j<_tour.size(); ++j) { |
---|
| 414 | Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u); |
---|
| 415 | if (tmp_cost < curr_cost) { |
---|
| 416 | curr_cost = tmp_cost; |
---|
| 417 | curr_pos = j; |
---|
| 418 | } |
---|
| 419 | } |
---|
| 420 | } |
---|
| 421 | else if (curr_pos > ipos) { |
---|
| 422 | ++curr_pos; |
---|
| 423 | } |
---|
| 424 | } |
---|
| 425 | |
---|
| 426 | _ins_cost[u] = curr_cost; |
---|
| 427 | _ins_pos[u] = curr_pos; |
---|
| 428 | } |
---|
| 429 | |
---|
| 430 | return min_cost; |
---|
[1199] | 431 | } |
---|
[1201] | 432 | |
---|
[1199] | 433 | private: |
---|
| 434 | const FullGraph &_gr; |
---|
| 435 | const CostMap &_cost; |
---|
[1204] | 436 | std::vector<Node> &_tour; |
---|
[1199] | 437 | std::vector<Node> &_notused; |
---|
[1204] | 438 | FullGraph::NodeMap<Cost> _ins_cost; |
---|
| 439 | FullGraph::NodeMap<int> _ins_pos; |
---|
[1199] | 440 | }; |
---|
| 441 | |
---|
[1201] | 442 | // Implementation of the random selection rule |
---|
[1199] | 443 | class RandomSelection { |
---|
| 444 | public: |
---|
| 445 | RandomSelection(const FullGraph &, const CostMap &, |
---|
[1201] | 446 | std::vector<Node> &, std::vector<Node> ¬used) |
---|
| 447 | : _notused(notused) {} |
---|
| 448 | |
---|
[1199] | 449 | Node select() const { |
---|
| 450 | const int index = rnd[_notused.size()]; |
---|
| 451 | Node n = _notused[index]; |
---|
[1204] | 452 | _notused[index] = _notused.back(); |
---|
| 453 | _notused.pop_back(); |
---|
[1199] | 454 | return n; |
---|
| 455 | } |
---|
[1204] | 456 | |
---|
[1199] | 457 | private: |
---|
| 458 | std::vector<Node> &_notused; |
---|
| 459 | }; |
---|
| 460 | |
---|
| 461 | |
---|
[1201] | 462 | // Implementation of the default insertion method |
---|
| 463 | class DefaultInsertion { |
---|
[1199] | 464 | private: |
---|
| 465 | Cost costDiff(Node u, Node v, Node w) const { |
---|
[1201] | 466 | return |
---|
[1199] | 467 | _cost[_gr.edge(u, w)] + |
---|
| 468 | _cost[_gr.edge(v, w)] - |
---|
| 469 | _cost[_gr.edge(u, v)]; |
---|
| 470 | } |
---|
[1201] | 471 | |
---|
[1199] | 472 | public: |
---|
[1201] | 473 | DefaultInsertion(const FullGraph &gr, const CostMap &cost, |
---|
[1204] | 474 | std::vector<Node> &tour, Cost &total_cost) : |
---|
| 475 | _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {} |
---|
[1201] | 476 | |
---|
[1199] | 477 | void insert(Node n) const { |
---|
| 478 | int min = 0; |
---|
| 479 | Cost min_val = |
---|
[1204] | 480 | costDiff(_tour.front(), _tour.back(), n); |
---|
[1201] | 481 | |
---|
[1204] | 482 | for (unsigned int i=1; i<_tour.size(); ++i) { |
---|
| 483 | Cost tmp = costDiff(_tour[i-1], _tour[i], n); |
---|
[1199] | 484 | if (tmp < min_val) { |
---|
| 485 | min = i; |
---|
| 486 | min_val = tmp; |
---|
| 487 | } |
---|
| 488 | } |
---|
[1201] | 489 | |
---|
[1204] | 490 | _tour.insert(_tour.begin()+min, n); |
---|
[1201] | 491 | _total += min_val; |
---|
[1199] | 492 | } |
---|
[1201] | 493 | |
---|
[1199] | 494 | private: |
---|
| 495 | const FullGraph &_gr; |
---|
| 496 | const CostMap &_cost; |
---|
[1204] | 497 | std::vector<Node> &_tour; |
---|
[1201] | 498 | Cost &_total; |
---|
[1199] | 499 | }; |
---|
[1201] | 500 | |
---|
| 501 | // Implementation of a special insertion method for the cheapest |
---|
| 502 | // selection rule |
---|
| 503 | class CheapestInsertion { |
---|
[1199] | 504 | TEMPLATE_GRAPH_TYPEDEFS(FullGraph); |
---|
| 505 | public: |
---|
[1201] | 506 | CheapestInsertion(const FullGraph &, const CostMap &, |
---|
| 507 | std::vector<Node> &, Cost &total_cost) : |
---|
| 508 | _total(total_cost) {} |
---|
| 509 | |
---|
[1199] | 510 | void insert(Cost diff) const { |
---|
[1201] | 511 | _total += diff; |
---|
[1199] | 512 | } |
---|
| 513 | |
---|
| 514 | private: |
---|
[1201] | 515 | Cost &_total; |
---|
| 516 | }; |
---|
| 517 | |
---|
[1199] | 518 | }; |
---|
[1201] | 519 | |
---|
[1199] | 520 | }; // namespace lemon |
---|
| 521 | |
---|
| 522 | #endif |
---|