TabuSearch< GRAPH, VALUE, POLICY, TRAITS > Class Template Reference
[Metaheuristics]

---

Detailed Description

template<typename GRAPH, typename VALUE, template< typename > class POLICY, typename TRAITS>
class lemon::TabuSearch< GRAPH, VALUE, POLICY, TRAITS >

This class offers the implementation of tabu-search algorithm. The tabu-serach is a local-search. It starts from a specified point of the problem's graph representation, and in every step it goes to the localy best next Node except those in tabu set. The maximum size of this tabu set defines how many Node will be remembered. The best Node ever found will also stored, so we wont lose it, even is the search continues. The class can be used on any kind of Graph and with any kind of Value with a total-settlement on it.

Parameters:

	_Graph	The graph type the algorithm runs on.
	_Value	The values' type associated to the nodes.
	_Policy	Controlls the search. Determinates when to stop, or how manage stuck search. Default value is IterationPolicy .
	_Traits	Collection of needed types. Default value is TabuSearchDefaultTraits .

Author:

Szabadkai Mark

#include <lemon/tabu_search.h>

List of all members.

Classes
class	BadParameterError
	Thrown by setting the size of the tabu-set and the given size is less than 2. More...
Public Types
typedef TabuSearch< GRAPH, VALUE, POLICY, TRAITS >	SelfType
	Public types.
Public Member Functions
	TabuSearch (const Graph &graph, const HeightMap &hm, const int tabusz=3, Policy p=Policy())
	Constructor.
	~TabuSearch ()
	Destructor.
void	tabuSize (const unsigned int size)
	Set/Get the size of the tabu set.
void	policy (Policy p)
	Set/Get Policy.
Execution control
The simplest way to execute the algorithm is to use the member functions called run( 'startnode' ).
void	init (const Node startn)
	Initializes the internal data.
bool	step ()
	Does one iteration.
void	run (const Node startn)
	Runs a search while the Policy stops it.
Query Functions
The result of the TabuSearch algorithm can be obtained using these functions.
Node	current () const
	The node, the search is standing on.
Node	best () const
	The best node found until now.
TabuIterator	tabu_begin () const
	Beginning to iterate on the current tabu set.
TabuIterator	tabu_end () const
	Ending to iterate on the current tabu set.
Protected Attributes
std::deque< Node >	tabu
	The tabu set. Teh current node is the first.
unsigned int	mts
	Maximal tabu size.
Node	b
	The best Node found.

---

Constructor & Destructor Documentation

TabuSearch	(	const Graph &	graph,
		const HeightMap &	hm,
		const int	tabusz = 3,
		Policy	p = Policy()
	)			[inline]

Parameters:

	graph	the graph the algorithm will run on.
	hm	the height map used by the algorithm.
	tabusz	the maximal size of the tabu set. Default value is 3
	p	the Policy controlling the search.

---

Member Function Documentation

void init

(

const Node

startn

)

[inline]

Parameters:

startn

The start node where the search begins.

bool step

(

)

[inline]

If the Policy allows it searches for the best next node, then steps onto it.

Returns:

False if one Policy condition wants to stop the search.

Request premmision from ControllPolicy

Find the best next potential node

Handle stuck search

Move on...

void run

(

const Node

startn

)

[inline]

Parameters:

startn

The start node where the search begins.