1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/opt2_tsp.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -0,0 +1,367 @@
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-2013
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 +
1.32 +namespace lemon {
1.33 +
1.34 + /// \ingroup tsp
1.35 + ///
1.36 + /// \brief 2-opt algorithm for symmetric TSP.
1.37 + ///
1.38 + /// Opt2Tsp implements the 2-opt heuristic for solving
1.39 + /// symmetric \ref tsp "TSP".
1.40 + ///
1.41 + /// This algorithm starts with an initial tour and iteratively improves it.
1.42 + /// At each step, it removes two edges and the reconnects the created two
1.43 + /// paths in the other way if the resulting tour is shorter.
1.44 + /// The algorithm finishes when no such 2-opt move can be applied, and so
1.45 + /// the tour is 2-optimal.
1.46 + ///
1.47 + /// If no starting tour is given to the \ref run() function, then the
1.48 + /// algorithm uses the node sequence determined by the node IDs.
1.49 + /// Oherwise, it starts with the given tour.
1.50 + ///
1.51 + /// This is a rather slow but effective method.
1.52 + /// Its typical usage is the improvement of the result of a fast tour
1.53 + /// construction heuristic (e.g. the InsertionTsp algorithm).
1.54 + ///
1.55 + /// \tparam CM Type of the cost map.
1.56 + template <typename CM>
1.57 + class Opt2Tsp
1.58 + {
1.59 + public:
1.60 +
1.61 + /// Type of the cost map
1.62 + typedef CM CostMap;
1.63 + /// Type of the edge costs
1.64 + typedef typename CM::Value Cost;
1.65 +
1.66 + private:
1.67 +
1.68 + GRAPH_TYPEDEFS(FullGraph);
1.69 +
1.70 + const FullGraph &_gr;
1.71 + const CostMap &_cost;
1.72 + Cost _sum;
1.73 + std::vector<int> _plist;
1.74 + std::vector<Node> _path;
1.75 +
1.76 + public:
1.77 +
1.78 + /// \brief Constructor
1.79 + ///
1.80 + /// Constructor.
1.81 + /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
1.82 + /// \param cost The cost map.
1.83 + Opt2Tsp(const FullGraph &gr, const CostMap &cost)
1.84 + : _gr(gr), _cost(cost) {}
1.85 +
1.86 + /// \name Execution Control
1.87 + /// @{
1.88 +
1.89 + /// \brief Runs the algorithm from scratch.
1.90 + ///
1.91 + /// This function runs the algorithm starting from the tour that is
1.92 + /// determined by the node ID sequence.
1.93 + ///
1.94 + /// \return The total cost of the found tour.
1.95 + Cost run() {
1.96 + _path.clear();
1.97 +
1.98 + if (_gr.nodeNum() == 0) return _sum = 0;
1.99 + else if (_gr.nodeNum() == 1) {
1.100 + _path.push_back(_gr(0));
1.101 + return _sum = 0;
1.102 + }
1.103 + else if (_gr.nodeNum() == 2) {
1.104 + _path.push_back(_gr(0));
1.105 + _path.push_back(_gr(1));
1.106 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
1.107 + }
1.108 +
1.109 + _plist.resize(2*_gr.nodeNum());
1.110 + for (int i = 1; i < _gr.nodeNum()-1; ++i) {
1.111 + _plist[2*i] = i-1;
1.112 + _plist[2*i+1] = i+1;
1.113 + }
1.114 + _plist[0] = _gr.nodeNum()-1;
1.115 + _plist[1] = 1;
1.116 + _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
1.117 + _plist[2*_gr.nodeNum()-1] = 0;
1.118 +
1.119 + return start();
1.120 + }
1.121 +
1.122 + /// \brief Runs the algorithm starting from the given tour.
1.123 + ///
1.124 + /// This function runs the algorithm starting from the given tour.
1.125 + ///
1.126 + /// \param tour The tour as a path structure. It must be a
1.127 + /// \ref checkPath() "valid path" containing excactly n arcs.
1.128 + ///
1.129 + /// \return The total cost of the found tour.
1.130 + template <typename Path>
1.131 + Cost run(const Path& tour) {
1.132 + _path.clear();
1.133 +
1.134 + if (_gr.nodeNum() == 0) return _sum = 0;
1.135 + else if (_gr.nodeNum() == 1) {
1.136 + _path.push_back(_gr(0));
1.137 + return _sum = 0;
1.138 + }
1.139 + else if (_gr.nodeNum() == 2) {
1.140 + _path.push_back(_gr(0));
1.141 + _path.push_back(_gr(1));
1.142 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
1.143 + }
1.144 +
1.145 + _plist.resize(2*_gr.nodeNum());
1.146 + typename Path::ArcIt it(tour);
1.147 + int first = _gr.id(_gr.source(it)),
1.148 + prev = first,
1.149 + curr = _gr.id(_gr.target(it)),
1.150 + next = -1;
1.151 + _plist[2*first+1] = curr;
1.152 + for (++it; it != INVALID; ++it) {
1.153 + next = _gr.id(_gr.target(it));
1.154 + _plist[2*curr] = prev;
1.155 + _plist[2*curr+1] = next;
1.156 + prev = curr;
1.157 + curr = next;
1.158 + }
1.159 + _plist[2*first] = prev;
1.160 +
1.161 + return start();
1.162 + }
1.163 +
1.164 + /// \brief Runs the algorithm starting from the given tour.
1.165 + ///
1.166 + /// This function runs the algorithm starting from the given tour
1.167 + /// (node sequence).
1.168 + ///
1.169 + /// \param tour A vector that stores all <tt>Node</tt>s of the graph
1.170 + /// in the desired order.
1.171 + ///
1.172 + /// \return The total cost of the found tour.
1.173 + Cost run(const std::vector<Node>& tour) {
1.174 + _path.clear();
1.175 +
1.176 + if (_gr.nodeNum() == 0) return _sum = 0;
1.177 + else if (_gr.nodeNum() == 1) {
1.178 + _path.push_back(_gr(0));
1.179 + return _sum = 0;
1.180 + }
1.181 + else if (_gr.nodeNum() == 2) {
1.182 + _path.push_back(_gr(0));
1.183 + _path.push_back(_gr(1));
1.184 + return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
1.185 + }
1.186 +
1.187 + _plist.resize(2*_gr.nodeNum());
1.188 + typename std::vector<Node>::const_iterator it = tour.begin();
1.189 + int first = _gr.id(*it),
1.190 + prev = first,
1.191 + curr = _gr.id(*(++it)),
1.192 + next = -1;
1.193 + _plist[2*first+1] = curr;
1.194 + for (++it; it != tour.end(); ++it) {
1.195 + next = _gr.id(*it);
1.196 + _plist[2*curr] = prev;
1.197 + _plist[2*curr+1] = next;
1.198 + prev = curr;
1.199 + curr = next;
1.200 + }
1.201 + _plist[2*first] = curr;
1.202 + _plist[2*curr] = prev;
1.203 + _plist[2*curr+1] = first;
1.204 +
1.205 + return start();
1.206 + }
1.207 +
1.208 + /// @}
1.209 +
1.210 + /// \name Query Functions
1.211 + /// @{
1.212 +
1.213 + /// \brief The total cost of the found tour.
1.214 + ///
1.215 + /// This function returns the total cost of the found tour.
1.216 + ///
1.217 + /// \pre run() must be called before using this function.
1.218 + Cost tourCost() const {
1.219 + return _sum;
1.220 + }
1.221 +
1.222 + /// \brief Returns a const reference to the node sequence of the
1.223 + /// found tour.
1.224 + ///
1.225 + /// This function returns a const reference to a vector
1.226 + /// that stores the node sequence of the found tour.
1.227 + ///
1.228 + /// \pre run() must be called before using this function.
1.229 + const std::vector<Node>& tourNodes() const {
1.230 + return _path;
1.231 + }
1.232 +
1.233 + /// \brief Gives back the node sequence of the found tour.
1.234 + ///
1.235 + /// This function copies the node sequence of the found tour into
1.236 + /// an STL container through the given output iterator. The
1.237 + /// <tt>value_type</tt> of the container must be <tt>FullGraph::Node</tt>.
1.238 + /// For example,
1.239 + /// \code
1.240 + /// std::vector<FullGraph::Node> nodes(countNodes(graph));
1.241 + /// tsp.tourNodes(nodes.begin());
1.242 + /// \endcode
1.243 + /// or
1.244 + /// \code
1.245 + /// std::list<FullGraph::Node> nodes;
1.246 + /// tsp.tourNodes(std::back_inserter(nodes));
1.247 + /// \endcode
1.248 + ///
1.249 + /// \pre run() must be called before using this function.
1.250 + template <typename Iterator>
1.251 + void tourNodes(Iterator out) const {
1.252 + std::copy(_path.begin(), _path.end(), out);
1.253 + }
1.254 +
1.255 + /// \brief Gives back the found tour as a path.
1.256 + ///
1.257 + /// This function copies the found tour as a list of arcs/edges into
1.258 + /// the given \ref lemon::concepts::Path "path structure".
1.259 + ///
1.260 + /// \pre run() must be called before using this function.
1.261 + template <typename Path>
1.262 + void tour(Path &path) const {
1.263 + path.clear();
1.264 + for (int i = 0; i < int(_path.size()) - 1; ++i) {
1.265 + path.addBack(_gr.arc(_path[i], _path[i+1]));
1.266 + }
1.267 + if (int(_path.size()) >= 2) {
1.268 + path.addBack(_gr.arc(_path.back(), _path.front()));
1.269 + }
1.270 + }
1.271 +
1.272 + /// @}
1.273 +
1.274 + private:
1.275 +
1.276 + // Iterator class for the linked list storage of the tour
1.277 + class PathListIt {
1.278 + public:
1.279 + PathListIt(const std::vector<int> &pl, int i=0)
1.280 + : plist(&pl), act(i), last(pl[2*act]) {}
1.281 + PathListIt(const std::vector<int> &pl, int i, int l)
1.282 + : plist(&pl), act(i), last(l) {}
1.283 +
1.284 + int nextIndex() const {
1.285 + return (*plist)[2*act] == last ? 2*act+1 : 2*act;
1.286 + }
1.287 +
1.288 + int prevIndex() const {
1.289 + return (*plist)[2*act] == last ? 2*act : 2*act+1;
1.290 + }
1.291 +
1.292 + int next() const {
1.293 + int x = (*plist)[2*act];
1.294 + return x == last ? (*plist)[2*act+1] : x;
1.295 + }
1.296 +
1.297 + int prev() const {
1.298 + return last;
1.299 + }
1.300 +
1.301 + PathListIt& operator++() {
1.302 + int tmp = act;
1.303 + act = next();
1.304 + last = tmp;
1.305 + return *this;
1.306 + }
1.307 +
1.308 + operator int() const {
1.309 + return act;
1.310 + }
1.311 +
1.312 + private:
1.313 + const std::vector<int> *plist;
1.314 + int act;
1.315 + int last;
1.316 + };
1.317 +
1.318 + // Checks and applies 2-opt move (if it improves the tour)
1.319 + bool checkOpt2(const PathListIt& i, const PathListIt& j) {
1.320 + Node u = _gr.nodeFromId(i),
1.321 + un = _gr.nodeFromId(i.next()),
1.322 + v = _gr.nodeFromId(j),
1.323 + vn = _gr.nodeFromId(j.next());
1.324 +
1.325 + if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
1.326 + _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
1.327 + {
1.328 + _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
1.329 + _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
1.330 +
1.331 + _plist[i.nextIndex()] = j;
1.332 + _plist[j.nextIndex()] = i;
1.333 +
1.334 + return true;
1.335 + }
1.336 +
1.337 + return false;
1.338 + }
1.339 +
1.340 + // Executes the algorithm from the initial tour
1.341 + Cost start() {
1.342 +
1.343 + restart_search:
1.344 + for (PathListIt i(_plist); true; ++i) {
1.345 + PathListIt j = i;
1.346 + if (++j == 0 || ++j == 0) break;
1.347 + for (; j != 0 && j != i.prev(); ++j) {
1.348 + if (checkOpt2(i, j))
1.349 + goto restart_search;
1.350 + }
1.351 + }
1.352 +
1.353 + PathListIt i(_plist);
1.354 + _path.push_back(_gr.nodeFromId(i));
1.355 + for (++i; i != 0; ++i)
1.356 + _path.push_back(_gr.nodeFromId(i));
1.357 +
1.358 + _sum = _cost[_gr.edge(_path.back(), _path.front())];
1.359 + for (int i = 0; i < int(_path.size())-1; ++i) {
1.360 + _sum += _cost[_gr.edge(_path[i], _path[i+1])];
1.361 + }
1.362 +
1.363 + return _sum;
1.364 + }
1.365 +
1.366 + };
1.367 +
1.368 +}; // namespace lemon
1.369 +
1.370 +#endif