firstimprovement.hh

Go to the documentation of this file.

#if !defined(_FIRST_DESCENT_HH_)
#define _FIRST_DESCENT_HH_

#include "easylocal/searchengines/localsearch.hh"
#include "easylocal/helpers/statemanager.hh"
#include "easylocal/helpers/neighborhoodexplorer.hh"

namespace EasyLocal {
  
  namespace Core {
    
    template <class Input, class State, class Move, typename CFtype = int>
    class FirstImprovement : public LocalSearch<Input, State, Move, CFtype>
    {
    public:
      FirstImprovement(const Input& in,
                   StateManager<Input, State, CFtype>& e_sm,
                   NeighborhoodExplorer<Input, State, Move, CFtype>& e_ne,
                   std::string name);
    protected:
      bool StopCriterion();
      void SelectMove();
    };
    
    /*************************************************************************
     * Implementation
     *************************************************************************/
    
    template <class Input, class State, class Move, typename CFtype>
    FirstImprovement<Input, State, Move, CFtype>::FirstImprovement(const Input& in,
                                                           StateManager<Input, State, CFtype>& e_sm, NeighborhoodExplorer<Input, State, Move, CFtype>& e_ne,
                                                           std::string name)
    : LocalSearch<Input, State, Move, CFtype>(in, e_sm, e_ne, name, "First Improvement Engine")
    {}
    
    template <class Input, class State, class Move, typename CFtype>
    void FirstImprovement<Input, State, Move, CFtype>::SelectMove()
    {
      size_t explored;
      EvaluatedMove<Move, CFtype> em = this->ne.SelectFirst(*this->p_current_state, explored, [](const Move& mv, CostStructure<CFtype> move_cost) {
        return move_cost < 0;
      }, this->weights);
      this->current_move = em;
      this->evaluations += explored;
    }
    
    template <class Input, class State, class Move, typename CFtype>
    bool FirstImprovement<Input, State, Move, CFtype>::StopCriterion()
    {
      return this->iteration > 0 && !this->current_move.is_valid;
    }        
  }
}

#endif // _FIRST_DESCENT_HH_