kpeter@1033: /* -*- mode: C++; indent-tabs-mode: nil; -*- kpeter@1033: * kpeter@1033: * This file is a part of LEMON, a generic C++ optimization library. kpeter@1033: * kpeter@1033: * Copyright (C) 2003-2010 kpeter@1033: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport kpeter@1033: * (Egervary Research Group on Combinatorial Optimization, EGRES). kpeter@1033: * kpeter@1033: * Permission to use, modify and distribute this software is granted kpeter@1033: * provided that this copyright notice appears in all copies. For kpeter@1033: * precise terms see the accompanying LICENSE file. kpeter@1033: * kpeter@1033: * This software is provided "AS IS" with no warranty of any kind, kpeter@1033: * express or implied, and with no claim as to its suitability for any kpeter@1033: * purpose. kpeter@1033: * kpeter@1033: */ kpeter@1033: f4c3@1031: #ifndef LEMON_OPT2_TSP_H f4c3@1031: #define LEMON_OPT2_TSP_H f4c3@1031: kpeter@1033: /// \ingroup tsp kpeter@1033: /// \file kpeter@1034: /// \brief 2-opt algorithm for symmetric TSP. kpeter@1033: f4c3@1031: #include f4c3@1031: #include f4c3@1031: f4c3@1031: namespace lemon { kpeter@1033: kpeter@1034: /// \ingroup tsp kpeter@1034: /// kpeter@1033: /// \brief 2-opt algorithm for symmetric TSP. kpeter@1033: /// kpeter@1033: /// Opt2Tsp implements the 2-opt heuristic for solving kpeter@1033: /// symmetric \ref tsp "TSP". kpeter@1033: /// kpeter@1033: /// This algorithm starts with an initial tour and iteratively improves it. kpeter@1033: /// At each step, it removes two edges and the reconnects the created two kpeter@1033: /// paths in the other way if the resulting tour is shorter. kpeter@1033: /// The algorithm finishes when no such 2-opt move can be applied, and so kpeter@1033: /// the tour is 2-optimal. kpeter@1033: /// kpeter@1033: /// If no starting tour is given to the \ref run() function, then the kpeter@1033: /// algorithm uses the node sequence determined by the node IDs. kpeter@1033: /// Oherwise, it starts with the given tour. kpeter@1033: /// kpeter@1036: /// This is a rather slow but effective method. kpeter@1036: /// Its typical usage is the improvement of the result of a fast tour kpeter@1036: /// construction heuristic (e.g. the InsertionTsp algorithm). kpeter@1033: /// kpeter@1033: /// \tparam CM Type of the cost map. f4c3@1031: template kpeter@1033: class Opt2Tsp kpeter@1033: { kpeter@1033: public: kpeter@1033: kpeter@1033: /// Type of the cost map kpeter@1033: typedef CM CostMap; kpeter@1033: /// Type of the edge costs kpeter@1033: typedef typename CM::Value Cost; kpeter@1033: f4c3@1031: private: kpeter@1033: f4c3@1031: GRAPH_TYPEDEFS(FullGraph); f4c3@1031: kpeter@1033: const FullGraph &_gr; kpeter@1033: const CostMap &_cost; kpeter@1033: Cost _sum; kpeter@1033: std::vector _plist; kpeter@1033: std::vector _path; kpeter@1033: f4c3@1031: public: kpeter@1033: kpeter@1033: /// \brief Constructor kpeter@1033: /// kpeter@1033: /// Constructor. kpeter@1033: /// \param gr The \ref FullGraph "full graph" the algorithm runs on. kpeter@1033: /// \param cost The cost map. kpeter@1033: Opt2Tsp(const FullGraph &gr, const CostMap &cost) kpeter@1033: : _gr(gr), _cost(cost) {} kpeter@1033: kpeter@1033: /// \name Execution Control kpeter@1033: /// @{ kpeter@1033: kpeter@1033: /// \brief Runs the algorithm from scratch. kpeter@1033: /// kpeter@1033: /// This function runs the algorithm starting from the tour that is kpeter@1033: /// determined by the node ID sequence. kpeter@1033: /// kpeter@1033: /// \return The total cost of the found tour. kpeter@1033: Cost run() { kpeter@1033: _path.clear(); kpeter@1033: kpeter@1033: if (_gr.nodeNum() == 0) return _sum = 0; kpeter@1033: else if (_gr.nodeNum() == 1) { kpeter@1033: _path.push_back(_gr(0)); kpeter@1033: return _sum = 0; f4c3@1031: } kpeter@1033: else if (_gr.nodeNum() == 2) { kpeter@1033: _path.push_back(_gr(0)); kpeter@1033: _path.push_back(_gr(1)); kpeter@1033: return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))]; kpeter@1033: } f4c3@1031: kpeter@1033: _plist.resize(2*_gr.nodeNum()); kpeter@1033: for (int i = 1; i < _gr.nodeNum()-1; ++i) { kpeter@1033: _plist[2*i] = i-1; kpeter@1033: _plist[2*i+1] = i+1; f4c3@1031: } kpeter@1033: _plist[0] = _gr.nodeNum()-1; kpeter@1033: _plist[1] = 1; kpeter@1033: _plist[2*_gr.nodeNum()-2] = _gr.nodeNum()-2; kpeter@1033: _plist[2*_gr.nodeNum()-1] = 0; kpeter@1033: kpeter@1033: return start(); f4c3@1031: } f4c3@1031: kpeter@1034: /// \brief Runs the algorithm starting from the given tour. kpeter@1033: /// kpeter@1033: /// This function runs the algorithm starting from the given tour. kpeter@1033: /// kpeter@1033: /// \param tour The tour as a path structure. It must be a kpeter@1033: /// \ref checkPath() "valid path" containing excactly n arcs. kpeter@1033: /// kpeter@1033: /// \return The total cost of the found tour. kpeter@1033: template kpeter@1033: Cost run(const Path& tour) { kpeter@1033: _path.clear(); kpeter@1033: kpeter@1033: if (_gr.nodeNum() == 0) return _sum = 0; kpeter@1033: else if (_gr.nodeNum() == 1) { kpeter@1033: _path.push_back(_gr(0)); kpeter@1033: return _sum = 0; kpeter@1033: } kpeter@1033: else if (_gr.nodeNum() == 2) { kpeter@1033: _path.push_back(_gr(0)); kpeter@1033: _path.push_back(_gr(1)); kpeter@1033: return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))]; kpeter@1033: } kpeter@1033: kpeter@1033: _plist.resize(2*_gr.nodeNum()); kpeter@1033: typename Path::ArcIt it(tour); kpeter@1033: int first = _gr.id(_gr.source(it)), kpeter@1033: prev = first, kpeter@1033: curr = _gr.id(_gr.target(it)), kpeter@1033: next = -1; kpeter@1033: _plist[2*first+1] = curr; kpeter@1033: for (++it; it != INVALID; ++it) { kpeter@1033: next = _gr.id(_gr.target(it)); kpeter@1033: _plist[2*curr] = prev; kpeter@1033: _plist[2*curr+1] = next; kpeter@1033: prev = curr; kpeter@1033: curr = next; kpeter@1033: } kpeter@1033: _plist[2*first] = prev; kpeter@1033: kpeter@1033: return start(); kpeter@1033: } kpeter@1033: kpeter@1034: /// \brief Runs the algorithm starting from the given tour. kpeter@1033: /// kpeter@1034: /// This function runs the algorithm starting from the given tour kpeter@1034: /// (node sequence). kpeter@1033: /// kpeter@1034: /// \param tour A vector that stores all Nodes of the graph kpeter@1034: /// in the desired order. kpeter@1033: /// kpeter@1033: /// \return The total cost of the found tour. kpeter@1034: Cost run(const std::vector& tour) { kpeter@1033: _path.clear(); kpeter@1033: kpeter@1033: if (_gr.nodeNum() == 0) return _sum = 0; kpeter@1033: else if (_gr.nodeNum() == 1) { kpeter@1033: _path.push_back(_gr(0)); kpeter@1033: return _sum = 0; kpeter@1033: } kpeter@1033: else if (_gr.nodeNum() == 2) { kpeter@1033: _path.push_back(_gr(0)); kpeter@1033: _path.push_back(_gr(1)); kpeter@1033: return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))]; kpeter@1033: } kpeter@1033: kpeter@1033: _plist.resize(2*_gr.nodeNum()); kpeter@1034: typename std::vector::const_iterator it = tour.begin(); kpeter@1033: int first = _gr.id(*it), kpeter@1033: prev = first, kpeter@1033: curr = _gr.id(*(++it)), kpeter@1033: next = -1; kpeter@1033: _plist[2*first+1] = curr; kpeter@1033: for (++it; it != tour.end(); ++it) { kpeter@1033: next = _gr.id(*it); kpeter@1033: _plist[2*curr] = prev; kpeter@1033: _plist[2*curr+1] = next; kpeter@1033: prev = curr; kpeter@1033: curr = next; kpeter@1033: } kpeter@1033: _plist[2*first] = curr; kpeter@1033: _plist[2*curr] = prev; kpeter@1033: _plist[2*curr+1] = first; kpeter@1033: kpeter@1033: return start(); kpeter@1033: } kpeter@1033: kpeter@1033: /// @} kpeter@1033: kpeter@1033: /// \name Query Functions kpeter@1033: /// @{ kpeter@1033: kpeter@1033: /// \brief The total cost of the found tour. kpeter@1033: /// kpeter@1033: /// This function returns the total cost of the found tour. kpeter@1033: /// kpeter@1033: /// \pre run() must be called before using this function. kpeter@1033: Cost tourCost() const { kpeter@1033: return _sum; kpeter@1033: } kpeter@1033: kpeter@1033: /// \brief Returns a const reference to the node sequence of the kpeter@1033: /// found tour. kpeter@1033: /// kpeter@1034: /// This function returns a const reference to a vector kpeter@1033: /// that stores the node sequence of the found tour. kpeter@1033: /// kpeter@1033: /// \pre run() must be called before using this function. kpeter@1033: const std::vector& tourNodes() const { kpeter@1033: return _path; kpeter@1033: } kpeter@1033: kpeter@1033: /// \brief Gives back the node sequence of the found tour. kpeter@1033: /// kpeter@1033: /// This function copies the node sequence of the found tour into kpeter@1037: /// an STL container through the given output iterator. The kpeter@1037: /// value_type of the container must be FullGraph::Node. kpeter@1037: /// For example, kpeter@1037: /// \code kpeter@1037: /// std::vector nodes(countNodes(graph)); kpeter@1037: /// tsp.tourNodes(nodes.begin()); kpeter@1037: /// \endcode kpeter@1037: /// or kpeter@1037: /// \code kpeter@1037: /// std::list nodes; kpeter@1037: /// tsp.tourNodes(std::back_inserter(nodes)); kpeter@1037: /// \endcode kpeter@1033: /// kpeter@1033: /// \pre run() must be called before using this function. kpeter@1037: template kpeter@1037: void tourNodes(Iterator out) const { kpeter@1037: std::copy(_path.begin(), _path.end(), out); kpeter@1033: } kpeter@1033: kpeter@1033: /// \brief Gives back the found tour as a path. kpeter@1033: /// kpeter@1033: /// This function copies the found tour as a list of arcs/edges into kpeter@1033: /// the given \ref concept::Path "path structure". kpeter@1033: /// kpeter@1033: /// \pre run() must be called before using this function. kpeter@1033: template kpeter@1033: void tour(Path &path) const { kpeter@1033: path.clear(); kpeter@1033: for (int i = 0; i < int(_path.size()) - 1; ++i) { kpeter@1033: path.addBack(_gr.arc(_path[i], _path[i+1])); kpeter@1033: } kpeter@1033: if (int(_path.size()) >= 2) { kpeter@1033: path.addBack(_gr.arc(_path.back(), _path.front())); kpeter@1033: } kpeter@1033: } kpeter@1033: kpeter@1033: /// @} kpeter@1033: f4c3@1031: private: kpeter@1033: kpeter@1033: // Iterator class for the linked list storage of the tour kpeter@1033: class PathListIt { f4c3@1031: public: kpeter@1033: PathListIt(const std::vector &pl, int i=0) kpeter@1033: : plist(&pl), act(i), last(pl[2*act]) {} kpeter@1033: PathListIt(const std::vector &pl, int i, int l) kpeter@1033: : plist(&pl), act(i), last(l) {} f4c3@1031: kpeter@1033: int nextIndex() const { kpeter@1033: return (*plist)[2*act] == last ? 2*act+1 : 2*act; f4c3@1031: } kpeter@1033: kpeter@1033: int prevIndex() const { kpeter@1033: return (*plist)[2*act] == last ? 2*act : 2*act+1; f4c3@1031: } kpeter@1033: f4c3@1031: int next() const { kpeter@1033: int x = (*plist)[2*act]; kpeter@1033: return x == last ? (*plist)[2*act+1] : x; f4c3@1031: } f4c3@1031: f4c3@1031: int prev() const { kpeter@1033: return last; f4c3@1031: } kpeter@1033: kpeter@1033: PathListIt& operator++() { f4c3@1031: int tmp = act; f4c3@1031: act = next(); f4c3@1031: last = tmp; f4c3@1031: return *this; f4c3@1031: } kpeter@1033: f4c3@1031: operator int() const { f4c3@1031: return act; f4c3@1031: } kpeter@1033: f4c3@1031: private: kpeter@1033: const std::vector *plist; f4c3@1031: int act; f4c3@1031: int last; f4c3@1031: }; f4c3@1031: kpeter@1033: // Checks and applies 2-opt move (if it improves the tour) kpeter@1033: bool checkOpt2(const PathListIt& i, const PathListIt& j) { kpeter@1033: Node u = _gr.nodeFromId(i), kpeter@1033: un = _gr.nodeFromId(i.next()), kpeter@1033: v = _gr.nodeFromId(j), kpeter@1033: vn = _gr.nodeFromId(j.next()); f4c3@1031: kpeter@1033: if (_cost[_gr.edge(u, un)] + _cost[_gr.edge(v, vn)] > kpeter@1033: _cost[_gr.edge(u, v)] + _cost[_gr.edge(un, vn)]) kpeter@1033: { kpeter@1033: _plist[PathListIt(_plist, i.next(), i).prevIndex()] = j.next(); kpeter@1033: _plist[PathListIt(_plist, j.next(), j).prevIndex()] = i.next(); f4c3@1031: kpeter@1033: _plist[i.nextIndex()] = j; kpeter@1033: _plist[j.nextIndex()] = i; f4c3@1031: kpeter@1033: return true; f4c3@1031: } kpeter@1033: f4c3@1031: return false; kpeter@1033: } f4c3@1031: kpeter@1033: // Executes the algorithm from the initial tour kpeter@1033: Cost start() { f4c3@1031: kpeter@1033: restart_search: kpeter@1033: for (PathListIt i(_plist); true; ++i) { kpeter@1033: PathListIt j = i; kpeter@1033: if (++j == 0 || ++j == 0) break; kpeter@1033: for (; j != 0 && j != i.prev(); ++j) { kpeter@1033: if (checkOpt2(i, j)) kpeter@1033: goto restart_search; f4c3@1031: } f4c3@1031: } f4c3@1031: kpeter@1033: PathListIt i(_plist); kpeter@1033: _path.push_back(_gr.nodeFromId(i)); kpeter@1033: for (++i; i != 0; ++i) kpeter@1033: _path.push_back(_gr.nodeFromId(i)); f4c3@1031: kpeter@1033: _sum = _cost[_gr.edge(_path.back(), _path.front())]; kpeter@1033: for (int i = 0; i < int(_path.size())-1; ++i) { kpeter@1033: _sum += _cost[_gr.edge(_path[i], _path[i+1])]; kpeter@1033: } f4c3@1031: f4c3@1031: return _sum; f4c3@1031: } f4c3@1031: f4c3@1031: }; f4c3@1031: f4c3@1031: }; // namespace lemon f4c3@1031: f4c3@1031: #endif