1.1 --- a/lemon/opt2_tsp.h Sat Jan 08 22:49:09 2011 +0100
1.2 +++ b/lemon/opt2_tsp.h Sat Jan 08 22:51:16 2011 +0100
1.3 @@ -1,203 +1,354 @@
1.4 +/* -*- mode: C++; indent-tabs-mode: nil; -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library.
1.7 + *
1.8 + * Copyright (C) 2003-2010
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 #ifndef LEMON_OPT2_TSP_H
1.23 #define LEMON_OPT2_TSP_H
1.24
1.25 +/// \ingroup tsp
1.26 +/// \file
1.27 +/// \brief 2-opt algorithm for symmetric TSP
1.28 +
1.29 #include <vector>
1.30 #include <lemon/full_graph.h>
1.31 -#include <lemon/path.h>
1.32
1.33 namespace lemon {
1.34 -
1.35 - namespace opt2_helper {
1.36 - template <class L>
1.37 - L vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.38 - return L(_path.begin(), _path.end());
1.39 - }
1.40 -
1.41 - template <>
1.42 - std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
1.43 - return _path;
1.44 - }
1.45 - }
1.46 -
1.47 +
1.48 + /// \brief 2-opt algorithm for symmetric TSP.
1.49 + ///
1.50 + /// Opt2Tsp implements the 2-opt heuristic for solving
1.51 + /// symmetric \ref tsp "TSP".
1.52 + ///
1.53 + /// This algorithm starts with an initial tour and iteratively improves it.
1.54 + /// At each step, it removes two edges and the reconnects the created two
1.55 + /// paths in the other way if the resulting tour is shorter.
1.56 + /// The algorithm finishes when no such 2-opt move can be applied, and so
1.57 + /// the tour is 2-optimal.
1.58 + ///
1.59 + /// If no starting tour is given to the \ref run() function, then the
1.60 + /// algorithm uses the node sequence determined by the node IDs.
1.61 + /// Oherwise, it starts with the given tour.
1.62 + ///
1.63 + /// This is a relatively slow but powerful method.
1.64 + /// A typical usage of it is the improvement of a solution that is resulted
1.65 + /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm).
1.66 + ///
1.67 + /// \tparam CM Type of the cost map.
1.68 template <typename CM>
1.69 - class Opt2Tsp {
1.70 + class Opt2Tsp
1.71 + {
1.72 + public:
1.73 +
1.74 + /// Type of the cost map
1.75 + typedef CM CostMap;
1.76 + /// Type of the edge costs
1.77 + typedef typename CM::Value Cost;
1.78 +
1.79 private:
1.80 +
1.81 GRAPH_TYPEDEFS(FullGraph);
1.82
1.83 + const FullGraph &_gr;
1.84 + const CostMap &_cost;
1.85 + Cost _sum;
1.86 + std::vector<int> _plist;
1.87 + std::vector<Node> _path;
1.88 +
1.89 public:
1.90 - typedef CM CostMap;
1.91 - typedef typename CM::Value Cost;
1.92 -
1.93 -
1.94 - Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost),
1.95 - tmppath(_gr.nodeNum()*2) {
1.96 -
1.97 - for (int i=1; i<_gr.nodeNum()-1; ++i) {
1.98 - tmppath[2*i] = i-1;
1.99 - tmppath[2*i+1] = i+1;
1.100 +
1.101 + /// \brief Constructor
1.102 + ///
1.103 + /// Constructor.
1.104 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
1.105 + /// \param cost The cost map.
1.106 + Opt2Tsp(const FullGraph &gr, const CostMap &cost)
1.107 + : _gr(gr), _cost(cost) {}
1.108 +
1.109 + /// \name Execution Control
1.110 + /// @{
1.111 +
1.112 + /// \brief Runs the algorithm from scratch.
1.113 + ///
1.114 + /// This function runs the algorithm starting from the tour that is
1.115 + /// determined by the node ID sequence.
1.116 + ///
1.117 + /// \return The total cost of the found tour.
1.118 + Cost run() {
1.119 + _path.clear();
1.120 +
1.121 + if (_gr.nodeNum() == 0) return _sum = 0;
1.122 + else if (_gr.nodeNum() == 1) {
1.123 + _path.push_back(_gr(0));
1.124 + return _sum = 0;
1.125 }
1.126 - tmppath[0] = _gr.nodeNum()-1;
1.127 - tmppath[1] = 1;
1.128 - tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
1.129 - tmppath[2*(_gr.nodeNum()-1)+1] = 0;
1.130 - }
1.131 -
1.132 - Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) :
1.133 - _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
1.134 + else if (_gr.nodeNum() == 2) {
1.135 + _path.push_back(_gr(0));
1.136 + _path.push_back(_gr(1));
1.137 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
1.138 + }
1.139
1.140 - for (unsigned int i=1; i<path.size()-1; ++i) {
1.141 - tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
1.142 - tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
1.143 + _plist.resize(2*_gr.nodeNum());
1.144 + for (int i = 1; i < _gr.nodeNum()-1; ++i) {
1.145 + _plist[2*i] = i-1;
1.146 + _plist[2*i+1] = i+1;
1.147 }
1.148 -
1.149 - tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
1.150 - tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
1.151 - tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
1.152 - tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
1.153 + _plist[0] = _gr.nodeNum()-1;
1.154 + _plist[1] = 1;
1.155 + _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
1.156 + _plist[2*_gr.nodeNum()-1] = 0;
1.157 +
1.158 + return start();
1.159 }
1.160
1.161 + /// \brief Runs the algorithm from the given tour.
1.162 + ///
1.163 + /// This function runs the algorithm starting from the given tour.
1.164 + ///
1.165 + /// \param tour The tour as a path structure. It must be a
1.166 + /// \ref checkPath() "valid path" containing excactly n arcs.
1.167 + ///
1.168 + /// \return The total cost of the found tour.
1.169 + template <typename Path>
1.170 + Cost run(const Path& tour) {
1.171 + _path.clear();
1.172 +
1.173 + if (_gr.nodeNum() == 0) return _sum = 0;
1.174 + else if (_gr.nodeNum() == 1) {
1.175 + _path.push_back(_gr(0));
1.176 + return _sum = 0;
1.177 + }
1.178 + else if (_gr.nodeNum() == 2) {
1.179 + _path.push_back(_gr(0));
1.180 + _path.push_back(_gr(1));
1.181 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
1.182 + }
1.183 +
1.184 + _plist.resize(2*_gr.nodeNum());
1.185 + typename Path::ArcIt it(tour);
1.186 + int first = _gr.id(_gr.source(it)),
1.187 + prev = first,
1.188 + curr = _gr.id(_gr.target(it)),
1.189 + next = -1;
1.190 + _plist[2*first+1] = curr;
1.191 + for (++it; it != INVALID; ++it) {
1.192 + next = _gr.id(_gr.target(it));
1.193 + _plist[2*curr] = prev;
1.194 + _plist[2*curr+1] = next;
1.195 + prev = curr;
1.196 + curr = next;
1.197 + }
1.198 + _plist[2*first] = prev;
1.199 +
1.200 + return start();
1.201 + }
1.202 +
1.203 + /// \brief Runs the algorithm from the given tour.
1.204 + ///
1.205 + /// This function runs the algorithm starting from the given tour.
1.206 + ///
1.207 + /// \param tour The tour as a node sequence. It must be a standard
1.208 + /// sequence container storing all <tt>Node</tt>s in the desired order.
1.209 + ///
1.210 + /// \return The total cost of the found tour.
1.211 + template <template <typename> class Container>
1.212 + Cost run(const Container<Node>& tour) {
1.213 + _path.clear();
1.214 +
1.215 + if (_gr.nodeNum() == 0) return _sum = 0;
1.216 + else if (_gr.nodeNum() == 1) {
1.217 + _path.push_back(_gr(0));
1.218 + return _sum = 0;
1.219 + }
1.220 + else if (_gr.nodeNum() == 2) {
1.221 + _path.push_back(_gr(0));
1.222 + _path.push_back(_gr(1));
1.223 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
1.224 + }
1.225 +
1.226 + _plist.resize(2*_gr.nodeNum());
1.227 + typename Container<Node>::const_iterator it = tour.begin();
1.228 + int first = _gr.id(*it),
1.229 + prev = first,
1.230 + curr = _gr.id(*(++it)),
1.231 + next = -1;
1.232 + _plist[2*first+1] = curr;
1.233 + for (++it; it != tour.end(); ++it) {
1.234 + next = _gr.id(*it);
1.235 + _plist[2*curr] = prev;
1.236 + _plist[2*curr+1] = next;
1.237 + prev = curr;
1.238 + curr = next;
1.239 + }
1.240 + _plist[2*first] = curr;
1.241 + _plist[2*curr] = prev;
1.242 + _plist[2*curr+1] = first;
1.243 +
1.244 + return start();
1.245 + }
1.246 +
1.247 + /// @}
1.248 +
1.249 + /// \name Query Functions
1.250 + /// @{
1.251 +
1.252 + /// \brief The total cost of the found tour.
1.253 + ///
1.254 + /// This function returns the total cost of the found tour.
1.255 + ///
1.256 + /// \pre run() must be called before using this function.
1.257 + Cost tourCost() const {
1.258 + return _sum;
1.259 + }
1.260 +
1.261 + /// \brief Returns a const reference to the node sequence of the
1.262 + /// found tour.
1.263 + ///
1.264 + /// This function returns a const reference to the internal structure
1.265 + /// that stores the node sequence of the found tour.
1.266 + ///
1.267 + /// \pre run() must be called before using this function.
1.268 + const std::vector<Node>& tourNodes() const {
1.269 + return _path;
1.270 + }
1.271 +
1.272 + /// \brief Gives back the node sequence of the found tour.
1.273 + ///
1.274 + /// This function copies the node sequence of the found tour into
1.275 + /// the given standard container.
1.276 + ///
1.277 + /// \pre run() must be called before using this function.
1.278 + template <typename Container>
1.279 + void tourNodes(Container &container) const {
1.280 + container.assign(_path.begin(), _path.end());
1.281 + }
1.282 +
1.283 + /// \brief Gives back the found tour as a path.
1.284 + ///
1.285 + /// This function copies the found tour as a list of arcs/edges into
1.286 + /// the given \ref concept::Path "path structure".
1.287 + ///
1.288 + /// \pre run() must be called before using this function.
1.289 + template <typename Path>
1.290 + void tour(Path &path) const {
1.291 + path.clear();
1.292 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
1.293 + path.addBack(_gr.arc(_path[i], _path[i+1]));
1.294 + }
1.295 + if (int(_path.size()) >= 2) {
1.296 + path.addBack(_gr.arc(_path.back(), _path.front()));
1.297 + }
1.298 + }
1.299 +
1.300 + /// @}
1.301 +
1.302 private:
1.303 - Cost c(int u, int v) {
1.304 - return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
1.305 - }
1.306 -
1.307 - class It {
1.308 +
1.309 + // Iterator class for the linked list storage of the tour
1.310 + class PathListIt {
1.311 public:
1.312 - It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
1.313 - It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
1.314 + PathListIt(const std::vector<int> &pl, int i=0)
1.315 + : plist(&pl), act(i), last(pl[2*act]) {}
1.316 + PathListIt(const std::vector<int> &pl, int i, int l)
1.317 + : plist(&pl), act(i), last(l) {}
1.318
1.319 - int next_index() const {
1.320 - return (tmppath[2*act]==last)? 2*act+1 : 2*act;
1.321 + int nextIndex() const {
1.322 + return (*plist)[2*act] == last ? 2*act+1 : 2*act;
1.323 }
1.324 -
1.325 - int prev_index() const {
1.326 - return (tmppath[2*act]==last)? 2*act : 2*act+1;
1.327 +
1.328 + int prevIndex() const {
1.329 + return (*plist)[2*act] == last ? 2*act : 2*act+1;
1.330 }
1.331 -
1.332 +
1.333 int next() const {
1.334 - return tmppath[next_index()];
1.335 + int x = (*plist)[2*act];
1.336 + return x == last ? (*plist)[2*act+1] : x;
1.337 }
1.338
1.339 int prev() const {
1.340 - return tmppath[prev_index()];
1.341 + return last;
1.342 }
1.343 -
1.344 - It& operator++() {
1.345 +
1.346 + PathListIt& operator++() {
1.347 int tmp = act;
1.348 act = next();
1.349 last = tmp;
1.350 return *this;
1.351 }
1.352 -
1.353 +
1.354 operator int() const {
1.355 return act;
1.356 }
1.357 -
1.358 +
1.359 private:
1.360 - const std::vector<int> &tmppath;
1.361 + const std::vector<int> *plist;
1.362 int act;
1.363 int last;
1.364 };
1.365
1.366 - bool check(std::vector<int> &path, It i, It j) {
1.367 - if (c(i, i.next()) + c(j, j.next()) >
1.368 - c(i, j) + c(j.next(), i.next())) {
1.369 + // Checks and applies 2-opt move (if it improves the tour)
1.370 + bool checkOpt2(const PathListIt& i, const PathListIt& j) {
1.371 + Node u = _gr.nodeFromId(i),
1.372 + un = _gr.nodeFromId(i.next()),
1.373 + v = _gr.nodeFromId(j),
1.374 + vn = _gr.nodeFromId(j.next());
1.375
1.376 - path[ It(path, i.next(), i).prev_index() ] = j.next();
1.377 - path[ It(path, j.next(), j).prev_index() ] = i.next();
1.378 + if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
1.379 + _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
1.380 + {
1.381 + _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
1.382 + _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
1.383
1.384 - path[i.next_index()] = j;
1.385 - path[j.next_index()] = i;
1.386 + _plist[i.nextIndex()] = j;
1.387 + _plist[j.nextIndex()] = i;
1.388
1.389 - return true;
1.390 + return true;
1.391 }
1.392 +
1.393 return false;
1.394 - }
1.395 -
1.396 - public:
1.397 -
1.398 - Cost run() {
1.399 - _path.clear();
1.400 + }
1.401
1.402 - if (_gr.nodeNum()>3) {
1.403 + // Executes the algorithm from the initial tour
1.404 + Cost start() {
1.405
1.406 -opt2_tsp_label:
1.407 - It i(tmppath);
1.408 - It j(tmppath, i, i.prev());
1.409 - ++j; ++j;
1.410 - for (; j.next()!=0; ++j) {
1.411 - if (check(tmppath, i, j))
1.412 - goto opt2_tsp_label;
1.413 - }
1.414 -
1.415 - for (++i; i.next()!=0; ++i) {
1.416 - It j(tmppath, i, i.prev());
1.417 - if (++j==0)
1.418 - break;
1.419 - if (++j==0)
1.420 - break;
1.421 -
1.422 - for (; j!=0; ++j) {
1.423 - if (check(tmppath, i, j))
1.424 - goto opt2_tsp_label;
1.425 - }
1.426 + restart_search:
1.427 + for (PathListIt i(_plist); true; ++i) {
1.428 + PathListIt j = i;
1.429 + if (++j == 0 || ++j == 0) break;
1.430 + for (; j != 0 && j != i.prev(); ++j) {
1.431 + if (checkOpt2(i, j))
1.432 + goto restart_search;
1.433 }
1.434 }
1.435
1.436 - It k(tmppath);
1.437 - _path.push_back(_gr.nodeFromId(k));
1.438 - for (++k; k!=0; ++k)
1.439 - _path.push_back(_gr.nodeFromId(k));
1.440 + PathListIt i(_plist);
1.441 + _path.push_back(_gr.nodeFromId(i));
1.442 + for (++i; i != 0; ++i)
1.443 + _path.push_back(_gr.nodeFromId(i));
1.444
1.445 -
1.446 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
1.447 + for (int i = 0; i < int(_path.size())-1; ++i) {
1.448 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
1.449 + }
1.450
1.451 - _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
1.452 - for (unsigned int i=0; i<_path.size()-1; ++i)
1.453 - _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
1.454 return _sum;
1.455 }
1.456
1.457 -
1.458 - template <typename L>
1.459 - void tourNodes(L &container) {
1.460 - container(opt2_helper::vectorConvert<L>(_path));
1.461 - }
1.462 -
1.463 - template <template <typename> class L>
1.464 - L<Node> tourNodes() {
1.465 - return opt2_helper::vectorConvert<L<Node> >(_path);
1.466 - }
1.467 -
1.468 - const std::vector<Node>& tourNodes() {
1.469 - return _path;
1.470 - }
1.471 -
1.472 - Path<FullGraph> tour() {
1.473 - Path<FullGraph> p;
1.474 - if (_path.size()<2)
1.475 - return p;
1.476 -
1.477 - for (unsigned int i=0; i<_path.size()-1; ++i) {
1.478 - p.addBack(_gr.arc(_path[i], _path[i+1]));
1.479 - }
1.480 - p.addBack(_gr.arc(_path.back(), _path.front()));
1.481 - return p;
1.482 - }
1.483 -
1.484 - Cost tourCost() {
1.485 - return _sum;
1.486 - }
1.487 -
1.488 -
1.489 - private:
1.490 - const FullGraph &_gr;
1.491 - const CostMap &_cost;
1.492 - Cost _sum;
1.493 - std::vector<int> tmppath;
1.494 - std::vector<Node> _path;
1.495 };
1.496
1.497 -
1.498 }; // namespace lemon
1.499
1.500 #endif