[1201] | 1 | /* -*- mode: C++; indent-tabs-mode: nil; -*- |
---|
| 2 | * |
---|
| 3 | * This file is a part of LEMON, a generic C++ optimization library. |
---|
| 4 | * |
---|
[1270] | 5 | * Copyright (C) 2003-2013 |
---|
[1201] | 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 |
---|
[1205] | 206 | /// an STL container through the given output iterator. The |
---|
| 207 | /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>. |
---|
| 208 | /// For example, |
---|
| 209 | /// \code |
---|
| 210 | /// std::vector<FullGraph::Node> nodes(countNodes(graph)); |
---|
| 211 | /// tsp.tourNodes(nodes.begin()); |
---|
| 212 | /// \endcode |
---|
| 213 | /// or |
---|
| 214 | /// \code |
---|
| 215 | /// std::list<FullGraph::Node> nodes; |
---|
| 216 | /// tsp.tourNodes(std::back_inserter(nodes)); |
---|
| 217 | /// \endcode |
---|
[1201] | 218 | /// |
---|
| 219 | /// \pre run() must be called before using this function. |
---|
[1205] | 220 | template <typename Iterator> |
---|
| 221 | void tourNodes(Iterator out) const { |
---|
| 222 | std::copy(_tour.begin(), _tour.end(), out); |
---|
[1201] | 223 | } |
---|
| 224 | |
---|
| 225 | /// \brief Gives back the found tour as a path. |
---|
| 226 | /// |
---|
| 227 | /// This function copies the found tour as a list of arcs/edges into |
---|
[1250] | 228 | /// the given \ref lemon::concepts::Path "path structure". |
---|
[1201] | 229 | /// |
---|
| 230 | /// \pre run() must be called before using this function. |
---|
| 231 | template <typename Path> |
---|
| 232 | void tour(Path &path) const { |
---|
| 233 | path.clear(); |
---|
[1204] | 234 | for (int i = 0; i < int(_tour.size()) - 1; ++i) { |
---|
| 235 | path.addBack(_gr.arc(_tour[i], _tour[i+1])); |
---|
[1201] | 236 | } |
---|
[1204] | 237 | if (int(_tour.size()) >= 2) { |
---|
| 238 | path.addBack(_gr.arc(_tour.back(), _tour.front())); |
---|
[1201] | 239 | } |
---|
| 240 | } |
---|
| 241 | |
---|
| 242 | /// @} |
---|
| 243 | |
---|
| 244 | private: |
---|
| 245 | |
---|
| 246 | // Initializes the algorithm |
---|
| 247 | void init(bool min) { |
---|
| 248 | Edge min_edge = min ? mapMin(_gr, _cost) : mapMax(_gr, _cost); |
---|
| 249 | |
---|
[1204] | 250 | _tour.clear(); |
---|
| 251 | _tour.push_back(_gr.u(min_edge)); |
---|
| 252 | _tour.push_back(_gr.v(min_edge)); |
---|
[1201] | 253 | |
---|
| 254 | _notused.clear(); |
---|
| 255 | for (NodeIt n(_gr); n!=INVALID; ++n) { |
---|
| 256 | if (n != _gr.u(min_edge) && n != _gr.v(min_edge)) { |
---|
| 257 | _notused.push_back(n); |
---|
| 258 | } |
---|
| 259 | } |
---|
| 260 | |
---|
| 261 | _sum = _cost[min_edge] * 2; |
---|
| 262 | } |
---|
| 263 | |
---|
| 264 | // Executes the algorithm |
---|
| 265 | template <class SelectionFunctor, class InsertionFunctor> |
---|
| 266 | void start() { |
---|
[1204] | 267 | SelectionFunctor selectNode(_gr, _cost, _tour, _notused); |
---|
| 268 | InsertionFunctor insertNode(_gr, _cost, _tour, _sum); |
---|
[1201] | 269 | |
---|
| 270 | for (int i=0; i<_gr.nodeNum()-2; ++i) { |
---|
| 271 | insertNode.insert(selectNode.select()); |
---|
| 272 | } |
---|
| 273 | |
---|
[1204] | 274 | _sum = _cost[_gr.edge(_tour.back(), _tour.front())]; |
---|
| 275 | for (int i = 0; i < int(_tour.size())-1; ++i) { |
---|
| 276 | _sum += _cost[_gr.edge(_tour[i], _tour[i+1])]; |
---|
[1201] | 277 | } |
---|
| 278 | } |
---|
| 279 | |
---|
| 280 | |
---|
[1204] | 281 | // Implementation of the nearest and farthest selection rule |
---|
| 282 | template <typename Comparator> |
---|
| 283 | class ComparingSelection { |
---|
[1199] | 284 | public: |
---|
[1204] | 285 | ComparingSelection(const FullGraph &gr, const CostMap &cost, |
---|
| 286 | std::vector<Node> &tour, std::vector<Node> ¬used) |
---|
| 287 | : _gr(gr), _cost(cost), _tour(tour), _notused(notused), |
---|
| 288 | _dist(gr, 0), _compare() |
---|
| 289 | { |
---|
| 290 | // Compute initial distances for the unused nodes |
---|
[1201] | 291 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
[1204] | 292 | Node u = _notused[i]; |
---|
| 293 | Cost min_dist = _cost[_gr.edge(u, _tour[0])]; |
---|
| 294 | for (unsigned int j=1; j<_tour.size(); ++j) { |
---|
| 295 | Cost curr = _cost[_gr.edge(u, _tour[j])]; |
---|
| 296 | if (curr < min_dist) { |
---|
| 297 | min_dist = curr; |
---|
[1201] | 298 | } |
---|
| 299 | } |
---|
[1204] | 300 | _dist[u] = min_dist; |
---|
| 301 | } |
---|
| 302 | } |
---|
[1201] | 303 | |
---|
[1204] | 304 | Node select() { |
---|
| 305 | |
---|
| 306 | // Select an used node with minimum distance |
---|
| 307 | Cost ins_dist = 0; |
---|
| 308 | int ins_node = -1; |
---|
| 309 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
| 310 | Cost curr = _dist[_notused[i]]; |
---|
| 311 | if (_compare(curr, ins_dist) || ins_node == -1) { |
---|
| 312 | ins_dist = curr; |
---|
| 313 | ins_node = i; |
---|
[1199] | 314 | } |
---|
| 315 | } |
---|
[1201] | 316 | |
---|
[1204] | 317 | // Remove the selected node from the unused vector |
---|
| 318 | Node sn = _notused[ins_node]; |
---|
| 319 | _notused[ins_node] = _notused.back(); |
---|
| 320 | _notused.pop_back(); |
---|
[1201] | 321 | |
---|
[1204] | 322 | // Update the distances of the remaining nodes |
---|
| 323 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
| 324 | Node u = _notused[i]; |
---|
| 325 | Cost nc = _cost[_gr.edge(sn, u)]; |
---|
| 326 | if (nc < _dist[u]) { |
---|
| 327 | _dist[u] = nc; |
---|
| 328 | } |
---|
| 329 | } |
---|
| 330 | |
---|
| 331 | return sn; |
---|
[1199] | 332 | } |
---|
| 333 | |
---|
| 334 | private: |
---|
| 335 | const FullGraph &_gr; |
---|
| 336 | const CostMap &_cost; |
---|
[1204] | 337 | std::vector<Node> &_tour; |
---|
[1199] | 338 | std::vector<Node> &_notused; |
---|
[1204] | 339 | FullGraph::NodeMap<Cost> _dist; |
---|
| 340 | Comparator _compare; |
---|
[1199] | 341 | }; |
---|
| 342 | |
---|
[1201] | 343 | // Implementation of the cheapest selection rule |
---|
[1199] | 344 | class CheapestSelection { |
---|
| 345 | private: |
---|
| 346 | Cost costDiff(Node u, Node v, Node w) const { |
---|
[1201] | 347 | return |
---|
[1199] | 348 | _cost[_gr.edge(u, w)] + |
---|
| 349 | _cost[_gr.edge(v, w)] - |
---|
| 350 | _cost[_gr.edge(u, v)]; |
---|
| 351 | } |
---|
| 352 | |
---|
| 353 | public: |
---|
| 354 | CheapestSelection(const FullGraph &gr, const CostMap &cost, |
---|
[1204] | 355 | std::vector<Node> &tour, std::vector<Node> ¬used) |
---|
| 356 | : _gr(gr), _cost(cost), _tour(tour), _notused(notused), |
---|
| 357 | _ins_cost(gr, 0), _ins_pos(gr, -1) |
---|
| 358 | { |
---|
| 359 | // Compute insertion cost and position for the unused nodes |
---|
[1199] | 360 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
[1204] | 361 | Node u = _notused[i]; |
---|
| 362 | Cost min_cost = costDiff(_tour.back(), _tour.front(), u); |
---|
[1270] | 363 | int min_pos = 0; |
---|
[1204] | 364 | for (unsigned int j=1; j<_tour.size(); ++j) { |
---|
| 365 | Cost curr_cost = costDiff(_tour[j-1], _tour[j], u); |
---|
| 366 | if (curr_cost < min_cost) { |
---|
| 367 | min_cost = curr_cost; |
---|
| 368 | min_pos = j; |
---|
[1199] | 369 | } |
---|
| 370 | } |
---|
[1204] | 371 | _ins_cost[u] = min_cost; |
---|
| 372 | _ins_pos[u] = min_pos; |
---|
| 373 | } |
---|
| 374 | } |
---|
[1199] | 375 | |
---|
[1204] | 376 | Cost select() { |
---|
| 377 | |
---|
| 378 | // Select an used node with minimum insertion cost |
---|
| 379 | Cost min_cost = 0; |
---|
| 380 | int min_node = -1; |
---|
| 381 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
| 382 | Cost curr_cost = _ins_cost[_notused[i]]; |
---|
| 383 | if (curr_cost < min_cost || min_node == -1) { |
---|
| 384 | min_cost = curr_cost; |
---|
| 385 | min_node = i; |
---|
[1199] | 386 | } |
---|
| 387 | } |
---|
| 388 | |
---|
[1204] | 389 | // Remove the selected node from the unused vector |
---|
| 390 | Node sn = _notused[min_node]; |
---|
| 391 | _notused[min_node] = _notused.back(); |
---|
| 392 | _notused.pop_back(); |
---|
[1270] | 393 | |
---|
[1204] | 394 | // Insert the selected node into the tour |
---|
| 395 | const int ipos = _ins_pos[sn]; |
---|
| 396 | _tour.insert(_tour.begin() + ipos, sn); |
---|
[1199] | 397 | |
---|
[1204] | 398 | // Update the insertion cost and position of the remaining nodes |
---|
| 399 | for (unsigned int i=0; i<_notused.size(); ++i) { |
---|
| 400 | Node u = _notused[i]; |
---|
| 401 | Cost curr_cost = _ins_cost[u]; |
---|
| 402 | int curr_pos = _ins_pos[u]; |
---|
| 403 | |
---|
| 404 | int ipos_prev = ipos == 0 ? _tour.size()-1 : ipos-1; |
---|
| 405 | int ipos_next = ipos == int(_tour.size())-1 ? 0 : ipos+1; |
---|
| 406 | Cost nc1 = costDiff(_tour[ipos_prev], _tour[ipos], u); |
---|
| 407 | Cost nc2 = costDiff(_tour[ipos], _tour[ipos_next], u); |
---|
[1270] | 408 | |
---|
[1204] | 409 | if (nc1 <= curr_cost || nc2 <= curr_cost) { |
---|
| 410 | // A new position is better than the old one |
---|
| 411 | if (nc1 <= nc2) { |
---|
| 412 | curr_cost = nc1; |
---|
| 413 | curr_pos = ipos; |
---|
| 414 | } else { |
---|
| 415 | curr_cost = nc2; |
---|
| 416 | curr_pos = ipos_next; |
---|
| 417 | } |
---|
| 418 | } |
---|
| 419 | else { |
---|
| 420 | if (curr_pos == ipos) { |
---|
| 421 | // The minimum should be found again |
---|
| 422 | curr_cost = costDiff(_tour.back(), _tour.front(), u); |
---|
[1270] | 423 | curr_pos = 0; |
---|
[1204] | 424 | for (unsigned int j=1; j<_tour.size(); ++j) { |
---|
| 425 | Cost tmp_cost = costDiff(_tour[j-1], _tour[j], u); |
---|
| 426 | if (tmp_cost < curr_cost) { |
---|
| 427 | curr_cost = tmp_cost; |
---|
| 428 | curr_pos = j; |
---|
| 429 | } |
---|
| 430 | } |
---|
| 431 | } |
---|
| 432 | else if (curr_pos > ipos) { |
---|
| 433 | ++curr_pos; |
---|
| 434 | } |
---|
| 435 | } |
---|
[1270] | 436 | |
---|
[1204] | 437 | _ins_cost[u] = curr_cost; |
---|
| 438 | _ins_pos[u] = curr_pos; |
---|
| 439 | } |
---|
| 440 | |
---|
| 441 | return min_cost; |
---|
[1199] | 442 | } |
---|
[1201] | 443 | |
---|
[1199] | 444 | private: |
---|
| 445 | const FullGraph &_gr; |
---|
| 446 | const CostMap &_cost; |
---|
[1204] | 447 | std::vector<Node> &_tour; |
---|
[1199] | 448 | std::vector<Node> &_notused; |
---|
[1204] | 449 | FullGraph::NodeMap<Cost> _ins_cost; |
---|
| 450 | FullGraph::NodeMap<int> _ins_pos; |
---|
[1199] | 451 | }; |
---|
| 452 | |
---|
[1201] | 453 | // Implementation of the random selection rule |
---|
[1199] | 454 | class RandomSelection { |
---|
| 455 | public: |
---|
| 456 | RandomSelection(const FullGraph &, const CostMap &, |
---|
[1201] | 457 | std::vector<Node> &, std::vector<Node> ¬used) |
---|
| 458 | : _notused(notused) {} |
---|
| 459 | |
---|
[1199] | 460 | Node select() const { |
---|
| 461 | const int index = rnd[_notused.size()]; |
---|
| 462 | Node n = _notused[index]; |
---|
[1204] | 463 | _notused[index] = _notused.back(); |
---|
| 464 | _notused.pop_back(); |
---|
[1199] | 465 | return n; |
---|
| 466 | } |
---|
[1204] | 467 | |
---|
[1199] | 468 | private: |
---|
| 469 | std::vector<Node> &_notused; |
---|
| 470 | }; |
---|
| 471 | |
---|
| 472 | |
---|
[1201] | 473 | // Implementation of the default insertion method |
---|
| 474 | class DefaultInsertion { |
---|
[1199] | 475 | private: |
---|
| 476 | Cost costDiff(Node u, Node v, Node w) const { |
---|
[1201] | 477 | return |
---|
[1199] | 478 | _cost[_gr.edge(u, w)] + |
---|
| 479 | _cost[_gr.edge(v, w)] - |
---|
| 480 | _cost[_gr.edge(u, v)]; |
---|
| 481 | } |
---|
[1201] | 482 | |
---|
[1199] | 483 | public: |
---|
[1201] | 484 | DefaultInsertion(const FullGraph &gr, const CostMap &cost, |
---|
[1204] | 485 | std::vector<Node> &tour, Cost &total_cost) : |
---|
| 486 | _gr(gr), _cost(cost), _tour(tour), _total(total_cost) {} |
---|
[1201] | 487 | |
---|
[1199] | 488 | void insert(Node n) const { |
---|
| 489 | int min = 0; |
---|
| 490 | Cost min_val = |
---|
[1204] | 491 | costDiff(_tour.front(), _tour.back(), n); |
---|
[1201] | 492 | |
---|
[1204] | 493 | for (unsigned int i=1; i<_tour.size(); ++i) { |
---|
| 494 | Cost tmp = costDiff(_tour[i-1], _tour[i], n); |
---|
[1199] | 495 | if (tmp < min_val) { |
---|
| 496 | min = i; |
---|
| 497 | min_val = tmp; |
---|
| 498 | } |
---|
| 499 | } |
---|
[1201] | 500 | |
---|
[1204] | 501 | _tour.insert(_tour.begin()+min, n); |
---|
[1201] | 502 | _total += min_val; |
---|
[1199] | 503 | } |
---|
[1201] | 504 | |
---|
[1199] | 505 | private: |
---|
| 506 | const FullGraph &_gr; |
---|
| 507 | const CostMap &_cost; |
---|
[1204] | 508 | std::vector<Node> &_tour; |
---|
[1201] | 509 | Cost &_total; |
---|
[1199] | 510 | }; |
---|
[1201] | 511 | |
---|
| 512 | // Implementation of a special insertion method for the cheapest |
---|
| 513 | // selection rule |
---|
| 514 | class CheapestInsertion { |
---|
[1199] | 515 | TEMPLATE_GRAPH_TYPEDEFS(FullGraph); |
---|
| 516 | public: |
---|
[1201] | 517 | CheapestInsertion(const FullGraph &, const CostMap &, |
---|
| 518 | std::vector<Node> &, Cost &total_cost) : |
---|
| 519 | _total(total_cost) {} |
---|
| 520 | |
---|
[1199] | 521 | void insert(Cost diff) const { |
---|
[1201] | 522 | _total += diff; |
---|
[1199] | 523 | } |
---|
| 524 | |
---|
| 525 | private: |
---|
[1201] | 526 | Cost &_total; |
---|
| 527 | }; |
---|
| 528 | |
---|
[1199] | 529 | }; |
---|
[1201] | 530 | |
---|
[1199] | 531 | }; // namespace lemon |
---|
| 532 | |
---|
| 533 | #endif |
---|