Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::LatticeMemoryManager< Set, CostType > Class Template Reference

#include <hamiltonian_path.h>

Public Member Functions

 LatticeMemoryManager ()
void Init (int max_card)
 Reserves memory and fills in the data necessary to access memory.
uint64_t Offset (Set s, int node) const
 Returns the offset in memory for f(s, node), with node contained in s.
uint64_t BaseOffset (int card, Set s) const
uint64_t OffsetDelta (int card, int added_node, int removed_node, int rank) const
void SetValue (Set s, int node, CostType value)
void SetValueAtOffset (uint64_t offset, CostType value)
CostType Value (Set s, int node) const
CostType ValueAtOffset (uint64_t offset) const

Detailed Description

template<typename Set, typename CostType>
class operations_research::LatticeMemoryManager< Set, CostType >

The Dynamic Programming (DP) algorithm memorizes the values f(set, node) for node in set, for all the subsets of cardinality <= max_card_. LatticeMemoryManager manages the storage of f(set, node) so that the DP iteration access memory in increasing addresses.

Definition at line 296 of file hamiltonian_path.h.

Constructor & Destructor Documentation

◆ LatticeMemoryManager()

template<typename Set, typename CostType>
operations_research::LatticeMemoryManager< Set, CostType >::LatticeMemoryManager ( )
inline

Definition at line 298 of file hamiltonian_path.h.

Member Function Documentation

◆ BaseOffset()

template<typename Set, typename CostType>
uint64_t operations_research::LatticeMemoryManager< Set, CostType >::BaseOffset ( int card,
Set s ) const
inline

Returns the base offset in memory for f(s, node), with node contained in s. This is useful in the Dynamic Programming iterations. Note(user): inlining this function gains about 5%.

Todo
(user): Investigate how to compute BaseOffset(card - 1, s \ { n }) from BaseOffset(card, n) to speed up the DP iteration.

There are binomial_coefficients_[node][node_rank + 1] sets which have node at node_rank.

Note(user): It is possible to get rid of base_offset_[card] by using a 2-D array. It would also make it possible to free all the memory but the layer being constructed and the preceding one, if another lattice of paths is constructed.

Todo
(user): Evaluate the interest of the above. There are 'card' f(set, j) to store. That is why we need to multiply local_offset by card before adding it to the corresponding base_offset_.

Definition at line 412 of file hamiltonian_path.h.

◆ Init()

template<typename Set, typename CostType>
void operations_research::LatticeMemoryManager< Set, CostType >::Init ( int max_card)

Reserves memory and fills in the data necessary to access memory.

Initialize binomial_coefficients_ using Pascal's triangle recurrence

Extend to (n, n + 1) to minimize branchings in LatticeMemoryManager(). This also makes the recurrence above work for k = n.

There are k * binomial_coefficients_[max_card_][k] f(S,j) values to store for each group of f(S,j), with card(S) = k. Update base_offset[k] accordingly.

Definition at line 362 of file hamiltonian_path.h.

◆ Offset()

template<typename Set, typename CostType>
uint64_t operations_research::LatticeMemoryManager< Set, CostType >::Offset ( Set s,
int node ) const

Returns the offset in memory for f(s, node), with node contained in s.

Definition at line 436 of file hamiltonian_path.h.

◆ OffsetDelta()

template<typename Set, typename CostType>
uint64_t operations_research::LatticeMemoryManager< Set, CostType >::OffsetDelta ( int card,
int added_node,
int removed_node,
int rank ) const
inline

Returns the offset delta for a set of cardinality 'card', to which node 'removed_node' is replaced by 'added_node' at 'rank'

Definition at line 315 of file hamiltonian_path.h.

◆ SetValue()

template<typename Set, typename CostType>
void operations_research::LatticeMemoryManager< Set, CostType >::SetValue ( Set s,
int node,
CostType value )

Memorizes the value = f(s, node) at the correct offset. This is favored in all other uses than the Dynamic Programming iterations.

Definition at line 448 of file hamiltonian_path.h.

◆ SetValueAtOffset()

template<typename Set, typename CostType>
void operations_research::LatticeMemoryManager< Set, CostType >::SetValueAtOffset ( uint64_t offset,
CostType value )
inline

Memorizes 'value' at 'offset'. This is useful in the Dynamic Programming iterations where we want to avoid compute the offset of a pair (set, node).

Definition at line 328 of file hamiltonian_path.h.

◆ Value()

template<typename Set, typename CostType>
CostType operations_research::LatticeMemoryManager< Set, CostType >::Value ( Set s,
int node ) const

Returns the memorized value f(s, node) with node in s. This is favored in all other uses than the Dynamic Programming iterations.

Definition at line 442 of file hamiltonian_path.h.

◆ ValueAtOffset()

template<typename Set, typename CostType>
CostType operations_research::LatticeMemoryManager< Set, CostType >::ValueAtOffset ( uint64_t offset) const
inline

Returns the memorized value at 'offset'. This is useful in the Dynamic Programming iterations.

Definition at line 338 of file hamiltonian_path.h.

The documentation for this class was generated from the following file: