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 <lemon/bits/utility.h>
deba@2067: #include <lemon/error.h>
deba@2067: #include <lemon/time_measure.h>
deba@2067: #include <functional>
deba@2067: #include <deque>
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<VALUE>,
deba@2067:             typename BETTER = std::less<VALUE>,
deba@2067:             bool UNDIR = UndirectedTagIndicator<GRAPH>::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<TS> {};
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<typename> class CP1, template<typename> class CP2, 
deba@2067:             typename COMBINATION >
deba@2067: #else
deba@2067:   template< template<typename> class CP1, template<typename> 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<TS>  Policy1;
deba@2067:       typedef CP2<TS>  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<typename> class POLICY, typename TRAITS >
deba@2067: #else
deba@2067:   template< typename GRAPH, typename VALUE,
deba@2067:             template<typename> class POLICY = IterationPolicy,
deba@2067:             typename TRAITS = TabuSearchDefaultTraits<GRAPH, VALUE> >
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<GRAPH,VALUE,POLICY,TRAITS>  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<SelfType>  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