METSlib 0.6

- Main Page
- Modules
- Classes

- Class List
- Class Hierarchy
- Class Members

Public Member Functions | Protected Attributes | Friends | List of all members
mets::permutation_problem Class Referenceabstract
Model

An abstract permutation problem. More...

`#include <model.hh>`

Inheritance diagram for mets::permutation_problem:
Collaboration diagram for mets::permutation_problem:

## 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

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.

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.

## Friends And Related Function Documentation

template<typename random_generator >

void random_shuffle | ( | permutation_problem & | p,
|  | random_generator & | rng
| ) |  |
| 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

Return to METSlib home page