Access to the final Held-Karp lower bound tree #3906
Unanswered
TryerGit
asked this question in
Graph and Algorithms
Replies: 0 comments
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Hello,
I would like to access the final Held-Karp lower bound tree for the TSP.
Looking at documentation about it available at : https://developers.google.com/optimization/reference/graph/one_tree_lower_bound
it is not clear to me which function returns the tree. The return value seems to be a double with signature:
const double lower_bound = ComputeOneTreeLowerBound(number_of_nodes, cost_function); //where number_of_nodes is the number of nodes in the TSP and cost_function is a function returning the cost between two nodes.
The actual tree that attains the lower bound does seem to be accessible : See, for e.g., https://ojmo.centre-mersenne.org/item/10.5802/ojmo.11.pdf Page 15, Algorithm 11
I was looking for some algorithm like what boost offers for the normal MST:
std::vector < Edge > spanning_tree; kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));which returns in
spanning_tree, the actual edges that feature in the MST.Thank you.
Beta Was this translation helpful? Give feedback.
All reactions