python - 如何实现状态空间树？

Question

我正在尝试解决来自 MIT OCW 的类似背包的问题.它的问题集 5。

我需要使用分支定界算法来找到最佳状态。所以我需要实现一个状态空间树。我理解这个算法的思想，但我发现它并不那么容易实现。

如果我发现预算不够的节点，我应该就此打住。我应该为每个树节点添加一个属性吗？

当我添加节点时，我应该从上界最大的节点开始。我怎样才能找到这样的节点？添加每个节点之前是否需要遍历所有节点？或者我可以保存一些 var 来帮助解决这个问题吗？

你有什么想法吗？你能用 python 实现它吗？

Answer 1

我希望我能正确理解问题，如果没有，请指导我:)
(很抱歉“状态”的两种不同含义引起的混淆)

您当然可以在节点中添加属性(它是状态的一部分!)，因为它的数据量非常小。请注意，保存它不是强制性的，因为它隐含地存在于状态的其余部分(给定您已经选择的状态，您可以计算它)。就个人而言，我会添加该属性，因为多次计算它没有意义。

关于第二个问题:IIRC，当你添加节点时，你不必遍历所有树，而只需要遍历边缘(即没有后代的节点集 - 不要被树的最深层次)。由于您正在寻找上限，(并且由于您仅使用正成本)，因此在三种情况下您正在寻找具有最高值的节点:

• 在最后一步中，您附加到具有最高值的节点，因此您刚刚添加的节点现在具有最高值
• 在添加的最后一步超出了预算，因此您不得不排除该选项。尝试添加另一个状态
• 没有更多状态可以尝试添加以构建新节点。这个分支不能再进一步了。查看其他节点中最高值的边缘