How to implement a state-space tree?

Question

I'm trying to solve a knapsack like problem from MIT OCW. It's problem set 5.

I need use branch and bound algorithm to find the optimal states. So I need implement a state-space tree. I understand the idea of this algorithm, but I find it's not so easy to implement.

If I find a node that with it, the budget is not enough, I should stop here. Should I add a attribute to every tree node?

When I add node, I should start from a node with the largest upper bound. How can I find such one? Need I traverse all the node before I add each node? Or record something?

Do you have any idea? Could you implement it in python? Thanks.

Answer 1

I hope I understood correctly the problem, if not please direct me :)
(sorry for the confusion arising from the two different meanings of "state")

You can of course add the attribute in the node (it's part of the state!), since it's a very tiny amount of data. Mind that it is not mandatory to save it though, since it is implicitly present in the rest of the state (given the states that you have already chosen, you can compute it). Personally, I'd add the attribute, since there's no point in calculating it many times.

On the second question: IIRC, when you add nodes, you don't have to traverse ALL the tree, but rather only the fringe (that is, the set of nodes which have no descendants - not to be confused by the deepest level of the tree). Since you're looking for an upper bound, (and since you're using only positive costs), there are three cases when you are looking for the node with the highest value:

• on the last step you appended to the node which had the highest value, so the node which you just added has now the highest value
• on the last step adding the you exceeded the budget, so you had to exclude the option. try to add another state
• there are no more states to try to add to build a new node. This branch can't go further. Look at the fringe for the highest value in the other nodes