Detailed Description

results of the brute-force algorithm

The brute-force algorithm performs an exhausitve search on any combination of intervals. It has exponential time complexity.

Results of the greedy algorithm are used to derive lower and upper bounds (and thus allow to reduce computation time, somewhat).

Definition at line 258 of file kalgorithm.h.

#include <kalgorithm.h>

Public Member Functions
bool	valid () const

	BruteForce ()
	empty constructor More...

Public Attributes
int	k_min = 0
	lower bound derived from greedy results. k_min = max{greedy.k_x,greedy.k_y} More...

int	k_max = 0
	upper bound derived from greedy results. k_max = min{greedy.k_xy,greedy.k_yx} More...

int	k_current
	current number of selected components More...

int	k_iteration
	optimal value of last iteration More...

int	k_optimal
	optimal value so far More...

data::BitSet	result
	subsset of selected components More...

Stack	stack1
	stacks used for backtracking More...

Stack	stack2

Constructor & Destructor Documentation

◆ BruteForce()

frechet::k::kAlgorithm::BruteForce::BruteForce ( )

inline

empty constructor

Definition at line 282 of file kalgorithm.h.

Member Function Documentation

◆ valid()

bool frechet::k::kAlgorithm::BruteForce::valid ( ) const

inline

Returns: true if there is a valid result

Definition at line 279 of file kalgorithm.h.

Member Data Documentation

◆ k_current

int frechet::k::kAlgorithm::BruteForce::k_current

current number of selected components

Definition at line 267 of file kalgorithm.h.

◆ k_iteration

int frechet::k::kAlgorithm::BruteForce::k_iteration

optimal value of last iteration

Definition at line 269 of file kalgorithm.h.

◆ k_max

int frechet::k::kAlgorithm::BruteForce::k_max = 0

upper bound derived from greedy results. k_max = min{greedy.k_xy,greedy.k_yx}

Definition at line 265 of file kalgorithm.h.

◆ k_min

int frechet::k::kAlgorithm::BruteForce::k_min = 0

lower bound derived from greedy results. k_min = max{greedy.k_x,greedy.k_y}

Definition at line 263 of file kalgorithm.h.

◆ k_optimal

int frechet::k::kAlgorithm::BruteForce::k_optimal

optimal value so far

Definition at line 271 of file kalgorithm.h.

◆ result

data::BitSet frechet::k::kAlgorithm::BruteForce::result

subsset of selected components

Definition at line 274 of file kalgorithm.h.

◆ stack1

Stack frechet::k::kAlgorithm::BruteForce::stack1

stacks used for backtracking

Definition at line 276 of file kalgorithm.h.

◆ stack2

Stack frechet::k::kAlgorithm::BruteForce::stack2