Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
// doxy/ or-tools/ src/ algorithms/ |
#include <knapsack_solver.h>
Public Member Functions | |
KnapsackSearchPath (const KnapsackSearchNode &from, const KnapsackSearchNode &to) | |
KnapsackSearchPath. | |
void | Init () |
const KnapsackSearchNode & | from () const |
const KnapsackSearchNode & | via () const |
const KnapsackSearchNode & | to () const |
const KnapsackSearchNode * | MoveUpToDepth (const KnapsackSearchNode &node, int depth) const |
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 (ie. much less than number_of_items) to benefit from an incremental update from the node 'from' to the node 'to'. '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 applying all decisions from 'via' to 'to'.
Definition at line 292 of file knapsack_solver.h.
operations_research::KnapsackSearchPath::KnapsackSearchPath | ( | const KnapsackSearchNode & | from, | |
const KnapsackSearchNode & | to | |||
) |
void operations_research::KnapsackSearchPath::Init | ( | ) |
Definition at line 120 of file knapsack_solver.cc.
const KnapsackSearchNode& operations_research::KnapsackSearchPath::from | ( | ) | const [inline] |
Definition at line 297 of file knapsack_solver.h.
const KnapsackSearchNode& operations_research::KnapsackSearchPath::via | ( | ) | const [inline] |
Definition at line 298 of file knapsack_solver.h.
const KnapsackSearchNode& operations_research::KnapsackSearchPath::to | ( | ) | const [inline] |
Definition at line 299 of file knapsack_solver.h.
const KnapsackSearchNode * operations_research::KnapsackSearchPath::MoveUpToDepth | ( | const KnapsackSearchNode & | node, | |
int | depth | |||
) | const |
Definition at line 133 of file knapsack_solver.cc.