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'.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-06 UTC."],[[["\u003cp\u003e\u003ccode\u003eKnapsackSearchPath\u003c/code\u003e is a class representing the path between nodes in a knapsack problem search tree, used for efficient state reconstruction.\u003c/p\u003e\n"],["\u003cp\u003eIt leverages an incremental update approach to rebuild the solution state at each node, offering better average complexity than applying all decisions from the root.\u003c/p\u003e\n"],["\u003cp\u003eThe \u003ccode\u003evia\u003c/code\u003e field stores the common parent of the \u003ccode\u003efrom\u003c/code\u003e and \u003ccode\u003eto\u003c/code\u003e nodes, enabling optimized state reconstruction by reverting and applying decisions between these nodes.\u003c/p\u003e\n"]]],["`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,["# KnapsackSearchPath\n\nC++ Reference: class KnapsackSearchPath\n=======================================\n\n\nNote: This documentation is automatically generated.\n\n----- KnapsackSearchPath ----- \nKnapsackSearchPath 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). \n\nHowever, 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'. \n\nThe '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'.\n\n| Method ||\n|----------------------------------------------------------------------------------------------------------------|---------------------------------------------------------------------------------------------------------|\n| [`from`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver.h#L396) | Return type: `const KnapsackSearchNode& ` \u003cbr /\u003e |\n| [`Init`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver.h#L395) | Return type: `void ` \u003cbr /\u003e |\n| [`KnapsackSearchPath`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver.h#L393) | \u003cbr /\u003e Arguments: `const KnapsackSearchNode& from, const KnapsackSearchNode& to` \u003cbr /\u003e |\n| [`MoveUpToDepth`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver.h#L399) | Return type: `const KnapsackSearchNode* ` Arguments: `const KnapsackSearchNode& node, int depth` \u003cbr /\u003e |\n| [`to`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver.h#L398) | Return type: `const KnapsackSearchNode& ` \u003cbr /\u003e |\n| [`via`](https://github.com/google/or-tools/blob/v9.4/ortools/algorithms/knapsack_solver.h#L397) | Return type: `const KnapsackSearchNode& ` \u003cbr /\u003e |"]]
