operations_research::KnapsackSearchPath Class Reference

#include <knapsack_solver.h>

Public Member Functions
	KnapsackSearchPath (const KnapsackSearchNode &from, const KnapsackSearchNode &to)
	--— KnapsackSearchPath --—
	KnapsackSearchPath (const KnapsackSearchPath &)=delete
	This type is neither copyable nor movable.
KnapsackSearchPath &	operator= (const KnapsackSearchPath &)=delete
void	Init ()
const KnapsackSearchNode &	from () const
const KnapsackSearchNode &	via () const
const KnapsackSearchNode &	to () const
const KnapsackSearchNode *	MoveUpToDepth (const KnapsackSearchNode &node, int depth) const

Detailed Description

--— KnapsackSearchPath --— KnapsackSearchPath is a small class used to represent the path between a node to another node in the search tree. As the solution state is not stored for each search node, the state should be rebuilt at each node. One simple solution is to apply all decisions between the node 'to' and the root. This can be computed in O(number_of_items).

However, it is possible to achieve better average complexity. Two consecutively explored nodes are usually close enough (i.e., much less than number_of_items) to benefit from an incremental update from the node 'from' to the node 'to'.

The 'via' field is the common parent of 'from' field and 'to' field. So the state can be built by reverting all decisions from 'from' to 'via' and then applying all decisions from 'via' to 'to'.

Definition at line 404 of file knapsack_solver.h.

Constructor & Destructor Documentation

KnapsackSearchPath() [1/2]

operations_research::KnapsackSearchPath::KnapsackSearchPath	(	const KnapsackSearchNode &	from,
		const KnapsackSearchNode &	to )

--— KnapsackSearchPath --—

Definition at line 120 of file knapsack_solver.cc.

KnapsackSearchPath() [2/2]

operations_research::KnapsackSearchPath::KnapsackSearchPath ( const KnapsackSearchPath & )

delete

This type is neither copyable nor movable.

Member Function Documentation

from()

const KnapsackSearchNode & operations_research::KnapsackSearchPath::from ( ) const

inline

Definition at line 416 of file knapsack_solver.h.

Init()

void operations_research::KnapsackSearchPath::Init

(

)

Find common parent.

Definition at line 124 of file knapsack_solver.cc.

MoveUpToDepth()

const KnapsackSearchNode * operations_research::KnapsackSearchPath::MoveUpToDepth	(	const KnapsackSearchNode &	node,
		int	depth ) const

Definition at line 137 of file knapsack_solver.cc.

operator=()

KnapsackSearchPath & operations_research::KnapsackSearchPath::operator= ( const KnapsackSearchPath & )

delete

to()

const KnapsackSearchNode & operations_research::KnapsackSearchPath::to ( ) const

inline

Definition at line 418 of file knapsack_solver.h.

via()

const KnapsackSearchNode & operations_research::KnapsackSearchPath::via ( ) const

inline

Definition at line 417 of file knapsack_solver.h.

---

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

• ortools/algorithms/knapsack_solver.h
• ortools/algorithms/knapsack_solver.cc