COIN-OR::LEMON - Graph Library

Changeset 1201:9a51db038228 in lemon for lemon/opt2_tsp.h


Ignore:
Timestamp:
01/08/11 22:51:16 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Document and greatly improve TSP algorithms (#386)

  • Add LEMON headers.
  • Add Doxygen doc for all classes and their members.
  • Clarify and unify the public API of the algorithms.
  • Various small improvements in the implementations to make them clearer and faster.
  • Avoid using adaptors in ChristofidesTsp?.
File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/opt2_tsp.h

    r1199 r1201  
     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
    119#ifndef LEMON_OPT2_TSP_H
    220#define LEMON_OPT2_TSP_H
    321
     22/// \ingroup tsp
     23/// \file
     24/// \brief 2-opt algorithm for symmetric TSP
     25
    426#include <vector>
    527#include <lemon/full_graph.h>
    6 #include <lemon/path.h>
    728
    829namespace lemon {
    9  
    10   namespace opt2_helper {
    11     template <class L>
    12     L vectorConvert(const std::vector<FullGraph::Node> &_path) {
    13       return L(_path.begin(), _path.end());
    14     }
    15  
    16     template <>
    17     std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) {
    18       return _path;
    19     }
    20   }
    21  
     30
     31  /// \brief 2-opt algorithm for symmetric TSP.
     32  ///
     33  /// Opt2Tsp implements the 2-opt heuristic for solving
     34  /// symmetric \ref tsp "TSP".
     35  ///
     36  /// This algorithm starts with an initial tour and iteratively improves it.
     37  /// At each step, it removes two edges and the reconnects the created two
     38  /// paths in the other way if the resulting tour is shorter.
     39  /// The algorithm finishes when no such 2-opt move can be applied, and so
     40  /// the tour is 2-optimal.
     41  ///
     42  /// If no starting tour is given to the \ref run() function, then the
     43  /// algorithm uses the node sequence determined by the node IDs.
     44  /// Oherwise, it starts with the given tour.
     45  ///
     46  /// This is a relatively slow but powerful method.
     47  /// A typical usage of it is the improvement of a solution that is resulted
     48  /// by a fast tour construction heuristic (e.g. the InsertionTsp algorithm).
     49  ///
     50  /// \tparam CM Type of the cost map.
    2251  template <typename CM>
    23   class Opt2Tsp {
     52  class Opt2Tsp
     53  {
     54    public:
     55
     56      /// Type of the cost map
     57      typedef CM CostMap;
     58      /// Type of the edge costs
     59      typedef typename CM::Value Cost;
     60
    2461    private:
     62
    2563      GRAPH_TYPEDEFS(FullGraph);
    2664
     65      const FullGraph &_gr;
     66      const CostMap &_cost;
     67      Cost _sum;
     68      std::vector<int> _plist;
     69      std::vector<Node> _path;
     70
    2771    public:
    28       typedef CM CostMap;
    29       typedef typename CM::Value Cost;
    30      
    31    
    32       Opt2Tsp(const FullGraph &gr, const CostMap &cost) : _gr(gr), _cost(cost),
    33             tmppath(_gr.nodeNum()*2) {
    34            
    35         for (int i=1; i<_gr.nodeNum()-1; ++i) {
    36           tmppath[2*i] = i-1;
    37           tmppath[2*i+1] = i+1;
    38         }
    39         tmppath[0] = _gr.nodeNum()-1;
    40         tmppath[1] = 1;
    41         tmppath[2*(_gr.nodeNum()-1)] = _gr.nodeNum()-2;
    42         tmppath[2*(_gr.nodeNum()-1)+1] = 0;
    43       }
    44      
    45       Opt2Tsp(const FullGraph &gr, const CostMap &cost, const std::vector<Node> &path) :
    46               _gr(gr), _cost(cost), tmppath(_gr.nodeNum()*2) {
    47 
    48         for (unsigned int i=1; i<path.size()-1; ++i) {
    49           tmppath[2*_gr.id(path[i])] = _gr.id(path[i-1]);
    50           tmppath[2*_gr.id(path[i])+1] = _gr.id(path[i+1]);
    51         }
    52        
    53         tmppath[2*_gr.id(path[0])] = _gr.id(path.back());
    54         tmppath[2*_gr.id(path[0])+1] = _gr.id(path[1]);
    55         tmppath[2*_gr.id(path.back())] = _gr.id(path[path.size()-2]);
    56         tmppath[2*_gr.id(path.back())+1] = _gr.id(path.front());
    57       }
     72
     73      /// \brief Constructor
     74      ///
     75      /// Constructor.
     76      /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
     77      /// \param cost The cost map.
     78      Opt2Tsp(const FullGraph &gr, const CostMap &cost)
     79        : _gr(gr), _cost(cost) {}
     80
     81      /// \name Execution Control
     82      /// @{
     83
     84      /// \brief Runs the algorithm from scratch.
     85      ///
     86      /// This function runs the algorithm starting from the tour that is
     87      /// determined by the node ID sequence.
     88      ///
     89      /// \return The total cost of the found tour.
     90      Cost run() {
     91        _path.clear();
     92
     93        if (_gr.nodeNum() == 0) return _sum = 0;
     94        else if (_gr.nodeNum() == 1) {
     95          _path.push_back(_gr(0));
     96          return _sum = 0;
     97        }
     98        else if (_gr.nodeNum() == 2) {
     99          _path.push_back(_gr(0));
     100          _path.push_back(_gr(1));
     101          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
     102        }
     103
     104        _plist.resize(2*_gr.nodeNum());
     105        for (int i = 1; i < _gr.nodeNum()-1; ++i) {
     106          _plist[2*i] = i-1;
     107          _plist[2*i+1] = i+1;
     108        }
     109        _plist[0] = _gr.nodeNum()-1;
     110        _plist[1] = 1;
     111        _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2;
     112        _plist[2*_gr.nodeNum()-1] = 0;
     113
     114        return start();
     115      }
     116
     117      /// \brief Runs the algorithm from the given tour.
     118      ///
     119      /// This function runs the algorithm starting from the given tour.
     120      ///
     121      /// \param tour The tour as a path structure. It must be a
     122      /// \ref checkPath() "valid path" containing excactly n arcs.
     123      ///
     124      /// \return The total cost of the found tour.
     125      template <typename Path>
     126      Cost run(const Path& tour) {
     127        _path.clear();
     128
     129        if (_gr.nodeNum() == 0) return _sum = 0;
     130        else if (_gr.nodeNum() == 1) {
     131          _path.push_back(_gr(0));
     132          return _sum = 0;
     133        }
     134        else if (_gr.nodeNum() == 2) {
     135          _path.push_back(_gr(0));
     136          _path.push_back(_gr(1));
     137          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
     138        }
     139
     140        _plist.resize(2*_gr.nodeNum());
     141        typename Path::ArcIt it(tour);
     142        int first = _gr.id(_gr.source(it)),
     143            prev = first,
     144            curr = _gr.id(_gr.target(it)),
     145            next = -1;
     146        _plist[2*first+1] = curr;
     147        for (++it; it != INVALID; ++it) {
     148          next = _gr.id(_gr.target(it));
     149          _plist[2*curr] = prev;
     150          _plist[2*curr+1] = next;
     151          prev = curr;
     152          curr = next;
     153        }
     154        _plist[2*first] = prev;
     155
     156        return start();
     157      }
     158
     159      /// \brief Runs the algorithm from the given tour.
     160      ///
     161      /// This function runs the algorithm starting from the given tour.
     162      ///
     163      /// \param tour The tour as a node sequence. It must be a standard
     164      /// sequence container storing all <tt>Node</tt>s in the desired order.
     165      ///
     166      /// \return The total cost of the found tour.
     167      template <template <typename> class Container>
     168      Cost run(const Container<Node>& tour) {
     169        _path.clear();
     170
     171        if (_gr.nodeNum() == 0) return _sum = 0;
     172        else if (_gr.nodeNum() == 1) {
     173          _path.push_back(_gr(0));
     174          return _sum = 0;
     175        }
     176        else if (_gr.nodeNum() == 2) {
     177          _path.push_back(_gr(0));
     178          _path.push_back(_gr(1));
     179          return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
     180        }
     181
     182        _plist.resize(2*_gr.nodeNum());
     183        typename Container<Node>::const_iterator it = tour.begin();
     184        int first = _gr.id(*it),
     185            prev = first,
     186            curr = _gr.id(*(++it)),
     187            next = -1;
     188        _plist[2*first+1] = curr;
     189        for (++it; it != tour.end(); ++it) {
     190          next = _gr.id(*it);
     191          _plist[2*curr] = prev;
     192          _plist[2*curr+1] = next;
     193          prev = curr;
     194          curr = next;
     195        }
     196        _plist[2*first] = curr;
     197        _plist[2*curr] = prev;
     198        _plist[2*curr+1] = first;
     199
     200        return start();
     201      }
     202
     203      /// @}
     204
     205      /// \name Query Functions
     206      /// @{
     207
     208      /// \brief The total cost of the found tour.
     209      ///
     210      /// This function returns the total cost of the found tour.
     211      ///
     212      /// \pre run() must be called before using this function.
     213      Cost tourCost() const {
     214        return _sum;
     215      }
     216
     217      /// \brief Returns a const reference to the node sequence of the
     218      /// found tour.
     219      ///
     220      /// This function returns a const reference to the internal structure
     221      /// that stores the node sequence of the found tour.
     222      ///
     223      /// \pre run() must be called before using this function.
     224      const std::vector<Node>& tourNodes() const {
     225        return _path;
     226      }
     227
     228      /// \brief Gives back the node sequence of the found tour.
     229      ///
     230      /// This function copies the node sequence of the found tour into
     231      /// the given standard container.
     232      ///
     233      /// \pre run() must be called before using this function.
     234      template <typename Container>
     235      void tourNodes(Container &container) const {
     236        container.assign(_path.begin(), _path.end());
     237      }
     238
     239      /// \brief Gives back the found tour as a path.
     240      ///
     241      /// This function copies the found tour as a list of arcs/edges into
     242      /// the given \ref concept::Path "path structure".
     243      ///
     244      /// \pre run() must be called before using this function.
     245      template <typename Path>
     246      void tour(Path &path) const {
     247        path.clear();
     248        for (int i = 0; i < int(_path.size()) - 1; ++i) {
     249          path.addBack(_gr.arc(_path[i], _path[i+1]));
     250        }
     251        if (int(_path.size()) >= 2) {
     252          path.addBack(_gr.arc(_path.back(), _path.front()));
     253        }
     254      }
     255
     256      /// @}
    58257
    59258    private:
    60       Cost c(int u, int v) {
    61         return _cost[_gr.edge(_gr.nodeFromId(u), _gr.nodeFromId(v))];
    62       }
    63      
    64       class It {
     259
     260      // Iterator class for the linked list storage of the tour
     261      class PathListIt {
    65262        public:
    66           It(const std::vector<int> &path, int i=0) : tmppath(path), act(i), last(tmppath[2*act]) {}
    67           It(const std::vector<int> &path, int i, int l) : tmppath(path), act(i), last(l) {}
    68 
    69           int next_index() const {
    70             return (tmppath[2*act]==last)? 2*act+1 : 2*act;
    71           }
    72          
    73           int prev_index() const {
    74             return (tmppath[2*act]==last)? 2*act : 2*act+1;
    75           }
    76          
     263          PathListIt(const std::vector<int> &pl, int i=0)
     264            : plist(&pl), act(i), last(pl[2*act]) {}
     265          PathListIt(const std::vector<int> &pl, int i, int l)
     266            : plist(&pl), act(i), last(l) {}
     267
     268          int nextIndex() const {
     269            return (*plist)[2*act] == last ? 2*act+1 : 2*act;
     270          }
     271
     272          int prevIndex() const {
     273            return (*plist)[2*act] == last ? 2*act : 2*act+1;
     274          }
     275
    77276          int next() const {
    78             return tmppath[next_index()];
     277            int x = (*plist)[2*act];
     278            return x == last ? (*plist)[2*act+1] : x;
    79279          }
    80280
    81281          int prev() const {
    82             return tmppath[prev_index()];
    83           }
    84          
    85           It& operator++() {
     282            return last;
     283          }
     284
     285          PathListIt& operator++() {
    86286            int tmp = act;
    87287            act = next();
     
    89289            return *this;
    90290          }
    91          
     291
    92292          operator int() const {
    93293            return act;
    94294          }
    95          
     295
    96296        private:
    97           const std::vector<int> &tmppath;
     297          const std::vector<int> *plist;
    98298          int act;
    99299          int last;
    100300      };
    101301
    102       bool check(std::vector<int> &path, It i, It j) {
    103         if (c(i, i.next()) + c(j, j.next()) >
    104             c(i, j) + c(j.next(), i.next())) {
    105 
    106             path[ It(path, i.next(), i).prev_index() ] = j.next();
    107             path[ It(path, j.next(), j).prev_index() ] = i.next();
    108 
    109             path[i.next_index()] = j;
    110             path[j.next_index()] = i;
    111 
    112             return true;
    113         }
     302      // Checks and applies 2-opt move (if it improves the tour)
     303      bool checkOpt2(const PathListIt& i, const PathListIt& j) {
     304        Node u  = _gr.nodeFromId(i),
     305             un = _gr.nodeFromId(i.next()),
     306             v  = _gr.nodeFromId(j),
     307             vn = _gr.nodeFromId(j.next());
     308
     309        if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] >
     310            _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)])
     311        {
     312          _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next();
     313          _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next();
     314
     315          _plist[i.nextIndex()] = j;
     316          _plist[j.nextIndex()] = i;
     317
     318          return true;
     319        }
     320
    114321        return false;
    115       }
    116      
    117     public:
    118      
    119       Cost run() {
    120         _path.clear();
    121 
    122         if (_gr.nodeNum()>3) {
    123 
    124 opt2_tsp_label:
    125           It i(tmppath);
    126           It j(tmppath, i, i.prev());
    127           ++j; ++j;
    128           for (; j.next()!=0; ++j) {
    129             if (check(tmppath, i, j))
    130               goto opt2_tsp_label;
    131           }
    132          
    133           for (++i; i.next()!=0; ++i) {
    134             It j(tmppath, i, i.prev());
    135             if (++j==0)
    136               break;
    137             if (++j==0)
    138               break;
    139            
    140             for (; j!=0; ++j) {
    141               if (check(tmppath, i, j))
    142                 goto opt2_tsp_label;
    143             }
    144           }
    145         }
    146 
    147         It k(tmppath);
    148         _path.push_back(_gr.nodeFromId(k));
    149         for (++k; k!=0; ++k)
    150           _path.push_back(_gr.nodeFromId(k));
    151 
    152        
    153 
    154         _sum = _cost[ _gr.edge(_path.back(), _path.front()) ];
    155         for (unsigned int i=0; i<_path.size()-1; ++i)
    156           _sum += _cost[ _gr.edge(_path[i], _path[i+1]) ];
     322     }
     323
     324      // Executes the algorithm from the initial tour
     325      Cost start() {
     326
     327      restart_search:
     328        for (PathListIt i(_plist); true; ++i) {
     329          PathListIt j = i;
     330          if (++j == 0 || ++j == 0) break;
     331          for (; j != 0 && j != i.prev(); ++j) {
     332            if (checkOpt2(i, j))
     333              goto restart_search;
     334          }
     335        }
     336
     337        PathListIt i(_plist);
     338        _path.push_back(_gr.nodeFromId(i));
     339        for (++i; i != 0; ++i)
     340          _path.push_back(_gr.nodeFromId(i));
     341
     342        _sum = _cost[_gr.edge(_path.back(), _path.front())];
     343        for (int i = 0; i < int(_path.size())-1; ++i) {
     344          _sum += _cost[_gr.edge(_path[i], _path[i+1])];
     345        }
     346
    157347        return _sum;
    158348      }
    159349
    160      
    161       template <typename L>
    162       void tourNodes(L &container) {
    163         container(opt2_helper::vectorConvert<L>(_path));
    164       }
    165      
    166       template <template <typename> class L>
    167       L<Node> tourNodes() {
    168         return opt2_helper::vectorConvert<L<Node> >(_path);
    169       }
    170 
    171       const std::vector<Node>& tourNodes() {
    172         return _path;
    173       }
    174      
    175       Path<FullGraph> tour() {
    176         Path<FullGraph> p;
    177         if (_path.size()<2)
    178           return p;
    179 
    180         for (unsigned int i=0; i<_path.size()-1; ++i) {
    181           p.addBack(_gr.arc(_path[i], _path[i+1]));
    182         }
    183         p.addBack(_gr.arc(_path.back(), _path.front()));
    184         return p;
    185       }
    186      
    187       Cost tourCost() {
    188         return _sum;
    189       }
    190      
    191 
    192   private:
    193     const FullGraph &_gr;
    194     const CostMap &_cost;
    195     Cost _sum;
    196     std::vector<int> tmppath;
    197     std::vector<Node> _path;
    198350  };
    199351
    200 
    201352}; // namespace lemon
    202353
Note: See TracChangeset for help on using the changeset viewer.