An abstract permutation problem. More...
#include <model.hh>
Public Member Functions | |
| void | apply_swap (int i, int j) |
| : Apply a swap and update the cost. Do not override unless you know what you are doing. | |
| virtual gol_type | compute_cost () const =0 |
| : Compute cost of the whole solution. | |
| void | copy_from (const copyable &other) |
| Copy from another permutation problem, if you introduce new member variables remember to override this and to call permutation_problem::copy_from in the overriding code. | |
| gol_type | cost_function () const |
| Returns the cost of the current solution. The default implementation provided returns the protected mets::permutation_problem::cost_m member variable. Do not override unless you know what you are doing. | |
| virtual gol_type | evaluate_swap (int i, int j) const =0 |
| : Evaluate a swap. | |
| permutation_problem () | |
| Unimplemented. | |
| permutation_problem (int n) | |
| Inizialize pi_m = {0, 1, 2, ..., n-1}. | |
| size_t | size () const |
| The size of the problem. Do not override unless you know what you are doing. | |
| void | update_cost () |
| Updates the cost with the one computed by the subclass. Do not override unless you know what you are doing. | |
Protected Attributes | |
| gol_type | cost_m |
| std::vector< int > | pi_m |
Friends | |
| template<typename random_generator > | |
| void | random_shuffle (permutation_problem &p, random_generator &rng) |
| Shuffle a permutation problem (generates a random starting point). | |
Detailed Description
An abstract permutation problem.
The permutation problem provides a skeleton to rapidly prototype permutation problems (such as Assignment problem, Quadratic AP, TSP, and so on). The skeleton holds a pi_m variable that, at each step, contains a permutation of the numbers in [0..n-1].
A few operators are provided to randomly choose a solution, to perturbate a solution with some random swaps and to simply swap two items in the list.
- See also:
- mets::swap_elements
Constructor & Destructor Documentation
Unimplemented.
| mets::permutation_problem::permutation_problem | ( | int | n | ) | [inline] |
Member Function Documentation
| void mets::permutation_problem::apply_swap | ( | int | i, |
| int | j | ||
| ) | [inline] |
| virtual gol_type mets::permutation_problem::compute_cost | ( | ) | const [pure virtual] |
: Compute cost of the whole solution.
You will need to override this one.
| void mets::permutation_problem::copy_from | ( | const copyable & | other | ) | [inline, virtual] |
Copy from another permutation problem, if you introduce new member variables remember to override this and to call permutation_problem::copy_from in the overriding code.
- Parameters:
-
other the problem to copy from
Implements mets::copyable.
| gol_type mets::permutation_problem::cost_function | ( | ) | const [inline, virtual] |
Returns the cost of the current solution. The default implementation provided returns the protected mets::permutation_problem::cost_m member variable. Do not override unless you know what you are doing.
Implements mets::evaluable_solution.
| virtual gol_type mets::permutation_problem::evaluate_swap | ( | int | i, |
| int | j | ||
| ) | const [pure virtual] |
: Evaluate a swap.
Implement this method to evaluate the change in the cost function after the swap (without actually modifying the solution). The method should return the difference in cost between the current position and the position after the swap (negative if decreasing and positive otherwise).
To obtain maximal performance from the algorithm it is essential, whenever possible, to only compute the cost update and not the whole cost function.
| size_t mets::permutation_problem::size | ( | ) | const [inline] |
| void mets::permutation_problem::update_cost | ( | ) | [inline] |
Friends And Related Function Documentation
| void random_shuffle | ( | permutation_problem & | p, |
| random_generator & | rng | ||
| ) | [friend] |
Shuffle a permutation problem (generates a random starting point).
- See also:
- mets::permutation_problem
Member Data Documentation
gol_type mets::permutation_problem::cost_m [protected] |
std::vector<int> mets::permutation_problem::pi_m [protected] |
The documentation for this class was generated from the following file: