mets::permutation_problem Class Reference [Model]

An abstract permutation problem. More...

#include <model.hh>

Inheritance diagram for mets::permutation_problem:

Collaboration diagram for mets::permutation_problem:

List of all members.

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.
virtual gol_type	compute_cost () const =0
	: Compute cost of the whole solution.
virtual gol_type	evaluate_swap (int i, int j) const =0
	: Evaluate a swap.
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.
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).

---

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

)

[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