如何实现状态空间树？
我正在尝试解决一个类似背包问题的题目，来自MIT OCW，这是他们的作业集5。
我需要使用分支限界算法来找到最佳状态。所以我需要实现一个状态空间树。我理解这个算法的基本思路，但发现实现起来并不是那么简单。
如果我发现某个节点的预算不够，我应该在这里停止。那我是否需要给每个树节点添加一个属性呢？
在添加一个节点时，我应该从上界最大的节点开始。那我该如何找到这样的节点呢？我需要在添加每个节点之前遍历所有节点吗？还是可以保存一些变量来帮助我？
你有什么想法吗？能用Python实现一下吗？
1 个回答
2
我希望我理解了这个问题，如果没有，请告诉我哦 :)
（抱歉因为“状态”这个词有两个不同的意思而造成的混淆）
当然，你可以在节点中添加这个属性（这也是状态的一部分！），因为它的数据量非常小。不过要注意，保存这个属性并不是必须的，因为它在其他状态中隐含存在（根据你已经选择的状态，你可以计算出这个属性）。我个人会选择添加这个属性，因为没必要每次都去计算它。
关于第二个问题：如果我没记错的话，当你添加节点时，不需要遍历整棵树，而只需要看边缘节点（也就是那些没有子节点的节点——不要和树的最深层混淆）。因为你在寻找一个上限（而且你只用正数），所以在寻找值最高的节点时，有三种情况：
- 在最后一步，你添加到了值最高的节点上，所以你刚添加的节点现在就是值最高的节点
- 在最后一步添加时，你超出了预算，所以你必须排除这个选项。试着添加另一个状态
- 没有更多的状态可以尝试添加来构建新节点。这条分支无法继续。看看其他节点的边缘，找出最高的值