easylocaltemplates.cpp

来自「一个tabu search算法框架」· C++ 代码 · 共 2,039 行 · 第 1/5 页

  { 
    p_in = in;
    internal_state.SetInput(in); 
  }

  /** 
      Returns the cost of the internal state.
      
      @return the cost of the internal state
  */
  template <class Input, class Output, class State>
  fvalue LocalSearchSolver<Input,Output,State>::InternalStateCost() 
  { return internal_state_cost; }

  /**
     Constructs a local search solver by providing it a state manager,
     an output manager, an input object, and an output object.

     @param sm a pointer to a compatible state manager
     @param om a pointer to a compatible output manager
     @param in a pointer to an input object
     @param out a pointer to an output object
  */
  template <class Input, class Output, class State>
  LocalSearchSolver<Input,Output,State>::LocalSearchSolver(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in, Output* out) 
    : Solver<Input, Output>(in,out), p_sm(sm),  p_om(om), 
    number_of_init_trials(1)
  {
    if (in != NULL)
      internal_state.SetInput(in); 
  }

  /**
     The output is delivered by converting the final internal state
     to an output object by means of the output manager.
  */
  template <class Input, class Output, class State>
  void LocalSearchSolver<Input,Output,State>::DeliverOutput() 
  { p_om->OutputState(internal_state,*p_out); }

  /**
     The initial state is generated by delegating this task to 
     the state manager. The function invokes the SampleState function.
  */
  template <class Input, class Output, class State>
  void LocalSearchSolver<Input,Output,State>::FindInitialState() 
  { internal_state_cost = p_sm->SampleState(internal_state,number_of_init_trials); }

  /**
     The cost of the internal state is computed by the state manager.
  */
  template <class Input, class Output, class State>
  void LocalSearchSolver<Input,Output,State>::ComputeCost() 
  { internal_state_cost = p_sm->CostFunction(internal_state); }


  /**
     Checks wether the object state is consistent with all the related
     objects.
  */
  template <class Input, class Output, class State>
  void LocalSearchSolver<Input,Output,State>::Check()
  {
    assert(p_in != NULL);
    assert(p_in == p_sm->GetInput());
    assert(p_in == p_om->GetInput());
  }

  /**
     Sets the runner employed for solving the problem to the one passed as
     parameter.

     @param r the new runner to be used
  */
  template <class Input, class Output, class State>
  void SimpleLocalSearch<Input,Output,State>::SetRunner(Runner<Input,State> *r) 
  { p_runner = r; }


  /**
     Constructs a simple local search solver by providing it links to
     a state manager, an output manager, a runner, an input,
     and an output object.

     @param sm a pointer to a compatible state manager
     @param om a pointer to a compatible output manager
     @param r a pointer to a compatible runner
     @param in a pointer to an input object
     @param out a pointer to an output object
  */
  template <class Input, class Output, class State>
  SimpleLocalSearch<Input,Output,State>::SimpleLocalSearch(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Runner<Input,State>* r, Input* in, Output* out)
    : LocalSearchSolver<Input,Output,State>(sm,om,in,out) 
  { p_runner = r; }


  /**
     Constructs a simple local search solver by providing it links to
     a state manager, an output manager, an input, and an output object.

     @param sm a pointer to a compatible state manager
     @param om a pointer to a compatible output manager
     @param in a pointer to an input object
     @param out a pointer to an output object
  */
  template <class Input, class Output, class State>
  SimpleLocalSearch<Input,Output,State>::SimpleLocalSearch(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in, Output* out)
    : LocalSearchSolver<Input,Output,State>(sm,om,in,out) 
  { p_runner = NULL; }


  /** 
      Returns the number of iterations performed by the attached runner.
      
      @return the number of iterations elapsed.
  */
  template <class Input, class Output, class State>
  unsigned long SimpleLocalSearch<Input,Output,State>::NumberOfIterations() const 
  { return p_runner->NumberOfIterations(); }

  /**
     Lets the runner Go, and then collects the best state found.
  */
  template <class Input, class Output, class State>
  void SimpleLocalSearch<Input,Output,State>::Run()
  {
    p_runner->SetCurrentState(internal_state);
    p_runner->Go();
    internal_state = p_runner->GetBestState();
    internal_state_cost = p_runner->BestStateCost();
  }

  /**
     Performs a full solving procedure by finding an initial state, 
     running the attached runner and delivering the output.
  */
  template <class Input, class Output, class State>
  void LocalSearchSolver<Input,Output,State>::Solve()
  {
    FindInitialState();
    Run();
    DeliverOutput();
  }
  
  /**
     Start again a solving procedure, running the attached runner from
     the current internal state.
  */
  template <class Input, class Output, class State>
  void LocalSearchSolver<Input,Output,State>::ReSolve()
  {
    Run();
    DeliverOutput();
  }

  /**
     Tries multiple runs on different initial states and records the
     best one.
     
     @param n the number of trials
   */
  template <class Input, class Output, class State>
  void LocalSearchSolver<Input,Output,State>::MultiStartSolve(unsigned int n)
  { 
    State best_state;
    fvalue best_state_cost = 0; // we assign it a value only to prevent
                                // warnings from "smart" compilers
    for (unsigned int i = 0; i < n; i++)
      { 
	FindInitialState();
	Run();
	if (i == 0 || internal_state_cost < best_state_cost)
	  { 
	    best_state = internal_state;
	    best_state_cost = internal_state_cost;
	  }
      }
    internal_state = best_state;
    internal_state_cost = best_state_cost;
    DeliverOutput();
  }

  /**
     In the case of multi-runner solvers, the number of iterations is the
     overall number of iterations performed by any runner.
  */
  template <class Input, class Output, class State>
  unsigned long MultiRunnerSolver<Input,Output,State>::NumberOfIterations() const 
  { return total_iterations; }


  /**
     Constructs a multi runner solver by providing it links to
     a state manager, an output manager, an input, and an output object.

     @param sm a pointer to a compatible state manager
     @param om a pointer to a compatible output manager
     @param in a pointer to an input object
     @param out a pointer to an output object
  */
  template <class Input, class Output, class State>
  MultiRunnerSolver<Input,Output,State>::MultiRunnerSolver(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in, Output* out)
    : LocalSearchSolver<Input,Output,State>(sm,om,in,out), 
    total_iterations(0)
  { runners.clear(); }

  /**
     Sets the i-th runner managed by the solver to the passed parameter.

     @param r a pointer to a compatible runner
     @param i the runner position to set with r
  */
  template <class Input, class Output, class State>
  void MultiRunnerSolver<Input,Output,State>::SetRunner(Runner<Input,State> *r, unsigned int i) 
  { 
    assert(i < runners.size());
    runners[i] = r; 
  }

  /**
     Adds the given runner to the list of the managed runners.

     @param r a pointer to a compatible runner to add
   */
  template <class Input, class Output, class State>
  void MultiRunnerSolver<Input,Output,State>::AddRunner(Runner<Input,State> *r)
  { runners.push_back(r); }

  /**
     Clears the vector of runners managed by the solver.
  */
  template <class Input, class Output, class State>
  void MultiRunnerSolver<Input,Output,State>::ClearRunners()
  { runners.clear(); }

  /**
     Lets all the managed runners Go, and then it collects the best state
     found.
   */
  template <class Input, class Output, class State>
  void ComparativeSolver<Input,Output,State>::Run()
  { 
    int i;
    start_state = internal_state;
    runners[0]->SetCurrentState(start_state);
    runners[0]->Go();
    runners[0]->ComputeCost();
    internal_state = runners[0]->GetBestState();
    internal_state_cost = runners[0]->BestStateCost();
	
    for (i = 1; i < runners.size(); i++)
      {
	runners[i]->SetCurrentState(start_state);
	runners[i]->Go();
	runners[i]->ComputeCost();
	total_iterations += runners[i]->NumberOfIterations();
	if (runners[i]->BestStateCost() < internal_state_cost)
	  {
	    internal_state = runners[i]->GetBestState();
	    internal_state_cost = runners[i]->BestStateCost();
	  }
      }
  }

  /**
     Sets the number of rounds to the given value.
     
     @param r the number of rounds.
  */
  template <class Input, class Output, class State>
  void TokenRingSolver<Input,Output,State>::SetRounds(unsigned int r) 
  { max_idle_rounds = r; }

  /**
     Starts the token-ring from the i-th runner.
     
     @param i the runner which to start form
  */
  template <class Input, class Output, class State>
  void TokenRingSolver<Input,Output,State>::SetStartRunner(unsigned int i)
  { start_runner = i; }


  /**
     Constructs a token-ring runner solver by providing it links to
     a state manager, an output manager, an input, and an output object.

     @param sm a pointer to a compatible state manager
     @param om a pointer to a compatible output manager
     @param in a pointer to an input object
     @param out a pointer to an output object
  */
  template <class Input, class Output, class State>
  TokenRingSolver<Input,Output,State>::TokenRingSolver(StateManager<Input,State>* sm, OutputManager<Input,Output,State>* om, Input* in, Output* out) 
    : MultiRunnerSolver<Input,Output,State>(sm,om,in,out), 
    max_idle_rounds(1) 
  {}

  /**
     Checks wether the object state is consistent with all the related
     objects.
  */
  template <class Input, class Output, class State>
  void TokenRingSolver<Input,Output,State>::Check()
  {
    LocalSearchSolver<Input,Output,State>::Check();
    for (unsigned int i = 0; i < runners.size(); i++)
      {
	runners[i]->Check();
	assert(runners[i]->GetInput() == p_in);
      }
  }

  /**
     Outputs the solver state on a given output stream.

     @param os the output stream
  */
  template <class Input, class Output, class State>
  void TokenRingSolver<Input,Output,State>::Print(std::ostream& os) const
  {
    os << "Solver State" << std::endl;
    for (unsigned int i = 0; i < runners.size(); i++)
      {
	os << "Runner " << i << std::endl;
	runners[i]->Print(os);
      }
  }

  /**
     Runs all the managed runners one after another till no improvement
     has produced in a given number of rounds
  */
  template <class Input, class Output, class State>
  void TokenRingSolver<Input,Output,State>::Run()
  {
    assert(start_runner < runners.size());
  	
    // i is the current runner, j is the previous one;
    unsigned int i = start_runner, j = (start_runner >= 1) ?
      (start_runner - 1) : runners.size() - 1;
    int idle_rounds = 0;
    bool interrupt_search = false;
    bool improvement_found = false;
	
    ComputeCost(); // Set internal_state_cost
    // internal_state_cost is used to check
    // whether a full round has produces improvements or not
    runners[i]->SetCurrentState(internal_state);
	
    while (idle_rounds < max_idle_rounds && !interrupt_search)
      { 
        do
	  {
	    runners[i]->Go();
	    if (runners[i]->BestStateCost() < internal_state_cost) 
	      { 
	        internal_state = runners[i]->GetBestState(); 
	        internal_state_cost = runners[i]->BestStateCost(); 
	        improvement_found = true;
	      } 
	    total_iterations += runners[i]->NumberOfIterations();
	    if (runners[i]->LowerBoundReached() || runners.size() == 1)
	      {
	        interrupt_search = true;
	        break;
	      }
	    j = i;
	    i = (i + 1) % runners.size();
	    runners[i]->SetCurrentState(runners[j]->GetBestState());
  	  }
        while (i != start_runner);
		
        if (!interrupt_search)
	  {
	    if (improvement_found)
	      idle_rounds = 0;
	    else
  	      idle_rounds++;
  	    improvement_found = false;
  	  }
      }
  }

  // Abstract Move Tester

  /**
     Constructs an abstract move tester and assign it a name passed 
     as parameter.
     @param s the name of the tester
  */
  template <class Input, class Output, class State>
  AbstractMoveTester<Input,Output,State>::AbstractMoveTester(std::string s) 
  { name = s; }

  /**
     Gets the name of the tester.
     @returns the name of the tester
  */
  template <class Input, class Output, class State>
  std::string AbstractMoveTester<Input,Output,State>::Name() 
  { return name; }

  // Move Tester

  /**
     Constructs a move t