An abstract permutation problem. More...
#include <model.hh>
Public Member Functions | |
| permutation_problem () | |
| Unimplemented. | |
| permutation_problem (int n) | |
| Inizialize pi_m = {0, 1, 2, ..., n-1}. | |
| 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. More... | |
| virtual gol_type | compute_cost () const =0 |
| : Compute cost of the whole solution. More... | |
| virtual gol_type | evaluate_swap (int i, int j) const =0 |
| : Evaluate a swap. More... | |
| size_t | size () const |
| The size of the problem. Do not override unless you know what you are doing. | |
| 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. | |
| void | update_cost () |
| Updates the cost with the one computed by the subclass. Do not override unless you know what you are doing. | |
| void | apply_swap (int i, int j) |
| : Apply a swap and update the cost. Do not override unless you know what you are doing. | |
 Public Member Functions inherited from mets::feasible_solution | |
| virtual | ~feasible_solution () |
| Virtual dtor. | |
Protected Attributes | |
| std::vector< int > | pi_m |
| gol_type | cost_m |
Friends | |
| template<typename random_generator > | |
| void | random_shuffle (permutation_problem &p, random_generator &rng) |
| Shuffle a permutation problem (generates a random starting point). More... | |
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
Member Function Documentation
|
pure virtual |
: Compute cost of the whole solution.
You will need to override this one.
|
inlinevirtual |
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.
|
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.
Friends And Related Function Documentation
|
friend |
Shuffle a permutation problem (generates a random starting point).
- See Also
- mets::permutation_problem
The documentation for this class was generated from the following file:
- metslib/model.hh