状態空間ツリーを実装する方法は？

Question

私はMIT OCWからナップザックのような問題を解決しようとしています。 その問題が設定されました。5

最適な状態を見つけるためにブランチとバインドされたアルゴリズムを使用する必要があります。 したがって、状態空間ツリーを実装する必要があります。 私はこのアルゴリズムの考え方を理解していますが、実装するのはそれほど簡単ではありません。

予算が足りないノードが見つかった場合は、ここで停止する必要があります。 すべてのツリーノードに属性を追加する必要がありますか？

ノードを追加するとき、最大の上限を持つノードから開始する必要があります。 どのようにしてそのようなノードを見つけることができますか？各ノードを追加する前に、すべてのノードを走査する必要がありますか？または、それを助けるためにいくつかの変数を保存することはできますか？

ご存知ですか？それをPythonで実装できますか？

私を指示してくださいいない場合、私は、私が正しく問題を理解願っています:)
（「状態」の二つの異なる意味から生じる混乱して申し訳ありません）

あなたはもちろんで属性を追加することができます

Answer 1

ノード（それは状態の一部です！）は非常に小さいデータ量ですから。あなたがすでに選択した状態が与えられれば、あなたがそれを計算することができるので、それが国の残りの部分に暗黙的に存在するので、それを保存することは必須ではないことに注意してください。個人的には、何度も何度も計算する必要がないので、属性を追加します。

第2の質問：IIRCでは、ノードを追加するときに、ツリー全体を走査する必要はなく、フリンジだけ（すなわち、子孫のないノードの集合 - 混乱しないでください。ツリーの最も深いレベル）。 あなたは、上限を探しているので（とあなたが唯一の正のコストを使用しているので）あなたが最も高い値を持つノードを探しているとき、3例があります。最後のステップあなたの

• 最も高い値を持つノードに追加されているため、最後に追加したノードには、最後に追加した値の最大値が
• となっているため、このオプションを除外する必要がありました。別の状態を追加しようとしてください。
• 新しいノードを構築するために追加しようとする状態はこれ以上ありません。このブランチはさらに進まない。他のノードの中で最高の価値を見いだしてください。