Stay organized with collections
Save and categorize content based on your preferences.
C++ Reference: class KnapsackSearchPath
Note: This documentation is automatically generated.
----- 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'.
| Method |
from | Return type: const KnapsackSearchNode& |
Init | Return type: void |
KnapsackSearchPath | Arguments: const KnapsackSearchNode& from,
const KnapsackSearchNode& to |
MoveUpToDepth | Return type: const KnapsackSearchNode* Arguments: const KnapsackSearchNode& node,
int depth |
to | Return type: const KnapsackSearchNode& |
via | Return type: const KnapsackSearchNode& |
Except as otherwise noted, the content of this page is licensed under the Creative Commons Attribution 4.0 License, and code samples are licensed under the Apache 2.0 License. For details, see the Google Developers Site Policies. Java is a registered trademark of Oracle and/or its affiliates.
Last updated 2024-08-06 UTC.
[null,null,["Last updated 2024-08-06 UTC."],[],["`KnapsackSearchPath` represents the path between two nodes in a search tree. Instead of rebuilding the state from the root for each node, which takes O(number_of_items), it uses an incremental approach. It defines 'from,' 'to,' and 'via' nodes, where 'via' is the common parent. State is built by reverting decisions from 'from' to 'via', then applying decisions from 'via' to 'to', enabling more efficient updates. Key methods include `from`, `to`, `via`, and `MoveUpToDepth`.\n"],null,[]]
