deba@2067: /* -*- C++ -*- deba@2067: * deba@2067: * This file is a part of LEMON, a generic C++ optimization library deba@2067: * deba@2067: * Copyright (C) 2003-2006 deba@2067: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport deba@2067: * (Egervary Research Group on Combinatorial Optimization, EGRES). deba@2067: * deba@2067: * Permission to use, modify and distribute this software is granted deba@2067: * provided that this copyright notice appears in all copies. For deba@2067: * precise terms see the accompanying LICENSE file. deba@2067: * deba@2067: * This software is provided "AS IS" with no warranty of any kind, deba@2067: * express or implied, and with no claim as to its suitability for any deba@2067: * purpose. deba@2067: * deba@2067: */ deba@2067: deba@2067: deba@2067: #ifndef LEMON_TABU_SEARCH_H deba@2067: #define LEMON_TABU_SEARCH_H deba@2067: deba@2067: /// \ingroup experimental deba@2067: /// \file deba@2067: /// \brief TabuSearch algorithm. deba@2067: /// deba@2067: /// \author Szabadkai Mark deba@2067: deba@2067: #include deba@2067: #include deba@2067: #include deba@2067: #include deba@2067: #include deba@2067: deba@2067: deba@2067: namespace lemon { deba@2067: deba@2067: /// \brief Default Traits for TabuSearch class. deba@2067: /// deba@2067: /// This template defines the needed types for the \ref TabuSearch class. deba@2067: /// Is main purpos is to simplify the main class's template interface, deba@2067: /// but it provides the EdgeIt type, passing to the concrete graph wheter deba@2067: /// it is directed or undirected. deba@2067: #ifdef DOXYGEN deba@2067: template< typename GRAPH, typename VALUE, deba@2067: typename HEIGHTMAP, typename BETTER, bool UNDIR > deba@2067: #else deba@2067: template< typename GRAPH, typename VALUE, deba@2067: typename HEIGHTMAP = typename GRAPH::template NodeMap, deba@2067: typename BETTER = std::less, deba@2067: bool UNDIR = UndirectedTagIndicator::value > deba@2067: #endif deba@2067: struct TabuSearchDefaultTraits { deba@2067: typedef VALUE Value; deba@2067: typedef BETTER Better; deba@2067: deba@2067: typedef GRAPH Graph; deba@2067: typedef typename GRAPH::Node Node; deba@2067: typedef HEIGHTMAP HeightMap; deba@2067: deba@2067: typedef typename GRAPH::IncEdgeIt EdgeIt; deba@2067: }; deba@2067: deba@2067: template< typename GRAPH, typename VALUE, deba@2067: typename HEIGHTMAP, typename BETTER > deba@2067: struct TabuSearchDefaultTraits< GRAPH, VALUE, HEIGHTMAP, BETTER, false > { deba@2067: typedef VALUE Value; deba@2067: typedef BETTER Better; deba@2067: deba@2067: typedef GRAPH Graph; deba@2067: typedef typename GRAPH::Node Node; deba@2067: typedef HEIGHTMAP HeightMap; deba@2067: deba@2067: typedef typename GRAPH::OutEdgeIt EdgeIt; deba@2067: }; deba@2067: deba@2067: deba@2067: deba@2067: /// \brief Policy hierarchy to controll the search algorithm. deba@2067: /// deba@2067: /// The fallowing template hierarchy offers a clean interface to define own deba@2067: /// policies, and combine existing ones. deba@2067: template< typename TS > deba@2067: struct TabuSearchPolicyConcept { deba@2067: void target( TS *ts ) {} deba@2067: deba@2067: void reset() {} deba@2067: bool onStep() { return false; } deba@2067: bool onStick() { return false; } deba@2067: bool onImprove( const typename TS::Value &best ) { return false; } deba@2067: }; deba@2067: deba@2067: template< typename TS > deba@2067: struct YesPolicy { deba@2067: void target( TS *ts ) {} deba@2067: deba@2067: void reset() {} deba@2067: bool onStep() { return true; } deba@2067: bool onStick() { return true; } deba@2067: bool onImprove( const typename TS::Value &best ) { return true; } deba@2067: }; deba@2067: deba@2067: template< typename TS > deba@2067: struct NoPolicy : public TabuSearchPolicyConcept {}; deba@2067: deba@2067: /// \brief Some basic methode, how tow Policies can be combined deba@2067: struct PolicyAndCombination { deba@2067: static bool evaluate( const bool r1, const bool r2 ) { deba@2067: return r1 && r2; deba@2067: } deba@2067: }; deba@2067: deba@2067: struct PolicyOrCombination { deba@2067: static bool evaluate( const bool r1, const bool r2 ) { deba@2067: return r1 || r2; deba@2067: } deba@2067: }; deba@2067: deba@2067: /// \brief CombinePolicies deba@2067: /// deba@2067: /// It combines tow policies using the given combination methode (mainly deba@2067: /// some of the basic logical methodes) to create a new one. deba@2067: #ifdef DOXYGEN deba@2067: template< template class CP1, template class CP2, deba@2067: typename COMBINATION > deba@2067: #else deba@2067: template< template class CP1, template class CP2, deba@2067: typename COMBINATION = PolicyAndCombination > deba@2067: #endif deba@2067: struct CombinePolicies { deba@2067: template< typename TS > deba@2067: struct Policy { deba@2067: typedef CP1 Policy1; deba@2067: typedef CP2 Policy2; deba@2067: deba@2067: Policy1 policy1; deba@2067: Policy2 policy2; deba@2067: deba@2067: inline Policy() : policy1(), policy2() {} deba@2067: inline Policy( const Policy1 &cp1, const Policy2 &cp2 ) deba@2067: : policy1(cp1), policy2(cp2) {} deba@2067: deba@2067: void target( TS *ts ) { deba@2067: policy1.target(ts), policy2.target(ts); deba@2067: }; deba@2067: deba@2067: void reset() { deba@2067: policy1.reset(), policy2.reset(); deba@2067: } deba@2067: deba@2067: bool onStep() { deba@2067: return cmb.evaluate( policy1.onStep(), policy2.onStep() ); deba@2067: } deba@2067: deba@2067: bool onStick() { deba@2067: return cmb.evaluate( policy1.onStick(), policy2.onStick() ); deba@2067: } deba@2067: deba@2067: bool onImprove( const typename TS::Value &best ) { deba@2067: return cmb.evaluate( policy1.onImprove(best), deba@2067: policy2.onImprove(best) ); deba@2067: } deba@2067: deba@2067: private: deba@2067: COMBINATION cmb; deba@2067: }; deba@2067: }; deba@2067: deba@2067: deba@2067: /// \brief IterationPolicy limits the number of iterations and the deba@2067: /// number of iterations without improvement deba@2067: template< typename TS > deba@2067: struct IterationPolicy { deba@2067: IterationPolicy() : _it_lim(100000), _noimpr_it_lim(5000) {} deba@2067: IterationPolicy( const long int itl, const long int noimpritl ) deba@2067: : _it_lim(itl), _noimpr_it_lim(noimpritl) deba@2067: {} deba@2067: deba@2067: void target( TS *ts ) {} deba@2067: deba@2067: void reset() { deba@2067: _it = _noimpr_it = 0; deba@2067: } deba@2067: deba@2067: bool onStep() { deba@2067: ++_it; ++_noimpr_it; deba@2067: return (_it <= _it_lim) && (_noimpr_it <= _noimpr_it_lim); deba@2067: } deba@2067: deba@2067: bool onStick() { deba@2067: return false; deba@2067: } deba@2067: deba@2067: bool onImprove( const typename TS::Value &best ) { deba@2067: _noimpr_it = 0; deba@2067: return true; deba@2067: } deba@2067: deba@2067: long int iterationLimit() const { deba@2067: return _it_lim; deba@2067: } deba@2067: deba@2067: void iterationLimit( const long int itl ) { deba@2067: _it_lim = itl; deba@2067: } deba@2067: deba@2067: long int noImprovementIterationLimit() const { deba@2067: return _noimpr_it_lim; deba@2067: } deba@2067: deba@2067: void noImprovementIterationLimit( const long int noimpritl ) { deba@2067: _noimpr_it_lim = noimpritl; deba@2067: } deba@2067: deba@2067: private: deba@2067: long int _it_lim, _noimpr_it_lim; deba@2067: long int _it, _noimpr_it; deba@2067: }; deba@2067: deba@2067: /// \brief HeightPolicy stops the search when a given height is reached or deba@2067: /// exceeds deba@2067: template< typename TS > deba@2067: struct HeightPolicy { deba@2067: typedef typename TS::Value Value; deba@2067: deba@2067: HeightPolicy() : _height_lim(), _found(false) {} deba@2067: HeightPolicy( const Value &hl ) : _height_lim(hl), _found(false) {} deba@2067: deba@2067: void target( TS *ts ) {} deba@2067: deba@2067: void reset() { deba@2067: _found = false; deba@2067: } deba@2067: deba@2067: bool onStep() { deba@2067: return !_found; deba@2067: } deba@2067: deba@2067: bool onStick() { deba@2067: return false; deba@2067: } deba@2067: deba@2067: bool onImprove( const Value &best ) { deba@2067: typename TS::Better better; deba@2067: _found = better(best, _height_lim) || (best == _height_lim); deba@2067: return !_found; deba@2067: } deba@2067: deba@2067: Value heightLimi() const { deba@2067: return _height_lim; deba@2067: } deba@2067: deba@2067: void heightLimi( const Value &hl ) { deba@2067: _height_lim = hl; deba@2067: } deba@2067: deba@2067: private: deba@2067: Value _height_lim; deba@2067: bool _found; deba@2067: }; deba@2067: deba@2067: /// \brief TimePolicy limits the time for searching. deba@2067: template< typename TS > deba@2067: struct TimePolicy { deba@2067: TimePolicy() : _time_lim(60.0), _timeisup(false) {} deba@2067: TimePolicy( const double tl ) : _time_lim(tl), _timeisup(false) {} deba@2067: deba@2067: void target( TS *ts ) {} deba@2067: deba@2067: void reset() { deba@2067: _timeisup = false; deba@2067: _t.reset(); deba@2067: } deba@2067: deba@2067: bool onStep() { deba@2067: update(); deba@2067: return !_timeisup; deba@2067: } deba@2067: deba@2067: bool onStick() { deba@2067: return false; deba@2067: } deba@2067: deba@2067: bool onImprove( const typename TS::Value &best ) { deba@2067: update(); deba@2067: return !_timeisup; deba@2067: } deba@2067: deba@2067: double timeLimit() const { deba@2067: return _time_lim; deba@2067: } deba@2067: deba@2067: void setTimeLimit( const double tl ) { deba@2067: _time_lim = tl; deba@2067: update(); deba@2067: } deba@2067: deba@2067: private: deba@2067: lemon::Timer _t; deba@2067: double _time_lim; deba@2067: bool _timeisup; deba@2067: deba@2067: inline void update() { deba@2067: _timeisup = _t.realTime() > _time_lim; deba@2067: } deba@2067: }; deba@2067: deba@2067: deba@2067: deba@2067: /// \brief TabuSearch main class deba@2067: /// deba@2067: /// This class offers the implementation of tabu-search algorithm. The deba@2067: /// tabu-serach is a local-search. It starts from a specified point of the deba@2067: /// problem's graph representation, and in every step it goes to the localy deba@2067: /// best next Node except those in tabu set. The maximum size of this tabu deba@2067: /// set defines how many Node will be remembered. The best Node ever found deba@2067: /// will also stored, so we wont lose it, even is the search continues. deba@2067: /// The class can be used on any kind of Graph and with any kind of Value deba@2067: /// with a total-settlement on it. deba@2067: /// deba@2067: /// \param _Graph The graph type the algorithm runs on. deba@2067: /// \param _Value The values' type associated to the nodes. deba@2067: /// \param _Policy Controlls the search. Determinates when to stop, or how deba@2067: /// manage stuck search. Default value is \ref IterationPolicy . deba@2067: /// \param _Traits Collection of needed types. Default value is deba@2067: /// \ref TabuSearchDefaultTraits . deba@2067: /// deba@2067: /// \author Szabadkai Mark deba@2067: #ifdef DOXYGEN deba@2067: template< typename GRAPH, typename VALUE, template class POLICY, typename TRAITS > deba@2067: #else deba@2067: template< typename GRAPH, typename VALUE, deba@2067: template class POLICY = IterationPolicy, deba@2067: typename TRAITS = TabuSearchDefaultTraits > deba@2067: #endif deba@2067: class TabuSearch deba@2067: { deba@2067: public: deba@2067: deba@2067: /// \brief Thrown by setting the size of the tabu-set and the given size deba@2067: /// is less than 2. deba@2067: class BadParameterError : public lemon::LogicError { deba@2067: public: alpar@2151: virtual const char* what() const throw() { deba@2067: return "lemon::TabuSearch::BadParameterError"; deba@2067: } deba@2067: }; deba@2067: deba@2067: ///Public types deba@2067: typedef TabuSearch SelfType; deba@2067: deba@2067: typedef typename TRAITS::Graph Graph; deba@2067: typedef typename TRAITS::Node Node; deba@2067: typedef typename TRAITS::Value Value; deba@2067: typedef typename TRAITS::HeightMap HeightMap; deba@2067: typedef typename TRAITS::Better Better; deba@2067: typedef typename std::deque< Node >::const_iterator TabuIterator; deba@2067: deba@2067: typedef POLICY Policy; deba@2067: deba@2067: protected: deba@2067: typedef typename TRAITS::EdgeIt EdgeIt; deba@2067: deba@2067: const Graph &gr; deba@2067: const HeightMap &height; deba@2067: /// The tabu set. Teh current node is the first deba@2067: std::deque< Node > tabu; deba@2067: /// Maximal tabu size deba@2067: unsigned int mts; deba@2067: /// The best Node found deba@2067: Node b; deba@2067: deba@2067: Better better; deba@2067: Policy pol; deba@2067: deba@2067: public: deba@2067: /// \brief Constructor deba@2067: /// deba@2067: /// \param graph the graph the algorithm will run on. deba@2067: /// \param hm the height map used by the algorithm. deba@2067: /// \param tabusz the maximal size of the tabu set. Default value is 3 deba@2067: /// \param p the Policy controlling the search. deba@2067: TabuSearch( const Graph &graph, const HeightMap &hm, deba@2067: const int tabusz = 3, Policy p = Policy() ) deba@2067: : gr(graph), height(hm), mts(tabusz), pol(p) deba@2067: { deba@2067: pol.target(this); deba@2067: } deba@2067: deba@2067: /// \brief Destructor deba@2067: ~TabuSearch() { deba@2067: pol.target(NULL); deba@2067: } deba@2067: deba@2067: /// Set/Get the size of the tabu set deba@2067: void tabuSize( const unsigned int size ) deba@2067: { deba@2067: if( size < 2 ) deba@2067: throw BadParameterError( "Tabu size must be at least 2!" ); deba@2067: mts = size; deba@2067: while( mts < tabu.size() ) deba@2067: tabu.pop_back(); deba@2067: } deba@2067: deba@2067: unsigned int tabuSize() const { deba@2067: return mts; deba@2067: } deba@2067: deba@2067: /// Set/Get Policy deba@2067: void policy( Policy p ) { deba@2067: pol.target(NULL); deba@2067: pol = p; deba@2067: pol.target(this); deba@2067: } deba@2067: deba@2067: Policy& policy() { deba@2067: return pol; deba@2067: } deba@2067: deba@2067: /// \name Execution control deba@2067: /// The simplest way to execute the algorithm is to use the member deba@2067: /// functions called \c run( 'startnode' ). deba@2067: ///@{ deba@2067: deba@2067: /// \brief Initializes the internal data. deba@2067: /// deba@2067: /// \param startn The start node where the search begins. deba@2067: void init( const Node startn ) { deba@2067: tabu.clear(); deba@2067: tabu.push_front( startn ); deba@2067: b = startn; deba@2067: pol.reset(); deba@2067: } deba@2067: deba@2067: /// \brief Does one iteration deba@2067: /// deba@2067: /// If the Policy allows it searches for the best next node, then steps deba@2067: /// onto it. deba@2067: /// \return %False if one Policy condition wants to stop the search. deba@2067: bool step() deba@2067: { deba@2067: ///Request premmision from ControllPolicy deba@2067: if( !pol.onStep() ) deba@2067: return false; deba@2067: deba@2067: ///Find the best next potential node deba@2067: Node n; bool found = false; deba@2067: for( EdgeIt e(gr,tabu[0]); e != INVALID; ++e ) deba@2067: { deba@2067: Node m = (gr.source(e) == tabu[0]) ? gr.target(e) : gr.source(e); deba@2067: bool wrong = false; deba@2067: for( int i = 1; i != (signed int)tabu.size(); ++i ) deba@2067: if( m == tabu[i] ) { deba@2067: wrong = true; deba@2067: break; deba@2067: } deba@2067: if( wrong ) deba@2067: continue; deba@2067: deba@2067: if( !found ) { deba@2067: n = m; deba@2067: found = true; deba@2067: } else deba@2067: if( better(height[m], height[n]) ) { deba@2067: n = m; deba@2067: } deba@2067: } deba@2067: deba@2067: ///Handle stuck search deba@2067: if( !found ) { deba@2067: return pol.onStick(); deba@2067: } deba@2067: deba@2067: ///Move on... deba@2067: tabu.push_front(n); deba@2067: while( mts < tabu.size() ) { deba@2067: tabu.pop_back(); deba@2067: } deba@2067: if( better(height[n], height[b]) ) { deba@2067: b = n; deba@2067: if( !pol.onImprove(height[b]) ) deba@2067: return false; deba@2067: } deba@2067: deba@2067: return true; deba@2067: } deba@2067: deba@2067: /// \brief Runs a search while the Policy stops it. deba@2067: /// deba@2067: /// \param startn The start node where the search begins. deba@2067: inline void run( const Node startn ) { deba@2067: std::cin.unsetf( std::ios_base::skipws ); deba@2067: char c; deba@2067: init( startn ); deba@2067: while( step() ) deba@2067: std::cin >> c; deba@2067: std::cin.setf( std::ios_base::skipws ); deba@2067: } deba@2067: deba@2067: ///@} deba@2067: deba@2067: /// \name Query Functions deba@2067: /// The result of the TabuSearch algorithm can be obtained using these deba@2067: /// functions.\n deba@2067: ///@{ deba@2067: deba@2067: /// \brief The node, the search is standing on. deba@2067: inline Node current() const { deba@2067: return tabu[0]; deba@2067: } deba@2067: deba@2067: /// \brief The best node found until now. deba@2067: inline Node best() const { deba@2067: return b; deba@2067: } deba@2067: deba@2067: /// \brief Beginning to iterate on the current tabu set. deba@2067: inline TabuIterator tabu_begin() const { deba@2067: return tabu.begin(); deba@2067: } deba@2067: deba@2067: /// \brief Ending to iterate on the current tabu set. deba@2067: inline TabuIterator tabu_end() const { deba@2067: return tabu.end(); deba@2067: } deba@2067: deba@2067: ///@} deba@2067: }; deba@2067: } deba@2067: #endif